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

High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices

Open access
Pelofske, Elijah, Bärtschi, Andreas, Golden, John, Eidenbenz, Stephan·2023·2023 IEEE International Conference on Quantum Computing and Engineering (QCE)
DOI 10.1109/qce57702.2023.00064
Open this paper in CoChat — free accountOpen PDF

Abstract

The Quantum Alternating Operator Ansatz (QAOA) is a hybrid classical-quantum algorithm that aims to sample the optimal solution(s) of discrete combinatorial optimization problems. We present optimized QAOA circuit constructions for sampling MAX$k$-SAT problems, specifically for$k=3$and$k=4$. The novel 4-SAT QAOA circuit construction we present uses measurement based uncomputation, followed by classical feed forward conditional operations. The QAOA circuit parameters for 3-SAT are optimized via exact classical (noise-free) simulation, using HPC resources to simulate up to 20 rounds on 10 qubits. In order to explore the limits of current NISQ devices we execute these optimized QAOA circuits for random 3-SAT test instances with clause-to-variable ratio 4 on four trapped ion quantum computers: Quantinuum H1-1 (20 qubits), IonQ Harmony (11 qubits), IonQ Aria 1 (25 qubits), and IonQ Forte (30 qubits). The QAOA circuits that are executed include$n=10$up to$p=20$, and$n=22$for$p=1$and$p=2$. The high round circuits use upwards of 9,000 individual gate instructions, making these some of the largest QAOA circuits executed on NISQ devices. Our main finding is that current NISQ devices perform best at low round counts (i.e.,$p=1, \ldots, 5$) and then – as expected due to noise – gradually start returning satisfiability truth assignments that are no better than randomly picked solutions as the number of QAOA rounds are further increased.

AI snapshot

Written from the paper’s full text.

TL;DR

The paper presents optimized QAOA circuit constructions for MAX k-SAT and benchmarks high-round QAOA for random 3-SAT on four trapped-ion NISQ devices. It finds that current NISQ performance peaks at low round counts and then degrades toward random sampling as rounds increase.

Key findings

  • QAOA circuits for random 3-SAT with clause-to-variable ratio 4 were executed on Quantinuum H1-1 (20 qubits), IonQ Harmony (11 qubits), IonQ Aria 1 (25 qubits), and IonQ Forte (30 qubits); circuits included n = 10 up to p = 20 and n = 22 for p = 1 and p = 2, with high-round circuits using upwards of 9,000 individual gate instructions.
  • The main finding is that NISQ devices perform best at low round counts (p = 1, …, 5) and then gradually return satisfiability assignments no better than randomly picked solutions as rounds increase. The paper reports p_max = 5, 4, 2 and p_noise = 6, 7, 6 for n = 6, 8, 10, respectively.
  • Quantinuum H1-1 was relatively stable at p = 1, 2, 3, 4 for n = 6, 8, 10; IonQ Harmony had lower mean approximation ratios, IonQ Aria performed similarly to Harmony, and IonQ Forte at low rounds was comparable to H1-1. For H1-1, a constant separation between ideal and NISQ approximation ratios was observed for p = 1 and p = 2 as n increased.
  • The 3-SAT phase separator uses 5 two-qubit gates per clause; the 4-SAT construction uses measurement-based uncomputation, k − 3 ancilla qubits, and 4k − 8 two-qubit gates for k > 3, giving 20 · n · p two-qubit gates for a p-round 3-SAT QAOA circuit at clause density 4. The 4-SAT circuits were not executed because they were out of reach of state-of-the-art hardware.

Methods

  • Optimized QAOA circuits were constructed for MAX 3-SAT and 4-SAT, targeting all-to-all connectivity and native Rzz two-qubit gates. For 3-SAT, angles were learned via exact, noise-free classical simulation using HPC resources, combining basin-hopping with local gradient descent and 10 basin-hopping iterations up to p = 20.
  • The sampled problems were random MAX 3-SAT instances with clause density 4. Experiments ran on four trapped-ion quantum computers between April 2023 and June 2023. Most parameter combinations used at least 40 shots; IonQ Forte used 2500 shots, and 140 shots were used for n = 6, 8, 10 at p = 1, 2, 3, 4, 5 (and n = 8 at p = 6, 7, 8) on IonQ Harmony, Quantinuum H1-1, and IonQ Aria. Random baselines used 100,000 uniform random variable assignments.
  • Analysis compared mean approximation ratios as a function of rounds p and problem size n, with error bars defined as the 40th and 60th percentiles of sampled approximation ratio distributions, against ideal simulation and random sampling.

Limitations

  • The paper states that angle finding was offloaded to HPC simulations, so the study does not determine the learnability of high-round QAOA angles on noisy hardware; shot noise is present; IonQ Aria and IonQ Forte data are incomplete due to a backend error preventing extremely high gate count circuits; the n = 20, p = 10 datapoint is missing because classical angle finding was too time intensive; and the 4-SAT circuits were not executed because they are out of reach of current hardware.
  • The paper states that future work should include improved angle-finding strategies, significantly higher shot counts, other trapped-ion devices, and unexplored QAOA mixers and state preparation algorithms.
  • Evident from the text: most hardware runs used only 40 shots per parameter combination, limiting statistical resolution, and the results are specific to random 3-SAT instances at clause density 4 on four trapped-ion devices.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1109/qce57702.2023.00064

Cites

Statistics

Nothing to recompute.

Claims the paper makes

0 of 20 cited sources checked · 0 supported · 0 flagged

  • Findingreasoning

    A p-round QAOA circuit for a 3-SAT problem on n qubits with clause density 4 requires a total of 20·n·p two-qubit gates.

    “Assuming a clause density of 4 for 3-SAT (justified later), we get a total of 20 • n • p two-qubit gates for a p-round QAOA circuit for a 3-SAT problem on n qubits, see Figures 5 and 6.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The hardware has all-to-all connectivity and native parameterizable Rzz(2γ)=e^{-iγZ⊗Z} two-qubit gates.
  • Findingnone given

    For any k-SAT clause with k > 3, the construction requires k−3 ancilla qubits and 4k−8 two-qubit gates.

    “Overall we need k -3 ancilla qubits and 4k -8 two-qubit gates for any k-SAT clause with k > 3 and 5 two-qubit gates per clause for 3-SAT.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The hardware has all-to-all connectivity and native parameterizable Rzz(2γ)=e^{-iγZ⊗Z} two-qubit gates.
  • Findingnone given

    A 3-SAT clause requires 5 two-qubit gates.

    “Overall we need k -3 ancilla qubits and 4k -8 two-qubit gates for any k-SAT clause with k > 3 and 5 two-qubit gates per clause for 3-SAT.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The hardware has all-to-all connectivity and native parameterizable Rzz(2γ)=e^{-iγZ⊗Z} two-qubit gates.
  • Findingnone given

    The 4-SAT implementation requires more gate operations and gate depth per round than the 3-SAT implementation.

    “The 4-SAT implementation requires even more gate operations and gate depth per round compared to 3-SAT, and puts it well out of reach of the state-of-theart quantum computers at this moment.”
    Quote in the paperSubstantial claim
  • Findingown data

    For a fixed p, as n increases, the gate depth does not substantially increase for larger n but oscillates within a few percentage points around an average.

    “Interestingly, Figure 7 shows that as n increases for a fixed p, the gate depth does not substantially increase for larger n, but rather seems oscillate within a few percentage points around an average.”
    Quote in the paperNot a substantial claim
  • May combine two claims. 8
  • Classified as probably not a substantial claim. 20
  • The quote only partly states this claim. 1

  • May combine two claims.

    Findingown data

    Current NISQ devices perform best at low QAOA round counts (p = 1,...,5) and then, as the number of rounds is further increased, gradually return satisfiability truth assignments that are no better than randomly picked solutions.

    “Our main finding is that current NISQ devices perform best at low round counts (i.e., p = 1, . . ., 5) and then -as expected due to noise -gradually start returning satisfiability truth assignments that are no better than randomly picked solutions as the number of QAOA rounds are further increased.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Good QAOA angles, though not necessarily optimal, can be learned efficiently for each round p.

  • May combine two claims.

    Findingown data

    The high-round QAOA circuits executed use upwards of 9,000 individual gate instructions, making them some of the largest QAOA circuits executed on NISQ devices.

    “The high round circuits use upwards of 9,000 individual gate instructions, making these some of the largest QAOA circuits executed on NISQ devices.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data

    For Quantinuum H1-1, rounds p=1,2,3,4 for all three 3-SAT problem instances are relatively stable in mean approximation ratios, not immediately decreasing but also not increasing substantially as expected for ideal QAOA.

    “Notably, rounds p = 1, 2, 3, 4 for all three 3-SAT problem instances on Quantinuum H1-1 are relatively stable in their mean approximation ratios, not immediately decreasing, but also not increasing substantially as is expected for the ideal QAOA computation.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Reasonably good angles can be efficiently computed.

  • Probably not a substantial claim: may not pass S4 (based).

    Findingnone given

    Each additional QAOA round significantly adds to the total gate count.

    “Because each additional round significantly adds to the total gate count”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim.

    Findingnone given

    The 4-SAT implementation uses mid-circuit measurement based AND uncomputation with mid-circuit qubit resets to re-use ancilla qubits.

    “The 4-SAT implementation makes use of mid-circuit measurement based AND uncomputation with mid circuit qubit resets in order to re-use ancilla qubits for the computation.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Findingnone given

    The samples from IonQ Aria in Figure 9 are comparable to IonQ Harmony.

    “The samples from IonQ Aria in Figure 9 are comparable to IonQ Harmony.”
    Quote in the paperNot a substantial claim
    • The authors state this as an assumption: Reasonably good angles can be efficiently computed.

  • Classified as probably not a substantial claim.

    Findingnone given

    Measurement-based uncomputation amounts to 1 CZ gate per ancilla.

    “Measurement-based uncomputation amounts to 1 CZ gate per ancilla (which as an added benefit also allows us to move the last CNOT of our base case into a classically controlled single-qubit gate).”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Findingnone given

    The accumulation of errors per round has a clear impact (performance degradation) on the actual execution of the algorithm even at low rounds.

    “Examining the behavior of the solution quality at lower rounds is important because the accumulation of errors per round has a clear impact (performance degradation) on the actual execution of the algorithm of the algorithm even at low rounds.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Max k-SAT is NP-hard for k ≥ 2.

    “Max k-SAT is N P -hard for k ≥ 2, and no classical polynomialtime approximation algorithm can guarantee to find a solution that is within 2 k -foot_0 2 k + ϵ of the optimum [28] (for any arbitrary but fixed ϵ > 0); note that the decision version of 2-SAT can be solved classically polynomially.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [28] source

      Not checked in the free run.

  • The quote only partly states this claim.

    Interpretationcitation

    The 3-SAT phase separator decomposition is essentially optimal.

    “Since 5 two-qubit gates are necessary for 2-controlled phase shift gates [62], this decomposition is essentially optimal.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationnone given

    The circuit construction easily extends to arbitrary k-SAT clauses.

    “We note that our construction easily extends to arbitrary k-SAT clauses.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisecitation

    The scalability of real-time angle-finding for a hybrid quantum-classical feedback loop is not clear for variational quantum algorithms and is expected to be hard, especially with noise.

    “However, we note that in general the scalability of real time angle-finding for a hybrid quantum-classical feedback loop is not clear for variational quantum algorithms, and in particular is expected to be quite hard especially with the presence of noise [57], [4].”
    Quote in the paperNot a substantial claim0 of 2 sources checked
    • cites [57] source

      Not checked in the free run.

    • cites [4] source

      Not checked in the free run.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Study design and conductreasoning

    There will be shot noise present in the results because all QAOA parameter combinations are sampled using at least 40 shots on each quantum computer.

    “All QAOA parameter combinations, e.g. for each p and n, are sampled using at least 40 shots (samples) on each quantum computer.This means that there will be shot noise present in the results.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationown data

    The conjectured peak point p_max is p_max = 5, 4, 2 for n = 6, 8, 10, respectively.

    “Our conjectured peak point p max is somewhat hard to identify due to shot noise, nevertheless it would be p max = 5, 4, 2 for n = 6, 8, 10, respectively”
    Quote in the paperNot a substantial claim
    • The authors state this as an assumption: Reasonably good angles can be efficiently computed.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Study design and conductnone given

    For both Figure 8 and Figure 9, the number of shots used for IonQ Forte is 2500 for the tested QAOA parameters and problem sizes.

    “For both Figure 8 and Figure 9, the number of shots used for IonQ Forte is 2500 for the tested QAOA parameters and problem sizes.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Study design and conductnone given

    The incomplete data from IonQ Aria and IonQ Forte is in part due to a current backend error that prevents extremely high gate count circuits from being executed on those two devices.

    “Note that the incomplete data from IonQ Aria and IonQ Forte (incomplete in that there are datapoints missing that could have been executed given the device qubit count, see Table I) is in part due to a current backend error that prevents extremely high gate count circuits from being executed on those two devices.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Study design and conductown data

    140 shots were also sampled for n = 8, at p = 6, 7, 8 rounds on IonQ Harmony, Quantinuum H1-1, and IonQ Aria.

    “140 shots were also sampled for n = 8, at p = 6, 7, 8 rounds on IonQ Harmony, Quantinuum H1-1, and IonQ Aria.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Study design and conductown data

    The random sample distribution used in Figure 8 and Figure 9 are generated using 100,000 (uniform) random variable assignment vectors.

    “The random sample distribution used in Figure 8 and Figure 9 (plotted as the light grey regions and the dashed black lines) are generated using 100, 000 (uniform) random variable assignment vectors”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Study design and conductnone given

    The experiments did not use all existing trapped-ion quantum computers that are publicly accessible.

    “The experiments we present here did not use all existing trapped-ion quantum computers that are publicly accessible.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning

    These QAOA circuits have fairly constant circuit depth per round even as n increases, due to the choice of constant clause density 4.

    “This is notable because it implies that these QAOA circuits have fairly constant circuit depth per round even as we increase n; this is due to our choice of constant clause densities (in our case 4).”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Premisenone given

    Sampling tasks with QAOA are sensitive to shot noise.

    “Sampling tasks with QAOA are sensitive to shot noise”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Study design and conductown data

    The error bars are defined as the 40th and 60th percentiles of the sampled approximation ratio distributions.

    “The error bars are asymmetric, and they are defined as the 40th and 60th percentiles of the sampled approximation ratio distributions”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Study design and conductcitation

    The data generated in these experiments and the 3-SAT problem instances are available as a public dataset.

    “The data generated in these experiments and the 3-SAT problem instances are available as a public dataset [42].”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [42] source

      Not checked in the free run.

  • Classified as probably not a substantial claim. May combine two claims.

    Premisenone given

    Simulating QAOA circuits for large problem sizes and high rounds is computationally intensive and requires HPC resources.

    “For large problem sizes and high rounds, simulating the QAOA circuits is quite computationally intensive and requires HPC resources.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim.

    Premisecitation

    In general, QAOA requires high p in order to be effective.

    “particularly because in general QAOA requires high p in order to be effective [14], [13]”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites [14] Farhi, 2020, The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples, arXiv

      Not checked in the free run.

    • cites [13] Farhi, 2020, The quantum approximate optimization algorithm needs to see the whole graph: A typical case, arXiv

      Not checked in the free run.

  • Classified as probably not a substantial claim.

    Study design and conductnone given

    The angles for each round were found using HPC classical computation in order to get very good, but not necessarily optimal, angles γ and β.

    “The angles for each round were found using HPC classical computation in order to get very good, but not necessarily optimal, angles γ and β.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Study design and conductreasoning

    For the other three quantum computers the number of shots used was 40 for each problem size and parameter combination, with the exception of the n = 6, 8, 10 plots in Figure 8 where a total of 140 shots were used for p = 1, 2, 3, 4, 5.

    “For the other three quantum computers the number of shots used was 40 for each problem size and parameter combination, with the exception of the n = 6, 8, 10 plots in Figure 8 where a total of 140 shots were used for p = 1, 2, 3, 4, 5”
    Quote in the paperNot a substantial claim
27 of 27

  • The authors state this as an assumption.

    Good QAOA angles, though not necessarily optimal, can be learned efficiently for each round p.

    “This is under the assumption that good angles, but not necessarily optimal angles, can be learned efficiently for each round p; in other words the conceptual picture of NISQ QAOA in Figure 1 is not intended to capture the difficulty of the angle finding problem (especially at very high rounds).”

  • The authors state this as an assumption.

    The hardware has all-to-all connectivity and native parameterizable Rzz(2γ)=e^{-iγZ⊗Z} two-qubit gates.

    “In particular, we assume all-to-all connectivity and native parameterizable Rzz(2γ) = e -iγZ⊗Z two-qubit gates.”

  • The paper relies on this without support.

    The main cost in both execution time and source of error on NISQ devices is the number of two-qubit gates.

    “The main cost in both execution time and source of error on NISQ devices is the number of two-qubit gates, hence we aim to minimize their use per clause.”

  • The paper relies on this without support.

    Current NISQ hardware has relatively high error rates.

    “The primary challenge is managing the relatively high error rates on current hardware.”

  • The authors state this as an assumption.

    Reasonably good angles can be efficiently computed.

    “assuming reasonably good angles can be efficiently computed”
5 of 5

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?

  • The number of two-qubit gates is ≈10^3 at N = 18, putting our experiments among the largest quantum optimization demonstrations on quantum hardware to date.

    “We remark that the number of two-qubit gates is ≈103 at N = 18, putting our experiments among the largest quantum optimization demonstrations on quantum hardware to date (36–38).”

    From Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem (2024) · cites this paper as [36]

    The Discussion and Conclusion (page unavailable) describes the paper’s hardware experiments as among the largest QAOA evaluations by gate depth and gate count, and the Results include problem sizes spanning n = 18. But the paper says its circuits contain thousands of gate instructions; the passages do not establish approximately 1,000 two-qubit gates specifically at n = 18. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

  • The data generated in these experiments and the 3-SAT problem instances are available as a public dataset.

    “The data generated in these experiments and the 3-SAT problem instances are available as a public dataset [42].”

    From High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices (2023) · cites this paper as [42]

Self-check

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

Each contradiction between two passages listed here was confirmed by an independent check.

  • Figure 6 gives a different target gate set

    Minor

    The Figure 6 caption lists `rz` twice and omits `rx`, while the hardware-implementation section says the circuit is compiled to a gate set that includes `rx`.

1 of 1

The citation lists haven’t been fetched yet

References 64 · Cited by 15

Research works printed but not linked: 5

  1. Gidney, 2019, Verifying Measurement Based Uncomputation
  2. He, 2023, Alignment between initial state and mixer improves qaoa performance for constrained portfolio optimization, arXiv
  3. 2023, Qiskit: An open-source framework for quantum computing
  4. Shaydulin, 2023, Qaoa with $n\cdot p\ \geq$
  5. 10.1038/s41467-021-27045-6 · DOI · Paper page

Authors
Pelofske, E., Bärtschi, A., Golden, J., & Eidenbenz, S.
Affiliations
Los Alamos National Laboratory (US)
ORCID
Venue
2023 IEEE International Conference on Quantum Computing and Engineering (QCE)
Publisher
IEEE
Published
2023-09-17
Pages
506-517
DOI
10.1109/qce57702.2023.00064
OpenAlex
W4389162702
Semantic Scholar
9b124fd6b31fd80d0e708e2afbfa587fbe10b7ef
Cited by
15
References
64
Citations by year
2025: 2 · 2024: 10 · 2023: 3
FWCI
2.66
Type
conference paper
Language
en
Open access
Licence
Locations
  • IEEE International Conference on Quantum Computing and Engineering (QCE) (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
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 Alternating Operator Ansatz, 3-SAT, trapped-ion quantum computer, NISQ devices, combinatorial optimization

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.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-10.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-10.

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