Pith. sign in

REVIEW 3 major objections 3 minor 86 references

Boosting quantum annealing performance through direct polynomial unconstrained binary optimization

T0 review · 3 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For toughSAT 3-SAT instances, the minimum energy gap closes as $\Delta E = 0.306 e^{-0.086N}$ in the PUBO form versus $0.17 e^{-0.33N}$ in the QUBO reduction, implying an exponentially growing annealing speedup.

desk verdict Careful, honest numerical study with a genuine but baseline-sensitive exponential advantage claim; worth refereeing after robustness checks. read the letter →

arxiv 2412.04398 v3 pith:EDWSNZXY submitted 2024-12-05 quant-ph

Sebastian Nagies , Kevin T. Geier , Javed Akram , Dimitrios Bantounas , Michael Johanning , Philipp Hauke This is my paper · ORCID
classification quant-ph
keywords quantumannealingpolynomialunconstrainedbinaryoptimizationQUBO3-SATminimumenergygapadiabaticcomputationhigher-orderinteractionsbenchmarkgenerators
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether solving an optimization problem directly in its natural higher-order polynomial form—PUBO—rather than converting it first to the quadratic QUBO form used by most quantum annealers can speed up annealing. For the paradigmatic 3-SAT problem, it shows that the native PUBO encoding uses only $N$ qubits while the authors' slack-variable QUBO reduction needs up to about $4.24N$ auxiliary qubits. Exact diagonalization of small instances shows the mean minimum energy gap closes as $\Delta E = \epsilon e^{-\alpha N}$, with $\alpha = 0.086(4)$ for the PUBO form of toughSAT instances versus $\alpha = 0.33(2)$ for the QUBO reduction, implying an exponentially growing speedup of the adiabatic annealing time. For the harder uniquePT1 instances the exponents are nearly equal but the PUBO gap is larger, giving a constant-factor speedup. The paper argues these gains outweigh the overhead of synthesizing three-body interactions, so direct PUBO implementation is a promising route to faster annealing on both analog and digital platforms.

What carries the argument

The load-bearing object is the minimum energy gap $\Delta E = \min_s \Delta E_{10}(s)$ of the linear annealing Hamiltonian $\hat H(s) = (1-s)\hat H_{\rm drive} + s \hat H_{\rm cost}$, measured by exact diagonalization. For exponentially hard problems the gap closes as $\Delta E = \epsilon e^{-\alpha N}$, and the adiabaticity time $T \approx \hbar V/\Delta E^2$ grows as $e^{2\alpha N}$, so the fitted exponent $\alpha$ for each encoding is the figure of merit. The comparison pairs the native third-order PUBO cost Hamiltonian with a QUBO reduction built by a greedy slack-variable algorithm whose penalty terms enforce $y = x_i x_j$, with both Hamiltonians normalized to their characteristic interaction scale ($J^{(3)}$ or $J^{(2)}$). The speedup formula $T_Q/T_P = (J^{(3)}/J^{(2)})(\tilde V_Q/\tilde V_P)(\tilde\epsilon_P/\tilde\epsilon_Q)^2 e^{2(\alpha_Q - \alpha_P)N}$ then converts the measured gap exponents into an estimate of the relative annealing time.

What would settle it

Re-run the scaling analysis on the same toughSAT ensembles using the alternative QUBO encodings of Appendix B (maximum independent set and linear-inequality reductions) or with $\lambda$ tuned near its per-instance optimum, and refit $\Delta E = \epsilon e^{-\alpha N}$; if any baseline yields $\alpha_Q \le \alpha_P$ within error bars, the claimed exponential PUBO speedup is an artifact of the chosen QUBO baseline rather than a property of the encodings.

Watch

Extended reading notes

Core claim

The central discovery is that the encoding of a 3-SAT instance changes the exponent with which the annealing gap closes, not just its prefactor. For ensembles of 200 toughSAT instances, exact diagonalization yields $\Delta E = 0.306 e^{-0.086N}$ for the native three-body PUBO Hamiltonian and $\Delta E = 0.17 e^{-0.33N}$ for the same instances reduced to QUBO by introducing slack variables with penalty terms; since the adiabaticity time scales as $T \propto \Delta E^{-2}$, this translates to an exponential separation in required sweep time. For uniquePT1 instances, the exponents are close ($\alpha_P = 0.352(1)$ versus $\alpha_Q = 0.364(8)$), but the prefactor is larger for PUBO, yielding a constant-factor speedup that is estimated at about six-fold for digital annealing once the four two-qubit gates needed per three-qubit gate are counted. A further finding is that the PUBO representation exposes generator structure: uniquePT4 instances reduce to a trivial local-field Hamiltonian, while uniquePT1 instances are harder than toughSAT instances.

Load-bearing premise

The exponential speedup is computed against one specific QUBO baseline—the authors' greedy slack-variable reduction with a problem-agnostic penalty strength $\lambda = 1$—so if a different QUBO encoding or a better-tuned penalty closes the gap with an equal or smaller exponent, the claimed exponential advantage would not hold.

Editorial extensions

If this is right

  • For toughSAT-style 3-SAT, the PUBO adiabaticity time grows as $\sim 1.19^N$ against $\sim 1.94^N$ for the QUBO reduction, giving about two orders of magnitude already at $N=11$ and another order of magnitude for every $\approx 4.7$ additional variables.
  • For uniquePT1 instances, where the gap exponents are nearly equal, the larger PUBO prefactor still yields a roughly sixfold speedup on digital hardware after counting four two-qubit gates per three-qubit gate.
  • PUBO formulations avoid up to $M \approx 4.24N$ ancillary qubits near the SAT phase transition, cutting spatial resources by up to an order of magnitude for 3-SAT and for problems like hypergraph coloring, NAE-4-SAT, and TSPTW.
  • The gap-based reasoning transfers from analog annealers to Trotterized digital annealing, where circuit depth tracks the adiabaticity time.
  • Benchmarking 3-SAT generators through their PUBO gap reveals that uniquePT4 instances are trivially solvable and that toughSAT instances are easier than uniquePT1 instances, information that matters for classical benchmark design.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, the same exact-diagonalization measurement of $\alpha$ could be applied to other native-PUBO problems, such as hypergraph coloring, NAE-4-SAT, and TSPTW, to test whether the exponential gap advantage generalizes.
  • Beyond the paper, the exponential claim rests on the choice of QUBO baseline; if the MIS or linear-inequality QUBO encodings from Appendix B, or a per-instance optimized penalty strength $\lambda$, produced an exponent at or below $\alpha_P$, the claimed advantage would shrink or disappear.
  • Beyond the paper, an error-inclusive simulation of the four-CNOT three-qubit gate decomposition would show whether the ideal adiabatic speedup survives on noisy digital hardware.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. This paper argues that solving optimization problems directly in polynomial unconstrained binary optimization (PUBO) form can outperform the standard QUBO reductions used in quantum annealing. It presents qubit-count savings for several PUBO-native problems, then focuses on 3-SAT. For instances generated by toughSAT and uniquePT1, the authors compute minimum energy gaps by exact diagonalization and fit exponential scalings ΔE = ε e^{-αN}. For toughSAT they find α_P = 0.086(4) for the PUBO form versus α_Q = 0.33(2) for their slack-variable QUBO reduction, which through Eq. (8) implies an exponentially growing PUBO speedup. They also analyze the dependence of the gap on the QUBO penalty strength and on the driving strength, and give a CNOT decomposition for the three-body interaction needed for digital implementations.

Significance. If the quantitative claims hold, the paper would make a practically relevant point: direct higher-order encodings can reduce both qubit counts and estimated annealing times, and the identification of benchmark-generator hardness (including the triviality of uniquePT4) is useful for the community. The numerical work is careful in several respects: ensembles of 200 instances, reported standard errors, and explicit sensitivity analyses for the penalty parameter and driving field. The exponential-advantage conclusion, however, rests on a single QUBO baseline and on gap fits over a small range of system sizes, so the central claim needs additional support before it can be taken as established.

major comments (3)
  1. [IVB3, Fig. 3, Table I] The QUBO curves in Fig. 3 extend to N=14 (toughSAT has M≈59 clauses and uniquePT1 has M=20). The slack-variable reduction of Section IVA3 introduces an ancilla for each selected variable pair, so the QUBO Hilbert-space dimension is 2^(N+N_anc). With N_anc potentially comparable to M, this is far beyond what is normally feasible with exact diagonalization (e.g., for uniquePT1 at N=14, even N_anc≈10 gives 2^24, and N_anc≈20 gives 2^34). The manuscript does not report the actual number of ancillas per instance nor the numerical method used to obtain the QUBO minimum gaps at N=12 and N=14. Since the fitted α_Q in Table I is the central quantity behind the exponential-advantage claim, please clarify how these data were computed and give the actual Hilbert-space sizes, or restrict the scaling analysis to sizes for which exact diagonalization is verifiable.
  2. [IVB4, Eq. (14), Section VB] The claimed exponential advantage is benchmarked against a single QUBO reduction: the greedy slack-variable construction with penalty strength λ=1. Section IVB4 shows that tuning λ on a single N=6 instance improves the minimum gap by about 19%, and Section VB concedes that a better penalty heuristic could reduce the PUBO improvement. Because Eq. (8) contains the factor e^{2(α_Q−α_P)N}, a modest change in α_Q, or a different QUBO encoding such as the MIS formulation in Eq. (B1), could remove the asymptotic advantage. Please provide gap-scaling results for at least one alternative QUBO encoding, or optimize the penalty strength in a documented per-size way, and show that α_Q remains significantly larger than α_P.
  3. [IVB3, Table I] The fitted exponents rely on N≤14 and 200 realizations. The PUBO exponent for toughSAT, α_P=0.086(4), is very close to zero, and the data span a short window (N=4,6,8,10,12,14). The exponential form is therefore not strongly distinguished from alternative fits, and finite-size corrections could alter the exponent difference that drives the speedup estimate. Please add a robustness analysis: fits excluding the smallest sizes, tests of power-law or stretched-exponential forms, and a statement of systematic finite-size uncertainty. This is load-bearing because the central claim is precisely the difference between α_P and α_Q.
minor comments (3)
  1. [IIIA, Eq. (11)] The polynomial displayed in Eq. (11) appears inconsistent with the encoding in Eq. (10) and f(x)=x^3+x. For x=2x1+x2+x3/2 one obtains 10x1 and 18x1x2, not 4x1 and 6x1x2. Please verify the expansion.
  2. [VA, Section VB] The conversion from 'four two-qubit gates per three-qubit gate' to J(3)/J(2)≈1/4 is asserted without derivation. Since this ratio enters the speedup estimate in Eq. (8), a brief explanation of how gate time maps to interaction strength would improve clarity.
  3. [IVB3] The comparison of the adiabaticity-time scaling T ∝ 1.19^N with classical Unique 3-SAT solvers is suggestive, but the text should more prominently state that the adiabaticity time is an upper-bound proxy based on the minimum gap, not an actual runtime benchmark. The caveat appears later, but the sentence in Section IVB3 is easy to over-read.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the PUBO-vs-QUBO gap exponents are obtained from independent exact diagonalization, and the exponential speedup is only a stated consequence of those measured exponents.

full rationale

The paper's central quantitative claim is the difference in the exponential gap-closing exponents, alpha_P = 0.086(4) versus alpha_Q = 0.33(2) for toughSAT instances (Table I). These exponents are not defined in terms of the claimed speedup; they are fit to minimum energy gaps obtained by exact diagonalization of the annealing Hamiltonian in Eq. (4) for 200 random instances per data point. The PUBO and QUBO Hamiltonians are separately constructed (Eq. (3) and the slack-variable reduction in Section IVA3), and the speedup formula in Eq. (8) is applied after the fact. The ratio T_Q/T_P is therefore a derived consequence of measured spectra, not a fitted parameter renamed as a prediction. Self-citations in the paper (e.g., Refs. [8,9,50,59]) are background or peripheral: they provide polymer-sampling examples, trapped-ion interaction schemes, or entanglement-related discussion, and none is invoked as a uniqueness theorem or as the justification for the gap-scaling result. The paper also explicitly acknowledges the main limitation of its QUBO baseline: Section IVB4 shows that tuning the penalty strength can change the gap on a single instance, and Section VB states that "Using a better heuristic ... could possibly reduce the calculated PUBO improvement." This is an honest caveat about the representativeness of the chosen QUBO reduction, not a circular step. No equation in the paper reduces to itself by construction, and no load-bearing claim is justified solely by a self-citation. Accordingly, no circularity is found.

Assumptions & free parameters 7 free parameters · 3 assumptions · 0 invented entities

The central claim rests on fitted gap-scaling exponents (free parameters) and on two domain assumptions: polynomial V prefactor and representativeness of the chosen QUBO reduction. No new physical entities are introduced.

free parameters (7)
  • alpha_P (PUBO gap exponent) = toughSAT: 0.086(4); uniquePT1: 0.352(1)
    Fitted to the exponential decay of the mean minimum gap DeltaE = epsilon e^{-alpha N}; the difference alpha_Q - alpha_P drives the claimed exponential speedup.
  • epsilon_P (PUBO gap prefactor) = toughSAT: 0.306(8); uniquePT1: 1.72(1)
    Prefactor in the gap scaling fit; enters the speedup estimate through (epsilon_P/epsilon_Q)^2.
  • alpha_Q (QUBO gap exponent) = toughSAT: 0.33(2); uniquePT1: 0.364(8)
    Fitted exponent for the QUBO reduction baseline.
  • epsilon_Q (QUBO gap prefactor) = toughSAT: 0.17(2); uniquePT1: 0.24(1)
    Prefactor in the QUBO gap scaling fit.
  • QUBO penalty strength lambda = 1 (default); optimum near 0.64 for one N=6 instance
    Chosen by hand to enforce consistency constraints; the gap and speedup estimates depend on it.
  • Driving strength hx = hx = J (default); optimum near 1.05J for one instance
    Chosen to match the cost energy scale; affects the minimum gap and adiabaticity time.
  • Ratio V_Q/V_P = about 0.5
    Estimated from small-system numerics and used to compute the constant prefactor in the speedup estimate.
assumptions (3)
  • domain assumption The adiabatic theorem and the simplified adiabaticity condition T = hbar V / DeltaE^2 with V scaling at most polynomially in N.
    Used in Section II to convert minimum-gap scaling into annealing-time scaling; the polynomial V assumption is stated but not verified at large N.
  • ad hoc to paper The slack-variable QUBO reduction with penalty strength lambda=1 represents the QUBO formulation fairly.
    The exponential advantage is established only against this reduction; other QUBO encodings are not benchmarked.
  • domain assumption The three 3-SAT generators from Ref [16] produce representative hard instances.
    The hardness conclusions for PUBO vs QUBO are based on these generators, especially toughSAT and uniquePT1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Boosting quantum annealing performance through direct polynomial unconstrained binary optimization." pith.science (2026). https://pith.science/paper/EDWSNZXY

@misc{pith2026241204398,
  author       = {Pith},
  title        = {Pith review of: Boosting quantum annealing performance through direct polynomial unconstrained binary optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EDWSNZXY}},
  note         = {Machine review of arXiv:2412.04398}
}
read the original abstract

Quantum annealing aims at solving optimization problems of practical relevance using quantum-computing hardware. Problems of interest are typically formulated in terms of quadratic unconstrained binary optimization (QUBO) Hamiltonians. However, many optimization problems are much more naturally formulated in terms of polynomial unconstrained binary optimization (PUBO) functions of higher order. As we show with various problem examples, leveraging the PUBO formulation can bring considerable savings in terms of required number of qubits. Moreover, in numerical benchmarks for the paradigmatic 3-SAT problem, we find scenarios where the scaling of the minimum energy gap during the optimization sweep differs significantly, suggesting the possibility of an exponentially faster annealing time when using the PUBO as compared to the QUBO formulation. This advantage persists even when considering the overhead caused by the higher-order interactions necessary for PUBO cost Hamiltonians. As an interesting side effect, the analysis on minimum energy gaps of different 3-SAT instance generators reveals different degrees of hardness, which will be of interest also for classical benchmark calculations. Our findings show a promising path to improving the resource efficiency and sweeping speed of quantum annealing protocols on both analog and digital platforms, which are important prerequisites when aiming at solving larger optimization problems with relevance to industry.

Figures

Figures reproduced from arXiv: 2412.04398 by the authors.

Figure 1
Figure 1. Typical gap profiles of PUBO and QUBO formulations of randomly generated 3-SAT instances. The plots show the [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Distribution of the minimum energy gap and [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 4
Figure 4. Dependence of the minimum energy gap on the [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figures from the paper (2 more)
Figure 5
Figure 5. Figure 5: Influence of the driving strength on the minimum [PITH_FULL_IMAGE:figures/full_fig_p011_5.png]
Figure 6
Figure 6. Figure 6: (a) The three-qubit gate RZZZ (θ) = exp(−i4θsˆ z 1sˆ z 2sˆ z 3) can be decomposed into four CNOT gates plus a single-qubit rotation. (b) Each CNOT gate can be further decomposed into one RZZ gate of fixed angle and multiple single-qubit rotations. The quantum gates in …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

86 extracted references · 66 canonical work pages

  1. [1]

    3-SAT as PUBO 3-SAT can be reformulated in various ways as a PUBO or QUBO problem in order to make it suitable for quan- tum annealing. A straightforward encoding consists in a PUBO problem of degree three: each clause is cast into the form of an energy term penalizing any choice of truth values that does not satisfy the clause. For example, the clause Cm...

  2. [2]

    Thus, one needs to find an equiva- lent encoding as a QUBO problem to solve 3-SAT on such hardware

    3-SAT as QUBO via slack variables Currently available quantum annealing hardware (e.g., the D-Wave machine [43]) natively only supports two- body interactions. Thus, one needs to find an equiva- lent encoding as a QUBO problem to solve 3-SAT on such hardware. A resource-efficient way to achieve this is to start with the PUBO formulation of 3-SAT given by ...

  3. [3]

    In principle, it is desirable forJ to be as large as possible in order to speed up the absolute computing time

    Characteristic energy scales In our numerics, we express the cost HamiltonianˆHcost in units of the global energy scaleJ, which we identify with a characteristic energy of the physical device. In principle, it is desirable forJ to be as large as possible in order to speed up the absolute computing time. In practice, however,J is limited by the maximum phy...

  4. [4]

    3-SAT problem generators To generate instances of the 3-SAT problem, we adapt the three different generatorstoughSAT, uniquePT1, and 7 0 0.25 0.5 0.75 1 -1 -2 -3 (a) toughSAT: PUBO Ground State

  5. [5]

    Typical gap profiles of PUBO and QUBO formulations of randomly generated 3-SAT instances

    Excited State 0 0.25 0.5 0.75 1 □3 □2 □1 (b) uniquePT1: PUBO 0 0.25 0.5 0.75 1 -1 -2 -3 (c) uniquePT4 0 0.25 0.5 0.75 1 □5 □4 □3 □2 □1 (d) toughSAT: QUBO reduction 0 0.25 0.5 0.75 1 □4 □3 □2 □1 (e) uniquePT1: QUBO reduction toughSAT 0.178(5) 0.022(1) uniquePT1 0.217(1) 0.026(1) (f) Minimum energy gaps ∆ E/J Generator PUBO QUBO 0.0 0.2 0.4 0.6 0.8 1.0 Time...

  6. [6]

    Finding an optimal QUBO reduction for a given PUBO problem is in generalNP-hard

    PUBO-to-QUBO reduction To assess the annealing performance gains of PUBO over QUBO formulations when solving 3-SAT instances, we compare the minimum energy gap of the PUBO for- mulation with that of the equivalent QUBO reduction. Finding an optimal QUBO reduction for a given PUBO problem is in generalNP-hard. For the small system sizes considered here, we...

  7. [7]

    Gap profiles Figure 1 illustrates typical gap profiles during an an- nealing sweep for specific instances withN = 6 variables, generated by each of the three generators. The blue and yellow lines correspond, respectively, to the energies of the instantaneous ground state and first excited state during a sweep according to the annealing protocol in Eq. (4)...

    work page

  8. [8]

    Figure 2 investigates the correlations between these two quantities for10 000random instances generated via toughSAT with N = 6 and M = round(4.24N) = 25

    Absence of correlations between minimum gap and number of three-body terms One may wonder whether the minimum gap (and thus the hardness to solve the PUBO problem with quan- tum annealing) depends on the number of nonzero three- body interaction coefficients present in the cost Hamilto- nian. Figure 2 investigates the correlations between these two quanti...

    work page

Show all 86 references
  1. [9]

    Scaling of the minimum gap versus system size As explained in Section II, a key characteristics for pre- dicting the performance of a quantum annealer is how the minimum energy gap encountered during the sweep scales with the problem size. In Fig. 3, we analyze the behavior of...

  2. [10]

    In this section, we in- vestigate how varying this strength affects the minimum energy gap

    Dependence of the minimum energy gap on the QUBO penalty strength Throughout our numerical analysis above, we have fol- lowed the heuristic described in Section IVA3 to deter- mine the strength of the energy penalty terms in the QUBO reduction of a PUBO problem such that the s...

  3. [11]

    However, hx is actually a free parameter that can be tuned to optimize the annealing schedule

    Influence of the driving strength on the annealing performance So far, we have chosen the strengthhx of the driving Hamiltonian to be the same as the energy scaleJ of the cost Hamiltonian, see Section IVA1. However, hx is actually a free parameter that can be tuned to optimize...

  4. [12]

    (b) Each CNOT gate can be further decomposed into one RZZ gate of fixed angle and multiple single-qubit rotations

    can be decomposed into four CNOT gates plus a single-qubit rotation. (b) Each CNOT gate can be further decomposed into one RZZ gate of fixed angle and multiple single-qubit rotations. The quantum gates in the decompositions are defined as Rα(θ) = exp( −iθˆsα), with α ∈ {X,Y,Z}...

  5. [13]

    can be synthesized from four CNOT gates, plus a single-qubit rotation around the z-axis [see Fig. 6(a)]. Each CNOT gate can be further decomposed into CNOT1,2 = e−iπ/4 ×Ry1 ( −π 2 ) Rx1 ( −π 2 ) Rx2 ( −π 2 ) H1H2 ×Rzz (π 2 ) H1H2Ry1 (π 2 ) , (17) where we used a two-qubit cont...

  6. [14]

    G. E. Santoro, R. Martoňák, E. Tosatti, and R. Car, The- ory of quantum annealing of an Ising spin glass, Science 295, 2427 (2002)

    2002

  7. [15]

    Martoňák, G

    R. Martoňák, G. E. Santoro, and E. Tosatti, Quantum annealing of the traveling-salesman problem, Phys. Rev. E 70, 057701 (2004)

    2004

  8. [16]

    Hauke, H

    P. Hauke, H. G. Katzgraber, W. Lechner, H. Nishimori, and W. D. Oliver, Perspectives of quantum annealing: methods and implementations, Rep. Progr. Phys. 83, 054401 (2020)

    2020

  9. [17]

    Rajak, S

    A. Rajak, S. Suzuki, A. Dutta, and B. K. Chakrabarti, Quantum annealing: an overview, Philos. Trans. R. Soc. Math. Phys. Eng. Sci.381, 20210417 (2022)

    2022

  10. [18]

    Yarkoni, E

    S. Yarkoni, E. Raponi, T. Bäck, and S. Schmitt, Quan- tum annealing for industry applications: introduction and review, Rep. Progr. Phys.85, 104001 (2022)

    2022

  11. [19]

    A. D. King, A. Nocera, M. M. Rams, J. Dziarmaga, R. Wiersema, W. Bernoudy, J. Raymond, N. Kaushal, N. Heinsdorf, R. Harris, K. Boothby, F. Altomare, A. J. Berkley, M. Boschnak, K. Chern, H. Chris- tiani, S. Cibere, J. Connor, M. H. Dehn, R. Desh- pande, S. Ejtemaee, P. Farré, ...

    2024

  12. [20]

    S. J. Weinberg, F. Sanches, T. Ide, K. Kamiya, and R. Correll, Supply chain logistics with quantum and clas- sical annealing algorithms, Sci. Rep.13, 4770 (2023)

    2023

  13. [21]

    Micheletti, P

    C. Micheletti, P. Hauke, and P. Faccioli, Polymer physics by quantum computing, Phys. Rev. Lett.127, 080501 (2021)

    2021

  14. [22]

    Slongo, P

    F. Slongo, P. Hauke, P. Faccioli, and C. Micheletti, Quantum-inspired encoding enhances stochastic sam- plingofsoftmattersystems,Sci.Adv. 9,eadi0204(2023)

    2023

  15. [23]

    Outeiral, G

    C. Outeiral, G. M. Morris, J. Shi, M. Strahm, S. C. Ben- jamin, and C. M. Deane, Investigating the potential for a limited quantum speedup on protein lattice problems, New J. Phys.23, 103030 (2021)

    2021

  16. [24]

    D. A. Chermoshentsev, A. O. Malyshev, M. Esencan, E. S. Tiunov, D. Mendoza, A. Aspuru-Guzik, A. K. Fe- dorov, and A. I. Lvovsky, Polynomial unconstrained bi- nary optimisation inspired by optical simulation (2022), arXiv:2106.13167 [quant-ph]

    2022 arXiv

  17. [25]

    Schmidbauer, K

    L. Schmidbauer, K. Wintersperger, E. Lobe, and W. Mauerer, Polynomial reduction methods and their impact on QAOA circuits (2024), arXiv:2406.08889 [quant-ph]

    2024 arXiv

  18. [26]

    J. D. Biamonte, Nonperturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins, Phys. Rev. A 77, 052331 (2008)

    2008

  19. [27]

    Babbush, B

    R. Babbush, B. O’Gorman, and A. Aspuru-Guzik, Re- source efficient gadgets for compiling adiabatic quan- tum optimization problems, Ann. Phys. (Berl.)525, 877 (2013)

    2013

  20. [28]

    Stein, F

    J. Stein, F. Chamanian, M. Zorn, J. Nüßlein, S. Zielin- ski, M. Kölle, and C. Linnhoff-Popien, Evidence that PUBO outperforms QUBO when solving continuous op- timization problems with the QAOA, inProceedings of the Companion Conference on Genetic and Evolutionary Computation, ...

    2023

  21. [29]

    Hsieh, R

    C.-Y. Hsieh, R. Amador, and C.-F. Chiang, Exploration of hard to solve 3-SAT problems, Journal of Information Technology in Industry7, 23 (2021)

    2021

  22. [30]

    A. P. Punnen, ed.,The Quadratic Unconstrained Binary Optimization Problem: Theory, Algorithms, and Appli- cations, 1st ed. (Springer Cham, Switzerland, 2022)

    2022

  23. [31]

    Glover, G

    F. Glover, G. Kochenberger, R. Hennig, and Y. Du, Quantum bridge analytics I: a tutorial on formulating and using QUBO models, Ann. Oper. Res. 314, 141 (2022)

    2022

  24. [32]

    Y. Du, H. Wang, R. Hennig, A. Hulandageri, G. Kochen- berger, and F. Glover, New advances for quantum- inspired optimization, Intl. Trans. in Op. Res. 32, 6 (2025)

    2025

  25. [33]

    Jansen, M.-B

    S. Jansen, M.-B. Ruskai, and R. Seiler, Bounds for the adiabatic approximation with applications to quan- tum computation, Journal of Mathematical Physics48, 102111 (2007)

    2007

  26. [34]

    D. A. Lidar, A. T. Rezakhani, and A. Hamma, Adiabatic approximation with exponential accuracy for many-body systems and quantum computation, J. Math. Phys.50, 102106 (2009)

    2009

  27. [35]

    M. H. S. Amin, Consistency of the adiabatic theorem, Phys. Rev. Lett.102, 220401 (2009)

    2009

  28. [36]

    Cheung, P

    D. Cheung, P. Høyer, and N. Wiebe, Improved error bounds for the adiabatic approximation, J. Phys. A: Math. Theor.44, 415302 (2011)

    2011

  29. [37]

    Čepait˙ e, A

    I. Čepait˙ e, A. Polkovnikov, A. J. Daley, and C. W. Duncan, Counterdiabatic optimized local driving, PRX Quantum 4, 010312 (2023)

    2023

  30. [38]

    L. P. García-Pintos, M. Sahasrabudhe, and C. Arenz, Tighter lower bounds on quantum annealing times (2024), arXiv:2410.14779 [quant-ph]. 17

    2024 arXiv

  31. [39]

    Bottarelli, M

    A. Bottarelli, M. G. de Andoin, P. Chandarana, K. Paul, X. Chen, M. Sanz, and P. Hauke, Symmetry-enhanced counterdiabatic quantum algorithm for qudits (2024), arXiv:2410.06710 [quant-ph]

    2024

  32. [40]

    Altshuler, H

    B. Altshuler, H. Krovi, and J. Roland, Anderson local- ization makes adiabatic quantum optimization fail, Proc. Natl. Acad. Sci.107, 12446 (2010)

    2010

  33. [41]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann, A quan- tum approximate optimization algorithm (2014), arXiv:1411.4028 [quant-ph]

    2014 arXiv

  34. [42]

    S. H. Sack and M. Serbyn, Quantum annealing initializa- tionofthequantumapproximateoptimizationalgorithm, Quantum 5, 491 (2021)

    2021

  35. [43]

    Blanes, F

    S. Blanes, F. Casas, and A. Murua, Splitting methods for differential equations, Acta Numerica33, 1–161 (2024)

    2024

  36. [44]

    Boros and P

    E. Boros and P. L. Hammer, Pseudo-boolean optimiza- tion, Discrete Appl. Math.123, 155 (2002)

    2002

  37. [45]

    Alessandroni, S

    E. Alessandroni, S. Ramos-Calderer, I. Roth, E. Traversi, and L. Aolita, Alleviating the quantum Big-M problem (2023), arXiv:2307.10379 [quant-ph]

    2023 arXiv

  38. [46]

    Aspvall, M

    B. Aspvall, M. F. Plass, and R. E. Tarjan, A linear- time algorithm for testing the truth of certain quantified boolean formulas, Inform. Process. Lett.14, 195 (1982)

    1982

  39. [47]

    S. A. Cook, The complexity of theorem-proving proce- dures, inProceedings of the Third Annual ACM Sympo- sium on Theory of Computing, STOC ’71 (Association for Computing Machinery, New York, NY, USA, 1971) p. 151–158

    1971

  40. [48]

    R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations(Springer US,

  41. [49]

    S. Aaronson, BQP and the polynomial hierarchy, inPro- ceedings of the Forty-Second ACM Symposium on The- ory of Computing, STOC ’10 (Association for Computing Machinery, New York, NY, USA, 2010) p. 141–150

    2010

  42. [50]

    B. Heim, T. F. Rønnow, S. V. Isakov, and M. Troyer, Quantum versus classical annealing of Ising spin glasses, Science 348, 215 (2015)

    2015

  43. [51]

    Albash and D

    T. Albash and D. A. Lidar, Adiabatic quantum compu- tation, Rev. Modern Phys.90, 015002 (2018)

    2018

  44. [52]

    Willsch, M

    D. Willsch, M. Willsch, C. D. Gonzalez Calaza, F. Jin, H. De Raedt, M. Svensson, and K. Michielsen, Bench- marking Advantage and D-Wave 2000Q quantum anneal- ers with exact cover problems, Quantum Inf. Process.21, 141 (2022)

    2022

  45. [53]

    Bernaschi, I

    M. Bernaschi, I. González-Adalid Pemartín, V. Martín- Mayor, and G. Parisi, The quantum transition of the two- dimensional Ising spin glass, Nature631, 749 (2024)

    2024

  46. [54]

    Mézard, G

    M. Mézard, G. Parisi, and R. Zecchina, Analytic and al- gorithmic solution of random satisfiability problems, Sci- ence 297, 812 (2002)

    2002

  47. [55]

    Žnidarič, Scaling of the running time of the quantum adiabatic algorithm for propositional satisfiability, Phys

    M. Žnidarič, Scaling of the running time of the quantum adiabatic algorithm for propositional satisfiability, Phys. Rev. A71, 062305 (2005)

    2005

  48. [56]

    D-Wave Systems,https://www.dwavesys.com/

  49. [57]

    Verma, M

    A. Verma, M. Lewis, and G. Kochenberger, Efficient QUBO transformation for higher degree pseudo boolean functions (2021), arXiv:2107.11695 [math.OC]

    2021 arXiv

  50. [58]

    T. D. Hansen, H. Kaplan, O. Zamir, and U. Zwick, Faster k-SAT algorithms using biased-PPSZ, inProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC ’19 (ACM, 2019) pp. 578–589

    2019

  51. [59]

    Bose, Exponential speed-up of quantum annealing via n-local catalysts (2024), arXiv:2409.13029 [quant-ph]

    R.Ghosh, L.A.Nutricati, N.Feinstein, P.A.Warburton, and S. Bose, Exponential speed-up of quantum annealing via n-local catalysts (2024), arXiv:2409.13029 [quant-ph]

    2024

  52. [60]

    Bermudez, D

    A. Bermudez, D. Porras, and M. A. Martin-Delgado, Competingmany-bodyinteractionsinsystemsoftrapped ions, Phys. Rev. A79, 060303 (2009)

    2009

  53. [61]

    D. Yang, G. S. Giri, M. Johanning, C. Wunderlich, P. Zoller, and P. Hauke, Analog quantum simulation of (1+1)-dimensional lattice QED with trapped ions, Phys. Rev. A94, 052321 (2016)

    2016

  54. [62]

    Andrade, Z

    B. Andrade, Z. Davoudi, T. Graß, M. Hafezi, G. Pagano, and A. Seif, Engineering an effective three-spin Hamilto- nian in trapped-ion systems for applications in quantum simulation, Quantum Sci. Technol.7, 034001 (2022)

    2022

  55. [63]

    Nagies, K

    S. Nagies, K. T. Geier, J. Akram, J. Okamoto, D. Ban- tounas, C. Wunderlich, M. Johanning, and P. Hauke, The role of higher-order terms in trapped-ion quantum com- puting with magnetic gradient induced coupling, Quan- tum Science and Technology10, 025051 (2025)

    2025

  56. [64]

    O. Katz, M. Cetina, and C. Monroe,n-body interactions between trapped ion qubits via spin-dependent squeez- ing, Phys. Rev. Lett.129, 063603 (2022)

    2022

  57. [65]

    Decker, C

    K. Decker, C. Karrasch, J. Eisert, and D. Kennes, Flo- quet engineering topological many-body localized sys- tems, Phys. Rev. Lett.124, 190601 (2020)

    2020

  58. [66]

    Chancellor, S

    N. Chancellor, S. Zohren, and P. A. Warburton, Cir- cuit design for multi-body interactions in superconduct- ing quantum annealing systems with applications to a scalable architecture, npj Quantum Information 3, 10.1038/s41534-017-0022-6 (2017)

    2017 doi

  59. [67]

    Rakyta and Z

    P. Rakyta and Z. Zimborás, Approaching the theoretical limit in quantum gate decomposition, Quantum6, 710 (2022)

    2022

  60. [68]

    Madden and A

    L. Madden and A. Simonetto, Best approximate quan- tum compiling problems, ACM Transactions on Quan- tum Computing3, 10.1145/3505181 (2022)

    2022 doi

  61. [69]

    Orús and J

    R. Orús and J. I. Latorre, Universality of entanglement and quantum-computation complexity, Phys. Rev. A69, 052308 (2004)

    2004

  62. [70]

    Lanting, A

    T. Lanting, A. J. Przybysz, A. Y. Smirnov, F. M. Spedalieri, M. H. Amin, A. J. Berkley, R. Harris, F. Al- tomare, S. Boixo, P. Bunyk, N. Dickson, C. Enderud, J. P. Hilton, E. Hoskinson, M. W. Johnson, E. Ladizin- sky, N. Ladizinsky, R. Neufeld, T. Oh, I. Perminov, C. Rich, M. ...

    2014

  63. [71]

    Hauke, L

    P. Hauke, L. Bonnes, M. Heyl, and W. Lech- ner, Probing entanglement in adiabatic quantum op- timization with trapped ions, Aip. Conf. Proc. 3, 10.3389/fphy.2015.00021 (2015)

    2015

  64. [72]

    G. C. Santra, S. S. Roy, D. J. Egger, and P. Hauke, Gen- uine multipartite entanglement in quantum optimization (2024), arXiv:2411.08119 [quant-ph]

    2024 arXiv

  65. [73]

    Lipkin, N

    H. Lipkin, N. Meshkov, and A. Glick, Validity of many- body approximation methods for a solvable model, Nu- clear Phys. B62, 188 (1965)

    1965

  66. [74]

    Meshkov, A

    N. Meshkov, A. Glick, and H. Lipkin, Validity of many- body approximation methods for a solvable model, Nu- clear Phys. B62, 199 (1965)

    1965

  67. [75]

    Glick, H

    A. Glick, H. Lipkin, and N. Meshkov, Validity of many- body approximation methods for a solvable model, Nu- clear Phys. B62, 211 (1965)

    1965

  68. [76]

    T. Jörg, F. Krzakala, J. Kurchan, A. C. Maggs, and J. Pujos, Energy gaps in quantum first-order mean- field–like transitions: The problems that quantum an- 18 nealing cannot solve, Europhys. Lett.89, 40004 (2010)

    2010

  69. [77]

    Ohzeki, Quantum Monte Carlo simulation of a par- ticular class of non-stoquastic Hamiltonians in quantum annealing, Sci

    M. Ohzeki, Quantum Monte Carlo simulation of a par- ticular class of non-stoquastic Hamiltonians in quantum annealing, Sci. Rep.7, 10.1038/srep41186 (2017)

    2017 doi

  70. [78]

    Seki and H

    Y. Seki and H. Nishimori, Quantum annealing with an- tiferromagnetic fluctuations, Phys. Rev. E 85, 051112 (2012)

    2012

  71. [79]

    G. A. Durkin, Quantum speedup at zero temperature via coherent catalysis, Phys. Rev. A99, 032315 (2019)

    2019

  72. [80]

    D. Y. Kang, T. Kelly, D. Kühn, A. Methuku, and D. Os- thus, Graph and hypergraph colouring via nibble meth- ods: A survey, in European Congress of Mathematics (EMS Press, 2023) pp. 771–823

    2023

  73. [81]

    Lucas, Ising formulations of many NP problems, Front

    A. Lucas, Ising formulations of many NP problems, Front. Physics2, 5 (2014)

    2014

  74. [82]

    Dominguez, J

    F. Dominguez, J. Unger, M. Traube, B. Mant, C. Ertler, and W. Lechner, Encoding-independent optimization problem formulation for quantum computing, Front. Quantum Sci. Technol.2, 1229471 (2023)

    2023

  75. [83]

    M. K. Bashar and N. Shukla, Designing Ising machines with higher order spin interactions and their application in solving combinatorial optimization, Sci. Rep.13, 9558 (2023)

    2023

  76. [84]

    Glos, and J

    Özlem Salehi, A. Glos, and J. A. Miszczak, Uncon- strained binary models of the travelling salesman prob- lem variants for quantum optimization, Quantum Inf. Process. 21, 67 (2022)

    2022

  77. [85]

    Choi, Adiabatic quantum algorithms for the np- complete maximum-weight independent set, exact cover and 3SAT problems (2010), arXiv:1004.2226 [quant-ph]

    V. Choi, Adiabatic quantum algorithms for the np- complete maximum-weight independent set, exact cover and 3SAT problems (2010), arXiv:1004.2226 [quant-ph]

    2010 arXiv

  78. [86]

    Herrman, L

    R. Herrman, L. Treffert, J. Ostrowski, P. C. Lotshaw, T.S.Humble,andG.Siopsis,GloballyoptimizingQAOA circuit depth for constrained optimization problems, Lect. Notes. Comput. Sc.14, 294 (2021)

    2021

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.