An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer
arXiv:2005.10258
Abstract
The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves combinatorial optimization problems. While there is evidence suggesting that the fixed form of the standard QAOA ansatz is not optimal, there is no systematic approach for finding better ansätze. We address this problem by developing an iterative version of QAOA that is problem-tailored, and which can also be adapted to specific hardware constraints. We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA, while simultaneously reducing the required number of CNOT gates and optimization parameters. We provide evidence that this speedup is connected to the concept of shortcuts to adiabaticity.
arXiv comment11 pages, 7 figures; v3: additional analysis, analytical results, and simulations of larger systems
Cited by in corpus (15)
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- Quantum circuit architecture search for variational quantum algorithms
- Digitized-counterdiabatic quantum approximate optimization algorithm
- Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
- Perceval: A Software Platform for Discrete Variable Photonic Quantum Computing
- Constrained mixers for the quantum approximate optimization algorithm
- Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
- GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
- Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
- Predicting quantum dynamical cost landscapes with deep learning
- A native measurement-based QAOA algorithm, applied to the MAX K-CUT problem
- Shortcuts to Quantum Approximate Optimization Algorithm
- Calibration-Aware Transpilation for Variational Quantum Optimization
- Quantum Approximate Optimization Algorithm with Sparsified Phase Operator
- Reducing measurement costs by recycling the Hessian in adaptive variational quantum algorithms