Dynamic adaptive quantum approximate optimization algorithm for shallow, noise-resilient circuits

Nikola Yanakiev, Normann Mertig, Christopher K. Long, and David R. M. Arvidsson-Shukur

Published: 20 March 2024

DOI: 10.1103/PhysRevA.109.032420

PDF Download

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 controlled-NOT (CNOT) gates as possible. Here we present the dynamic adaptive quantum approximate optimization algorithm (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 six to ten 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.

Citation

Nikola Yanakiev, Normann Mertig, Christopher K. Long, and David R. M. Arvidsson-Shukur. Dynamic adaptive quantum approximate optimization algorithm for shallow, noise-resilient circuits, Phys. Rev. A 109, 032420 (2024), DOI: 10.1103/PhysRevA.109.032420.

BibTeX

@article{PhysRevA.109.032420,
    title = {Dynamic adaptive quantum approximate optimization algorithm for shallow,   noise-resilient circuits},
    author = {Yanakiev, Nikola and Mertig, Normann and Long, Christopher K. and Arvidsson-Shukur, David R. M.},
    journal = {Phys. Rev. A},
    volume = {109},
    issue = {3},
    pages = {032420},
    numpages = {21},
    year = {2024},
    month = {Mar},
    publisher = {American Physical Society},
    doi = {10.1103/PhysRevA.109.032420},
    url = {https://link.aps.org/doi/10.1103/PhysRevA.109.032420}
}

Previous version

• Thu, 31 Aug 2023 18:00:02 UTC: https://arxiv.org/abs/2309.00047v1. Downloads: PDF, TeX Source

Analytics

• Google Scholar
• SciRate
• INSPIRE-HEP
• Semantic Scholar