Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers.

References in corpus (1)

• Quantum computing and the entanglement frontier

Cited by in corpus (43)

• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Warm-starting quantum optimization
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Variational Quantum Linear Solver
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Parameter Concentration in Quantum Approximate Optimization
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• Implementation of quantum imaginary-time evolution method on NISQ devices: Nonlocal approximation
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Empirical performance bounds for quantum approximate optimization
• Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA
• Training Optimization for Gate-Model Quantum Neural Networks
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Evaluation of QAOA based on the approximation ratio of individual samples
• GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
• Genetic optimization of quantum annealing
• Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits
• Comparison of QAOA with Quantum and Simulated Annealing
• Quantum State Optimization and Computational Pathway Evaluation for Gate-Model Quantum Computers
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
• Nonlinear dynamics and quantum chaos of a family of kicked $p$-spin models
• Analytical Framework for Quantum Alternating Operator Ansätze
• Approaches to Constrained Quantum Approximate Optimization
• Error mitigation with Clifford quantum-circuit data
• Quantum Error Mitigation Relying on Permutation Filtering
• Knapsack Problem variants of QAOA for battery revenue optimisation
• FLIP: A flexible initializer for arbitrarily-sized parametrized quantum circuits
• Power-optimal, stabilized entangling gate between trapped-ion qubits
• Reinforcement-Learning-Based Variational Quantum Circuits Optimization for Combinatorial Problems
• Forbidden subspaces for level-1 QAOA and IQP circuits
• EQC : Ensembled Quantum Computing for Variational Quantum Algorithms
• A quantum algorithm to count weighted ground states of classical spin Hamiltonians
• Lower Bounds on Circuit Depth of the Quantum Approximate Optimization Algorithm
• Accelerating variational quantum algorithms with multiple quantum processors
• The deep learning and statistical physics applications to the problems of combinatorial optimization
• Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles
• QPack: Quantum Approximate Optimization Algorithms as universal benchmark for quantum computers
• Depth Optimized Ansatz Circuit in QAOA for Max-Cut