CoChat
Sign Up
Cited by 772Quantum Computing Algorithms and ArchitectureQuantum many-body systemsMetaheuristic Optimization Algorithms Research

From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz

Open access
Hadfield, Stuart, Wang, Zhihui, O’Gorman, Bryan, Rieffel, Eleanor G., Venturelli, Davide, Biswas, Rupak·2019·Algorithms
DOI 10.3390/a12020034
Open this paper in CoChat — free accountOpen PDF

Abstract

The next few years will be exciting as prototype universal quantum processors emerge, enabling the implementation of a wider variety of algorithms. Of particular interest are quantum heuristics, which require experimentation on quantum hardware for their evaluation and which have the potential to significantly expand the breadth of applications for which quantum computers have an established advantage. A leading candidate is Farhi et al.’s quantum approximate optimization algorithm, which alternates between applying a cost function based Hamiltonian and a mixing Hamiltonian. Here, we extend this framework to allow alternation between more general families of operators. The essence of this extension, the quantum alternating operator ansatz, is the consideration of general parameterized families of unitaries rather than only those corresponding to the time evolution under a fixed local Hamiltonian for a time specified by the parameter. This ansatz supports the representation of a larger, and potentially more useful, set of states than the original formulation, with potential long-term impact on a broad array of application areas. For cases that call for mixing only within a desired subspace, refocusing on unitaries rather than Hamiltonians enables more efficiently implementable mixers than was possible in the original framework. Such mixers are particularly useful for optimization problems with hard constraints that must always be satisfied, defining a feasible subspace, and soft constraints whose violation we wish to minimize. More efficient implementation enables earlier experimental exploration of an alternating operator approach, in the spirit of the quantum approximate optimization algorithm, to a wide variety of approximate optimization, exact optimization, and sampling problems. In addition to introducing the quantum alternating operator ansatz, we lay out design criteria for mixing operators, detail mappings for eight problems, and provide a compendium with brief descriptions of mappings for a diverse array of problems.

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

Crossref · 10.3390/a12020034

Cites

94 of 94 references verified0 citation errors · 0 not checkable

Statistics

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?

  • Ansatz adaptations can occur as a byproduct, as in the Quantum Alternating Operator Ansatz where the primary goal is to find a mixing Hamiltonian that ensures staying in the feasible subspace.

    “Besides the mentioned ansatz search, as the driving force behind ansatz adaptation, there is also the possibility of having these adaptations as a byproduct, like it happens, e.g., within the Quantum Alternating Operator Ansatz where the primary goal is to find a mixing Hamiltonian that ensures to stay in the feasible subspace [11, 58, 95, 112, 116, 117, 120, 127].”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [58]

    The Introduction and Conclusions describe designing mixing operators that keep evolution within the feasible subspace, supporting that part of the claim. But the paper presents its extension of the ansatz as an explicit aim, not a byproduct, and says its mixers need not arise from a fixed mixing Hamiltonian. The indexed passages provide section labels but no page numbers. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

  • Hadfield et al. propose the Quantum Alternating Operator Ansatz where the problem-agnostic mixing Hamiltonian of the original QAOA is replaced by a mixing Hamiltonian that enforces constraints and ensures transitions between all pairs of feasible states.

    “Hadfield et al. [58] propose the Quantum Alternating Operator Ansatz where the problem-agnostic mixing Hamiltonian of the original QAOA is replaced by a mixing Hamiltonian that enforces constraints and ensures that transitions between all pairs of feasible states are provided.”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [58]

    Split into 2 atoms — 1 confirmed, 1 partially supported, 0 disputed, 0 misattributed, 0 unverifiable. Expand the claim to see per-atom verdicts.

    Experimental — accuracy not yet measured

  • Downsides of the Quantum Alternating Operator Ansatz are the resulting deep quantum circuits and the complexity of the mixer design.

    “Downsides of the proposed approach are the resulting deep quantum circuits and the complexity of the mixer design.”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [58]

    The Conclusions (page unavailable) discuss trade-offs between mixer-design complexity, gate complexity, and QAOA circuit depth. That supports these as potential implementation challenges, but not the unqualified claim that the ansatz results in deep circuits: the paper also describes mixer constructions that reduce depth. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • The parameterized quantum circuits often utilize multi-controlled operations to encode constraints into the ansatz.

    “However, the parameterized quantum circuits often utilize multi-controlled operations to encode constraints into the ansatz, e.g., the Quantum Alternating Operator Ansatz [58].”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [58]

  • The Quantum Alternating Operator Ansatz algorithm overcomes the limitation of unconstrained algorithms by using a parameterized circuit that limits the quantum evolution to a constraint-preserving subspace.

    “The Quantum Alternating Operator Ansatz algorithm22 overcomes this limitation by using a parameterized circuit which limits the quantum evolution to a constraint-preserving subspace.”

    From Constrained quantum optimization for extractive summarization on a trapped-ion quantum computer (2022) · cites this paper as [22]

Self-check

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

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

Cites

Flagged first, then by citations

Research works printed but not linked: 4

  1. Yang, Z.C.; Rahmani, A.; Shabani, A.; Neven, H.; Chamon, C. Optimizing variational quantum algorithms using Pontryagin's minimum principle. Phys. Rev. X 2017, 7, 021027. [CrossRef] · DOI · Paper page
  2. Ho, W.W.; Hsieh, T.H. Efficient preparation of non-trivial quantum states using the quantum approximate optimization algorithm. arXiv 2019, arXiv:1803.00026. Available online: https://arxiv.org/pdf/1803.00026. pdf (accessed on 11 February 2019). · arXiv
  3. Ueda, N.; Nagao, T. NP-Completeness Results for NONOGRAM via Parsimonious Reductions. Available online: https://pdfs.semanticscholar.org/1bb2/3460c7f0462d95832bb876ec2ee0e5bc46cf.pdf (accessed on 30 August 2017).
  4. Lovász, L. Coverings and colorings of hypergraphs. In Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, USA, 5-8 March 1973; Utilitas Mathematica Publishing: Winnipeg, MB, Canada, 1973; pp. 3-12.

Cited by

Sorted by citations

Related

Authors
Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R.
Affiliations
Ames Research Center (US)
Corresponding author
Hadfield, Stuart
ORCID
Venue
Algorithms
Publisher
MDPI AG
Published
2019-02-12
Volume
12
Issue
2
Pages
34
ISSN
1999-4893 (ISSN-L)
DOI
10.3390/a12020034
OpenAlex
W2754868542
Cited by
772
References
94
Citations by year
2026: 92 · 2025: 130 · 2024: 149 · 2023: 124 · 2022: 94 · 2021: 103 · 2020: 49 · 2019: 22 · 2018: 7 · 2017: 2
FWCI
30.80
Type
journal article
Language
en
Open access
Licence
Locations
  • Algorithms (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
  • arXiv (Cornell University)
Funders
National Aeronautics and Space Administration (NNX12AK33A)
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 › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
Keywords
quantum approximate optimization algorithm, Quantum Alternating Operator Ansatz, mixing operators, hard and soft constraints, combinatorial optimization, quantum annealing, problem mapping

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