---
tags: QAOA, NISQ, Noise, Numerical
sort-date: 2024-03-20
description: 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.
---

Nikola Yanakiev<a href="https://orcid.org/0009-0008-1924-9005"><font color="#a6ce39"><i class='fa-brands fa-orcid'></i></font></a>,
Normann Mertig<a href="https://orcid.org/0000-0003-3025-7141"><font color="#a6ce39"><i class='fa-brands fa-orcid'></i></font></a>,
[[/index|Christopher K. Long]]<a href="https://orcid.org/0009-0001-3230-942X"><font color="#a6ce39"><i class='fa-brands fa-orcid'></i></font></a>,
and David R. M. Arvidsson-Shukur<a href="https://orcid.org/0000-0002-0185-0352"><font color="#a6ce39"><i class='fa-brands fa-orcid'></i></font></a>

Published: 20 March 2024

DOI: [10.1103/PhysRevA.109.032420](https://doi.org/10.1103/PhysRevA.109.032420)

[[PDFs/Dynamic adaptive quantum approximate optimization algorithm for shallow, noise-resilient circuits.pdf|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 $𝑝^\star_\text{gate}$ 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 $𝑝^\star_\text{gate}>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](https://doi.org/10.1103/PhysRevA.109.032420).

## BibTeX

```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*](https://arxiv.org/abs/2309.00047v1). Downloads: [[PDFs/2309.00047v1.pdf|PDF]], [[TeX_Source/2309.00047v1.tar.gz|TeX Source]]

# Analytics

- [Google Scholar](https://scholar.google.com/citations?view_op=view_citation&citation_for_view=GRSIcsEAAAAJ:zYLM7Y9cAGgC)
- [SciRate](https://scirate.com/arxiv/2309.00047)
- [INSPIRE-HEP](https://inspirehep.net/literature/2770873)
- [Semantic Scholar](https://www.semanticscholar.org/paper/Dynamic-adaptive-quantum-approximate-optimization-Yanakiev-Mertig/dfe5677ca052aa45721ffce367f63cb63a3403ec)