Quantum computers have demonstrated great potential for solving certain problems more efficiently than their classical counterpart. Algorithms based on the quantum Fourier transform (QFT) such as Shor’s algorithm offer an exponential speed-up, while amplitude-amplification algorithms such as Grover’s search algorithm provide us with a polynomial speedup. The concept of “quantum supremacy” (quantum computers outperforming classical computers) has been explored for three general groups of problems:
- Structured problems, such as factoring and discrete logarithm. Out quantum computer takes advantage of the structure of these classes of problems to offer an exponential speedup compared to the best known classical alternative. While these speedups are the most promising, they require a large number of resources and are cannot be feasibly implemented in the near future.
- Quantum Simulations, originally proposed by Richard Feynman in the late 80s was thought to be the first motivation behind exploring quantum computation. Due to the fact that the space of all possible states of the system scales exponentially with the addition of a new element (eg. an atom), complex systems are very difficult to simulate classically. It has been shown that we can use a quantum computer to tackle interesting problems in quantum chemistry and chemical engineering. Furthermore, there are results on sampling the output of random quantum circuits which have been used for “quantum supremacy experiments”.
- General constraint satisfaction and optimization problems. Since these problems are NP-hard it is widely believed that we cannot gain an exponential speedup using a quantum computer, however, we can obtain quadratic speedup but utilizing a variation of Grover’s algorithm.
While these quantum algorithms are very exciting, they are beyond the capabilities of our near-term quantum computers; for example, any useful application of Shor’s factoring algorithm requires anywhere between tens of thousands to millions of qubits with error correction compared to quantum devices with hundreds of qubits that we might have available in the next few years.
Recently there has been increasing interest in hybrid classical-quantum algorithms among the community. The general idea behind this approach is to supplement the noisy intermediate-scale quantum (NISQ) devices with classical computers. In this blog post, we discuss the Quantum Approximate Optimization Algorithm (QAOA), which is a hybrid algorithm, alongside some of its applications.
QAOA is used for optimizing combinatorial problems. Let’s assume a problem with bits and clauses. Each clause is a constraint on a subset of the bits which satisfies a certain assignment. We can define a cost function as follows:
where is the bit string. In this article we consider a minimization problem, therefore we want if satisfies clause and 1 otherwise. Note that in the case of a maximization problem we only need to switch the value assigned to a satisfactory clause to 1. Our objective is to find a (qu)bit string that minimizes (or maximizes) our cost function.
At a higher level, we start with a quantum state in a uniform superposition of all possible inputs . This can be accomplished with qubits which span a space of size . Our goal is to come up with a series of operations that would evolve our initial quantum state into a superposition of states in which the valid solutions would have a significantly higher probability than other states. In manner, upon sampling the quantum state we are likely to get the correct solution with high probability. QAOA uses the cost function to construct a set of operations that would be able to efficiently map the unifrom superposition state into the desired quantum state. These operators involve single qubits rotations around the x-axis, and multiqubit rotations around the z-axis of our qubits.
Now let’s discuss the details of QAOA. For this algorithm we assume that our quantum computer works in the computation basis of . We start by setting our initial state to a uniform superposition over computational basis states:
Next, we define a unitary operator using the cost function as follows:
Here we convert every clause to a Hamiltonian consisting of Pauli Z ($\sigma^z$) operators. Just as a review, the two Pauli operators (X and Z) used in this blog post are representated as follows:
For example if we can map the clause to for a minimization problem. If , then will return a value of 1, and if the operator will return -1. The same applies to qubit as well. Therefore it is not hard to see that if and have the same value, then the operator as defined above will result in a 1, and it’ll result in 0 otherwise. Furthermore, since has integer eigenvalues we can restrict the angle to lie in .
Next, we define the admixing Hamiltonian:
and use it to define a unitary operator which consists of a product of commuting one qubit operations:
where . It’s easy to see that couples 2 or more qubits, while performs a single qubit rotation on the qubits in our system. Using these unitaries and our initial state we define a QAOA angle-dependent “ansatz” state as follows:
Here is the “depth” of our QAOA circuit, and , are each a vector of length controlling the angles for each layer. In the worst case scenario this state can be produce by a quantum circuit of depth , however by taking advantage of the structure of the instance we can further reduce the number of layers required. Let be the expectation of in our ansatz:
and let be the minimum of over angles,
Note that minimization at layers can be viewed as a constrained minimization at layers, therefore
Using an adiabatic approach  We can show that
Based on these results our QAOA algorithm will look like the following:
- c: pick a
- c: choose a set of angles
- q: prepare
- q: compute
- c: perform gradient descend/ascend on and get a new set of angles
- repeat from step 3 till convergence
- report the measurement result of in computational basis
If does not asymptotically grow with can be efficiently computed in
In this section we apply the QAOA algorithm to the MaxCut problem with bounded degree. MaxCut is an NP-hard problem that asks for a subset of the vertex set such that the number of edges between and the complementary subset is as large as possible. While QAOA does not offer a theoretical guarantee to solve MaxCut in polynomial time, it offers a path to utilizing NISQ devices for tackling such optimization problems and discuss patterns in such problems that can be used for reducing the number of steps required.
For this section, let’s assume , and we have a graph with vertices and an edge set of size . We can construct a cost function to be maximized as follows:
We can the compute the angle dependent cost of our ansatz as follows:
Let’s consider the operation associated with some edge :
Since QAOA consists of local operations, we may take advantage by thinking about the problem in terms of subproblems (or subgraphs) involving certain nodes. This property will allow us to simplify our clauses even further depending on the desired depth of our quantum circuit, therefore decreasing the amount of resources necessary to implement the algorithm.
The operator includes qubits (nodes) and , therefore the sequence of operators above will only involve qubits that are at most distance away from qubits and . Let’s consider the example of :
It’s easy to see that any factor of that does not depend on or will commute through and cancel out. Since the degree is bounded, each subgraph contains a number of qubits that is independent of , which allows for the evaluation of in terms of subsystems of size independent of .
For an subgraph define:
We can define our total cost as a sum over the cost of each subgraph:
where is a subgraph of type and “…” is used to omit the sequence of angle depending unitaries constructed using the elements of and . is then
where is the number of occurrence of the subgraph in the original edge sum. The function does not depend on and , and the only dependence on these variables comes through the weights from the original graph. The maximum number of qubits that can appear in our sequence of operators comes when the subgraph is a tree. For a graph with maximum degree , the number of qubits in this tree is
(or if ), which is independent of and . Therefore we can see that for constant can be efficiently computed.
Next, let’s consider the spread of C measured in the state .
For fixed and we see that the standard deviation of is upper-bounded by . Using this fact and the appropriate probability bounds we can see that the result of measuring the cost function of the state will be very close to the intended value of which bounds the uncertainty present in quantum measurement.
 E. Farhi, J. Goldstone, and S. Gutmann, “A Quantum Approximate Optimization Algorithm,” 2014.
 J. S. Otterbach, et. al, “Unsupervised Machine Learning on a Hybrid Quantum Computer,” 2017.