As a consequence of the widely-believed P ≠ NP conjecture, there is a broad classification of NP-hard optimization problems for which precise solutions cannot be found in polynomial time. Approximation algorithms are a class of algorithms, born from theoretical computer science, that efficiently find approximate, provably near-optimal solutions to these optimization problems. Together, approximation and randomized algorithms arose as possible solutions to intractability.
The first challenge of approximation algorithms is to approximate solutions to problems as close as possible to the optimal solutions while remaining within polynomial time. The second challenge is to guarantee the closeness of the approximations through mathematical proofs of the worst-case results. These mathematical proofs are crucial, because they distinguish approximation algorithms from heuristics, which are not guaranteed to succeed. Examples of heuristics include annealing and genetic algorithms.
It is import to note that approximation is not limited to numerical problems. The approximate string matching algorithm, also known as fuzzy string searching, finds strings of characters that approximately match patterns, as opposed to finding only exact matches. Another example is the successive approximation algorithm, which converts continuous analog waveforms into discrete digital representations within analog-to-digital converters (ADCs).
Not all approximation algorithms are classical algorithms. Quantum approximation algorithms are a classification of quantum algorithms that, like their classical counterparts, find approximate solutions for combinatorial optimization problems. They consist of parameterized quantum circuits alongside classical neural networks which determine the optimal parameters within these quantum circuits. While the term “advantage” is often applied to potential speed advantages using quantum computers, another possible advantage could be providing higher-quality approximations, which is what these quantum algorithms aim to do.
The most popular quantum approximation algorithms are QAOA and VQE, although both have become families of algorithms, rather than just individual algorithms. As we note in our article titled “Quantum Approximate Optimization Algorithm (QAOA),” QAOA seeks to find approximate solutions to NP-hard combinatorial optimization problems, which become more and more challenging to solve precisely as problem sizes grow. As we further note in our article titled “Variational Quantum Algorithm,” this hybrid classical-quantum approach can be used to approximate eigenvalue problems in addition to optimization problems.
Quantum approximation algorithms have steadily grown in popularity due to their practicality relative to quantum algorithms that require large, fault-tolerant quantum computers that do not yet exist. As a result of their ability to be executed on current quantum computers, the number of use cases being researched has grown considerably in recent years. At a high-level, a sampling of these applications include:
It is important to note that quantum approximation algorithms, such as QAOA, are not the only possible solvers for these classes of problems. For example, Rydberg blockades naturally and efficiently solve MIS and Maximum Clique problems on neutral atom quantum computers. The relative popularity of QAOA is due to it being around longer, but acceleration can be observed in neutral atom research as it relates to optimization and other problems.
Like the NP-hard problems they try to solve, approximation algorithms have their own challenges and limitations:
Quantum approximation algorithms have additional challenges and limitations:
One of the major challenges of the third point is the integration of classical neural networks with parameterized quantum circuits. As the quantum circuits grow to tackle larger optimization problems, the number of parameters grows. The complexity of optimizing larger numbers of parameters, paradoxically, becomes its own optimization problem. This is an ongoing area of research.
One such research project is “Approximation Algorithms Quantum Information & Semidefinite Optimization” by Centrum Wiskunde & Informatica (CWI), which is the Netherlands’ national research institute for mathematics and computer science. This group of researchers seeks to maximize the efficiency of approximation considering both classical and quantum computational resources.
Join the discussion! A question titled “Quantum approximation algorithms” was asked on Stack Exchange Theoretical Computer Science some years ago, and there are links to papers that may be of interest. These papers may lay a strong foundation for beginning to explore the latest research into solving combinatorial optimization problems using neutral atom quantum computers. That discussion continues in Discourse and Slack channels.