Reachability Deficits in Quantum Approximate Optimization of Graph Problems
| Autor: | H. Philathong, V. Akshay, I. Zacharov, Jacob Biamonte |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Random graph
Quantum Physics Mathematical optimization Ideal (set theory) Physics and Astronomy (miscellaneous) Computer science Physics QC1-999 FOS: Physical sciences Atomic and Molecular Physics and Optics Development (topology) Reachability Graph (abstract data type) Performance indicator Quantum Physics (quant-ph) Quantum Realization (systems) |
| Zdroj: | Quantum, Vol 5, p 532 (2021) |
| DOI: | 10.48550/arxiv.2007.09148 |
| Popis: | The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the \emph{density} of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. Motivated by Google's recent experimental realization of QAOA, we preform a reanalysis of the reported data reproduced in an ideal noiseless setting. We found that the reported capabilities of instances addressed experimentally by Google, approach a rapid fall-off region in approximation quality experienced beyond intermediate-density. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits. Comment: (feedback welcome) 11 pages; 5 composite figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|