Benchmarking the Quantum Approximate Optimization Algorithm
arXiv:1907.02359 · doi:10.1007/s11128-020-02692-8
Abstract
The performance of the quantum approximate optimization algorithm is evaluated by using three different measures: the probability of finding the ground state, the energy expectation value, and a ratio closely related to the approximation ratio. The set of problem instances studied consists of weighted MaxCut problems and 2-satisfiability problems. The Ising model representations of the latter possess unique ground states and highly-degenerate first excited states. The quantum approximate optimization algorithm is executed on quantum computer simulators and on the IBM Q Experience. Additionally, data obtained from the D-Wave 2000Q quantum annealer is used for comparison, and it is found that the D-Wave machine outperforms the quantum approximate optimization algorithm executed on a simulator. The overall performance of the quantum approximate optimization algorithm is found to strongly depend on the problem instance.
arXiv commentVersion after the referee process. Published in Quantum Information Processing
References in corpus (15)
- Quantum Computing in the NISQ era and beyond
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- A variational eigenvalue solver on a quantum processor
- Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
- Quantum Annealing in the Transverse Ising Model
- Adiabatic Quantum Computing
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
- Robustness of adiabatic quantum computation
- Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
- QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
- Architectural considerations in the design of a superconducting quantum annealing processor
- Massively parallel quantum computer simulator, eleven years later
- Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
Cited by in corpus (67)
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- Warm-starting quantum optimization
- Challenges and Opportunities in Quantum Optimization
- Quantum annealing initialization of the quantum approximate optimization algorithm
- Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
- Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems
- Digitized-counterdiabatic quantum approximate optimization algorithm
- MAXCUT QAOA performance guarantees for p >1
- From pulses to circuits and back again: A quantum optimal control perspective on variational quantum algorithms
- Classical variational simulation of the Quantum Approximate Optimization Algorithm
- Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
- Quantum Computing: Towards Industry Reference Problems
- QUARK: A Framework for Quantum Computing Application Benchmarking
- Quantum variational optimization: The role of entanglement and problem hardness
- Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
- Progress toward favorable landscapes in quantum combinatorial optimization
- Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
- Qubit-efficient encoding schemes for binary optimisation problems
- Challenges of variational quantum optimization with measurement shot noise
- Application-Motivated, Holistic Benchmarking of a Full Quantum Computing Stack
- GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
- Lyapunov control-inspired strategies for quantum combinatorial optimization
- An entanglement perspective on the quantum approximate optimization algorithm
- Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
- Quantum approximate optimization algorithm for qudit systems
- Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
- Applying quantum approximate optimization to the heterogeneous vehicle routing problem
- Reachability Deficits in Quantum Approximate Optimization of Graph Problems
- Mean-Field Approximate Optimization Algorithm
- PCA and t-SNE analysis in the study of QAOA entangled and non-entangled mixing operators
- Quantum Dropout: On and Over the Hardness of Quantum Approximate Optimization Algorithm
- Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
- Parity Quantum Optimization: Benchmarks
- Garden optimization problems for benchmarking quantum annealers
- Improved variational quantum eigensolver via quasi-dynamical evolution
- Multiobjective variational quantum optimization for constrained problems: an application to Cash Management
- Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems
- Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
- BILP-Q: Quantum Coalition Structure Generation
- Continuous-variable quantum approximate optimization on a programmable photonic quantum processor
- Quantum annealing for hard 2-SAT problems : Distribution and scaling of minimum energy gap and success probability
- Trainability Barriers in Low-Depth QAOA Landscapes
- NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization
- Gate Operations for Superconducting Qubits and Non-Markovianity
- Computing Graph Edit Distance with Algorithms on Quantum Devices
- Forbidden subspaces for level-1 QAOA and IQP circuits
- On Optimizing Hyperparameters for Quantum Neural Networks
- Unraveling Reverse Annealing: A Study of D-Wave Quantum Annealers
- Single entanglement connection architecture between multi-layer bipartite Hardware Efficient Ansatz
- Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments
- Adiabatic Bottlenecks in Quantum Annealing and Nonequilibrium Dynamics of Paramagnons
- Quantum annealer accelerates the variational quantum eigensolver in a triple-hybrid algorithm
- Tabu-driven Quantum Neighborhood Samplers
- Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
- Deep-Circuit QAOA
- Universal Quantum Computer Simulation of 50 Qubits on Europe`s First Exascale Supercomputer Harnessing Its Heterogeneous CPU-GPU Architecture
- Constraint-Aware Quantum Optimization via Hamming Weight Operators
- Optimal solutions to quantum annealing using two independent control functions
- Computational Phase Transitions: Benchmarking Ising Machines and Quantum Optimisers
- Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
- Symmetry-based quantum algorithms for open-shop scheduling with hard constraints
- Entanglement dynamics and performance of two-qubit gates for superconducting qubits under non-Markovian effects
- Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA
- A combined quantum-classical method applied to material design: optimization and discovery of photochromic materials for photopharmacology applications
- Statistical quality assessment of Ising-based annealer outputs
- Quantum combinatorial optimization beyond the variational paradigm: simple schedules for hard problems