CoChat
Sign Up
PreprintCited by 95Quantum Computing Algorithms and ArchitectureQuantum many-body systemsQuantum Information and Cryptography

The DOI matches its DataCite record.

On the Universality of the Quantum Approximate Optimization Algorithm

Open access
Morales, Mauro E. S., Biamonte, Jacob, Zimborás, Zoltán·2019·arXiv
DOI 10.48550/arxiv.1909.03123arXiv 1909.03123
Open this paper in CoChat — free accountOpen PDF

Abstract

The quantum approximate optimization algorithm (QAOA) is considered to be one of the most promising approaches towards using near-term quantum computers for practical application. In its original form, the algorithm applies two different Hamiltonians, called the mixer and the cost Hamiltonian, in alternation with the goal being to approach the ground state of the cost Hamiltonian. Recently, it has been suggested that one might use such a set-up as a parametric quantum circuit with possibly some other goal than reaching ground states. From this perspective, a recent work [S. Lloyd, arXiv:1812.11075] argued that for one-dimensional local cost Hamiltonians, composed of nearest neighbor ZZ terms, this set-up is quantum computationally universal, i.e., all unitaries can be reached up to arbitrary precision. In the present paper, we give the complete proof of this statement and the precise conditions under which such a one-dimensional QAOA might be considered universal. We further generalize this type of universality for certain cost Hamiltonians with ZZ and ZZZ terms arranged according to the adjacency structure of certain graphs and hypergraphs.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1909.03123

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 42

  1. Farhi, E., Goldstone, J., Gutmann, S.: A Quantum Approximate Optimization Algorithm. arXiv e-prints arXiv:1411.4028 (2014) · arXiv
  2. Yang, Z.C., Rahmani, A., Shabani, A., Neven, H., Chamon, C.: Optimizing variational quantum algo- rithms using pontryagin's minimum principle. Phys. Rev. X 7, 021027 (2017). https://doi.org/10.1103/ PhysRevX.7.021027 · DOI · Paper page
  3. Hadfield, S., Wang, Z., O'Gorman, B., Rieffel, E.G., Venturelli, D., Biswas, R.: From the quantum approximate optimization algorithm to a quantum alternating operator Ansatz. Algorithms (2019). https://doi.org/10.3390/a12020034 · DOI · Paper page
  4. Yuezhen Niu, M., Lu, S., Chuang, I.L.: Optimizing QAOA: Success Probability and Runtime Depen- dence on Circuit Depth. arXiv e-prints arXiv:1905.12134 (2019) · arXiv
  5. Hastings, M.B.: Classical and Quantum Bounded Depth Approximation Algorithms. arXiv e-prints arXiv:1905.07047 (2019) · arXiv
  6. Farhi, E., Harrow, A.W.: Quantum Supremacy through the Quantum Approximate Optimization Algo- rithm. arXiv e-prints arXiv:1602.07674 (2016) · arXiv
  7. Yen-Yu Lin, C., Zhu, Y.: Performance of QAOA on Typical Instances of Constraint Satisfaction Prob- lems with Bounded Degree. arXiv e-prints arXiv:1601.01744 (2016) · arXiv
  8. Crooks, G.E.: Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem. arXiv e-prints arXiv:1811.08419 (2018) · arXiv
  9. Marsh, S., Wang, J.B.: A quantum walk-assisted approximate algorithm for bounded np optimisation problems. Quantum Inf. Process. 18(3), 61 (2019). https://doi.org/10.1007/s11128-019-2171-3 · DOI · Paper page
  10. Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.H., Zhou, X.Q., Love, P.J., Aspuru-Guzik, A., O'Brien, J.L.: A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5, 4213 (2014). https://doi.org/10.1038/ncomms5213 · DOI · Paper page
  11. McClean, J., Romero, J., Babbush, R., Aspuru-Guzik, A.: The theory of variational hybrid quantum- classical algorithms. New J. Phys. 18, 023023 (2016). https://doi.org/10.1088/1367-2630/18/2/023023 · DOI · Paper page
  12. Biamonte, J.: Universal Variational Quantum Computation. arXiv e-prints arXiv:1903.04500 (2019) · arXiv
  13. McClean, J.R., Boixo, S., Smelyanskiy, V.N., Babbush, R., Neven, H.: Barren plateaus in quantum neural network training landscapes. Nat. Commun. 9(1), 4812 (2018)
  14. Du, Y., Hsieh, M.H., Liu, T., Tao, D.: The Expressive Power of Parameterized Quantum Circuits. arXiv e-prints arXiv:1810.11922 (2018) · arXiv
  15. Lloyd, S.: Quantum Approximate Optimization is Computationally Universal. arXiv e-prints arXiv:1812.11075 (2018) · arXiv
  16. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2010)
  17. Jurdjevic, V., Sussmann, H.J.: Control systems on lie groups. J. Differ. Equ. 12(2), 313-329 (1972). https://doi.org/10.1016/0022-0396(72)90035-6 · DOI
  18. Zimborás, Z., Zeier, R., Schulte-Herbrüggen, T., Burgarth, D.: Symmetry criteria for quantum simu- lability of effective interactions. Phys. Rev. A 92, 042309 (2015). https://doi.org/10.1103/PhysRevA. 92.042309 · DOI
  19. Zeier, R., Schulte-Herbrüggen, T.: Symmetry principles in quantum systems theory. J. Math. Phys. 52(11), 113510 (2011). https://doi.org/10.1063/1.3657939 · DOI
  20. Dirr, G., Helmke, U.: Lie theory for quantum control. GAMM-Mitteilungen 31(1), 59-93 (2008). https://doi.org/10.1002/gamm.200890003 · DOI
  21. Zimborás, Z., Zeier, R., Keyl, M., Schulte-Herbrüggen, T.: A dynamic systems approach to fermions and their relation to spins. EPJ Quantum Technol. 1(1), 11 (2014). https://doi.org/10.1140/epjqt11 · DOI
  22. Burgarth, D., Maruyama, K., Murphy, M., Montangero, S., Calarco, T., Nori, F., Plenio, M.B.: Scalable quantum computation via local control of only two qubits. Phys. Rev. A 81, 040303(R) (2010). https:// doi.org/10.1103/PhysRevA.81.040303 · DOI
  23. Brylinski, J.-L., Brylinski, R.: Universal quantum gates. In: Chen, G., Brylinski, R. (eds.) Math- ematics of Quantum Computation, pp. 117-134. Chapman and Hall/CRC, Cambridge (2002). arXiv:quant-ph/0108062 · arXiv
  24. Vlasov, A.Y.: Clifford algebras and universal sets of quantum gates. Phys. Rev. A 63(5), 054302 (2001)
  25. Bremner, M.J., Dodd, J.L., Nielsen, M.A., Bacon, D.: Fungible dynamics: there are only two types of entangling multiple-qubit interactions. Phys. Rev. A 69, 012313 (2004). https://doi.org/10.1103/ PhysRevA.69.012313 · DOI
  26. Oszmaniec, M., Zimborás, Z.: Universal extensions of restricted classes of quantum operations. Phys. Rev. Lett. 119, 220502 (2017). https://doi.org/10.1103/PhysRevLett.119.220502 · DOI
  27. Sawicki, A., Karnas, K.: Criteria for universality of quantum gates. Phys. Rev. A 95, 062303 (2017). https://doi.org/10.1103/PhysRevA.95.062303 · DOI
  28. Burgarth, D., Bose, S., Bruder, C., Giovannetti, V.: Local controllability of quantum networks. Phys. Rev. A 79, 060305 (2009). https://doi.org/10.1103/PhysRevA.79.060305 · DOI
  29. Burgarth, D., D'Alessandro, D., Hogben, L., Severini, S., Young, M.: Zero forcing, linear and quantum controllability for systems evolving on networks. IEEE Transa. Autom. Control 58(9), 2349-2354 (2013)
  30. Wang, Z., Hadfield, S., Jiang, Z., Rieffel, E.G.: Quantum approximate optimization algorithm for maxcut: a fermionic view. Phys. Rev. A 97, 022304 (2018). https://doi.org/10.1103/PhysRevA.97. 022304 · DOI · Paper page
  31. den Nest, M.V., Dür, W., Miyake, A., Briegel, H.J.: Fundamentals of universality in one-way quantum computation. New J. Phys. 9(6), 204-204 (2007). https://doi.org/10.1088/1367-2630/9/6/204 · DOI · Paper page
  32. Ho, W.W., Hsieh, T.H.: Efficient variational simulation of non-trivial quantum states. SciPost Phys. 6, 29 (2019). https://doi.org/10.21468/SciPostPhys.6.3.029 · DOI · Paper page
  33. Ho, W.W., Jonay, C., Hsieh, T.H.: Ultrafast variational simulation of nontrivial quantum states with long-range interactions. Phys. Rev. A 99, 052332 (2019). https://doi.org/10.1103/PhysRevA. 99.052332 · DOI
  34. Hadfield, S., Wang, Z., Rieffel, E.G., O'Gorman, B., Venturelli, D., Biswas, R.: Quantum approximate optimization with hard and soft constraints. In: Proceedings of the Second International Workshop on Post Moores Era Supercomputing, PMES'17, pp. 15-21. ACM, New York, NY, USA (2017). https:// doi.org/10.1145/3149526.3149530 · DOI · Paper page
  35. Akshay, V., Philathong, H., Morales, M.E.S., Biamonte, J.: Reachability Deficits in Quantum Approx- imate Optimization. arXiv e-prints arXiv:1906.11259 (2019) · arXiv
  36. Herasymenko, Y., O'Brien, T.E.: A diagrammatic approach to variational quantum ansatz construction. arXiv e-prints arXiv:1907.08157 (2019) · arXiv
  37. Cybenko, G.: Approximation by superpositions of a sigmoidal function. Math. Control Signals Syst. 2(4), 303-314 (1989). https://doi.org/10.1007/bf02551274 · DOI · Paper page
  38. Hornik, K.: Approximation capabilities of multilayer feedforward networks. Neural Netw. 4(2), 251- 257 (1991). https://doi.org/10.1016/0893-6080(91)90009-T · DOI · Paper page
  39. Csáji, B.C.: Approximation with Artificial Neural Networks. Master's thesis, Eötvös Loránd University, Hungary (2001)
  40. Burgarth, D., Giovannetti, V., Hogben, L., Severini, S., Young, M.: Logic circuits from zero forcing. Natural Comput. 14(3), 485-490 (2014). https://doi.org/10.1007/s11047-014-9438-5 · DOI
  41. Farhi, E., Goldstone, J., Gutmann, S.: A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem. arXiv e-prints arXiv:1412.6062 (2014) · arXiv
  42. Wang, Z., Rubin, N.C., Dominy, J.M., Rieffel, E.G.: XY -mixers: analytical and numerical results for QAOA. arXiv e-prints arXiv:1904.09314 (2019) · arXiv

Cited by

Sorted by citations

Metadata

Authors
Morales, M. E. S., Biamonte, J., & Zimborás, Z.
Affiliations
  • Skolkovo Institute of Science and Technology (RU)
  • Budapest University of Technology and Economics (HU)
Corresponding author
Zimborás, Zoltán
ORCID
Venue
arXiv
Publisher
arXiv
Published
2019
Volume
19
Issue
9
ISSN
1570-0755 (ISSN-L)
DOI
10.48550/arxiv.1909.03123
arXiv
1909.03123
OpenAlex
W2971844308
Cited by
95
References
0
Citations by year
2026: 6 · 2025: 15 · 2024: 14 · 2023: 17 · 2022: 22 · 2021: 18 · 2020: 3
FWCI
5.89
Type
journal article
Language
en
Open access
Licence
Locations
  • Quantum Information Processing (publishedVersion, cc-by)
  • Repository of the Academy's Library (Library of the Hungarian Academy of Sciences) (acceptedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • UTS ePRESS (University of Technology Sydney) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • Hungarian Scientific Research Fund (K124351)
  • Nemzeti Kutatási Fejlesztési és Innovációs Hivatal (K 124176, K124351, KH129601, K124152, 2017- 1.2.1-NKP-2017-00001)
  • Wigner Fizikai Kutatóközpont, Magyar Tudományos Akadémia
  • National Research, Development and Innovation Office (2017–1.2.1-NKP-2017-00001, K124152, K124351, KH129601)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
Keywords
quantum approximate optimization algorithm, hypergraphs, near-term quantum devices

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review