Quantum Approximate Optimization Algorithm (QAOA)

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).

What are Approximation Algorithms?

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 in Action

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:

• Financial portfolio optimization, which leverages QAOA to optimize allocations of assets so as to minimize risk and maximize profits for investment portfolios
• Credit scoring, which determines the credit worthiness of individuals or organizations so as to help make lending decisions
• Infrastructure optimizations, which leverage QAOA to optimize times, costs, or even safety for such things as delivery routes, air traffic routes, and shipping routes
• Scheduling, which may seek such benefits as minimizing manufacturing times or minimizing associated labor costs 
• Placement, maximizing coverage and minimizing overlap for locations such as cellular towers, coffee shops, restaurants, and electric vehicle (EV) recharging stations
• Cargo, which involves maximizing the total value of the contents in a container considering the volumes and weights of the individual items that may be selected
• Combinatorial optimization problems, which leverage QAOA to find optimal solutions within very large sets of solutions, such as Maximum Cut (MaxCut) and Maximum Independent Set (MIS) problems

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.

Approximation Algorithms Challenges and Limitations

Like the NP-hard problems they try to solve, approximation algorithms have their own challenges and limitations:

• Whether classical or quantum, algorithms must have mathematical proofs showing that their performance is near-optimal even when the optimal solutions are not known
• For many specific, important problems, there might not be any known approaches to finding precise solutions within polynomial time
• If approximations are acceptable in lieu of precise solutions, a determination needs to be made as to how close approximations need to be in order to be acceptable

Quantum approximation algorithms have additional challenges and limitations:

• The approximations are not guaranteed to be the best possible results, they’re only guaranteed to be within the range of acceptably close results
• This means that an algorithm such as QAOA may be run again, and the results might be either closer or farther away from the optimal results
• QAOA and VQE both rely on classical machine learning algorithms, which introduce their own challenges and limitations
• Current quantum computers are too error-prone to be of any usefulness today, and the fault-tolerant quantum computers of tomorrow will run different classes of algorithms
• The problem with errors is that it can take longer to converge at solutions as the values occasionally diverge away from the optimal solutions

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.

‍