Dynamic-ADAPT-QAOA: An algorithm with shallow and noise-resilient circuits

Abstract

The quantum approximate optimization algorithm (QAOA) is an appealing proposal to solve NP problems on noisy intermediate-scale quantum (NISQ) hardware. Making NISQ implementations of the QAOA resilient to noise requires short ansatz circuits with as few CNOT gates as possible. Here, we present Dynamic-ADAPT-QAOA. Our algorithm significantly reduces the circuit depth and the CNOT count of standard ADAPT-QAOA, a leading proposal for near-term implementations of the QAOA. Throughout our algorithm, the decision to apply CNOT-intensive operations is made dynamically, based on algorithmic benefits. Using density-matrix simulations, we benchmark the noise resilience of ADAPT-QAOA and Dynamic-ADAPT-QAOA. We compute the gate-error probability $p_{\text{gate}}^{\star }$ below which these algorithms provide, on average, more accurate solutions than the classical, polynomial-time approximation algorithm by Goemans and Williamson. For small systems with $6-10$ qubits, we show that $p_{\text{gate}}^{\star }>10^{-3}$ for Dynamic-ADAPT-QAOA. Compared to standard ADAPT-QAOA, this constitutes an order-of-magnitude improvement in noise resilience. This improvement should make Dynamic-ADAPT-QAOA viable for implementations on superconducting NISQ hardware, even in the absence of error mitigation.

arXiv comment15 pages, 9 figures

References in corpus (32)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Barren plateaus in quantum neural network training landscapes
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Adiabatic Quantum Computing
• Superconducting Qubits: Current State of Play
• Error mitigation for short-depth quantum circuits
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• An adaptive variational algorithm for exact molecular simulations on a quantum computer
• Extending the computational reach of a noisy superconducting quantum processor
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Towards Practical Quantum Variational Algorithms
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Annealing and Analog Quantum Computation
• Quantum optimization using variational algorithms on near-term quantum devices
• Efficient variational quantum simulator incorporating active error minimisation
• Practical Quantum Error Mitigation for Near-Future Applications
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• qubit-ADAPT-VQE: An adaptive algorithm for constructing hardware-efficient ansatze on a quantum processor
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• 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
• Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Optimized simulated annealing for Ising spin glasses
• Application of fermionic marginal constraints to hybrid quantum algorithms
• High-Fidelity, Frequency-Flexible Two-Qubit Fluxonium Gates with a Transmon Coupler
• Qubit-excitation-based adaptive variational quantum eigensolver
• ADAPT-VQE is insensitive to rough parameter landscapes and barren plateaus
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Quantifying the effect of gate errors on variational quantum eigensolvers for quantum chemistry

Cited by in corpus (4)

• State preparation of lattice field theories using quantum optimal control
• Minimal evolution times for fast, pulse-based state preparation in silicon spin qubits
• Shot-Efficient ADAPT-VQE via Reused Pauli Measurements and Variance-Based Shot Allocation
• Qubit-efficient quantum combinatorial optimization solver