In this tutorial we show how to (approximately) solve binary combinatorial optimization problems, using the Quantum Approximate Optimization Algorithm (QAOA). The QAOA algorithm belongs to the class of hybrid quantum algorithms (leveraging both classical as well as quantum compute), that are widely believed to be the working horse for the current NISQ (noisy intermediate-scale quantum) era. In this NISQ era QAOA is also an emerging approach for benchmarking quantum devices and is a prime candidate for demonstrating a practical quantum speed-up on near-term NISQ device [1,4]. To validate our approach we benchmark our results with exact results as obtained from classical QUBO solvers.
We provide a step-by-step walkthrough explaining the QAOA quantum algorithm and show how to build the corresponding parametrized quantum circuit ansatz using the Braket SDK, with simple modular building blocks (that can be re-used for other purposes). We use open-source off-the-shelf scipy optimizers for classical numerical optimization. While we demonstrate our proof-of-concept approach using classical simulators for circuit execution, our code could in principle be run on actual quantum hardware by simply changing the definition of the device object (provided that the gate set used in the ansatz is supported by the device, as is the case here for IonQ; for Rigetti we need to apply one more extra trick as shown below).
Background: Hybrid Quantum Algorithms
Quantum computers hold the promise to outperform even the most-powerful classical computers on a range of computational problems in (for example) optimization, chemistry, material science and cryptography. The canonical set of quantum algorithms (such as Shor's or Grover's quantum algorithms), however, comes with hardware requirements (such as a large number of quantum gates) that are currently not available with state-of-the-art technology. Specifically, these algorithms are typically believed to be feasible only with fault-tolerance as provided by quantum error correction. In the current noisy intermediate-scale (NISQ) era, near-term quantum computers do not have a large enough number of physical qubits for the implementation of error correction protocols, making this canonical set of quantum algorithms unsuitable for near-term devices. Against this background, the near-term focus has widely shifted to the class of hybrid quantum algorithms that do not require quantum error correction. In these hybrid quantum algorithms, the noisy near-term quantum computers are used as co-processors only, within a larger classical optimization loop, as sketched in the schematic figure below. Here, the undesired effects of noise are suppressed by deliberately limiting the quantum circuits on the quantum processing unit (QPU) to short bursts of the calculation, and the need for long coherence times (as required for the standard set of quantum algorithms) is traded for a classical overhead due to (possibly many) measurement repetitions and (essentially error-free) classical processing.