Resource-Efficient Quantum Optimization via Higher-Order Encoding

Dieter Jaksch; Frederik Koch; Joseph Doetsch; Rick Mukherjee; Shahram Panahiyan

REVIEW 3 major objections 5 minor 80 references

Resource-Efficient Quantum Optimization via Higher-Order Encoding

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

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

Pith's one-line read Higher-order binary encodings of optimization problems use logarithmically fewer qubits than QUBO one-hot encodings, and after compilation to one- and two-qubit gates cut CNOT counts by at least 89.6% across three problem classes.

desk verdict Real per-layer resource savings and a genuinely useful HUBO construction pipeline; the headline '89.6% CNOT reduction' rests on best-of-100 QAOA minima and per-encoding lambda tuning, so treat it as optimistic rather than established. read the letter →

arxiv 2511.17545 v2 pith:TPB2ACKN submitted 2025-11-10 quant-ph

Frederik Koch , Shahram Panahiyan , Rick Mukherjee , Joseph Doetsch , Dieter Jaksch This is my paper · ORCID

classification quant-ph

keywords higher-orderunconstrainedbinaryoptimizationQUBOQAOAcombinatorialone-hotencodinggateassignmentproblemmaxk-colorablesubgraphintegerprogramming

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

The paper shows that representing each m-valued variable of a combinatorial optimization problem by ⌈log2 m⌉ qubits (a HUBO encoding) instead of m one-hot qubits (QUBO) removes the need for one-hot penalty terms and reduces circuit size. It provides a systematic Walsh-Hadamard construction of the higher-order Hamiltonian coefficients and a Gray-code circuit that implements all terms with only single- and two-qubit gates. In QAOA benchmarks on Gate Assignment, Maximum k-Colorable Subgraph, and Integer Programming problems, the authors find qubit counts that grow logarithmically instead of linearly in the number of values, and total CNOT counts to reach fixed solution thresholds that are lower by 89.6–100% than QUBO. If this holds, HUBO is a drop-in, resource-efficient replacement for QUBO in near-term quantum optimization.

What carries the argument

The central object is the value-index bit encoding: each variable i is stored in d = ⌈log2 m⌉ qubits and the projector |v⟩⟨v|_i is expanded as a sum over products of Pauli-Z operators, producing a HUBO Hamiltonian whose interacting terms act on up to 2d qubits. Two constructions carry the argument: the Walsh-Hadamard transform that converts the classical cost coefficients c1(i,v) and c2(i,j,v,w) into the HUBO coefficients J_i,S and J_{ij,S1,S2} in O(n^2 m^6) time for quadratic objectives, and the Gray-code hypercube traversal that compiles all higher-order Z-products of a d-qubit block into a circuit with one CNOT and one RZ per term — the minimal count, replacing the naive 2^d(d−2)+2 CNOTs

What would settle it

Recompute the minimum total CNOTs needed to reach the target approximation ratio using the median (not the best) of the 100 QAOA runs for both encodings, with identical penalty multipliers and identical parameter-optimization budgets; if the median saving for any tested instance falls below 89.6%, the headline savings are an artifact of selection rather than of the encoding.

Watch

Extended reading notes

Core claim

For any COP with n variables each taking one of m values, the authors construct a HUBO Hamiltonian whose ground state encodes the optimal solution, using d = ⌈log2 m⌉ qubits per variable. The bitstrings of the d qubits are read as value indices, so the one-hot penalty needed in QUBO disappears. Coefficients of the Pauli-Z expansion are obtained from the classical cost coefficients by a Walsh-Hadamard transform, with polynomial numerical complexity. The cost unitary for QAOA is built from the commuting diagonal terms using a Gray-code parity scheme, so a term acting on t qubits costs one CNOT and one RZ gate after the first, and all terms of a 2d-qubit block are implemented with 2^(2d) − 2 CN

Load-bearing premise

The 89.6–100% total-CNOT savings to reach solution thresholds come from picking the best of 100 independent QAOA runs for each encoding, after tuning penalty multipliers separately for each encoding; if that best-of-100 selection or the penalty tuning favors HUBO, the saving is larger than a fair per-instance comparison would give.

Editorial extensions

If this is right

Exponential qubit reduction: n·m qubits become n·⌈log2 m⌉, so problems with many values per variable (e.g., gate assignment with many gates) become representable.
Deterministic per-layer gate savings: compiled per-layer CNOT counts for the tested instances are 68 vs 140 (GAP), 90 vs 132 (MkCS), and 38 vs 120 (IP) for HUBO versus QUBO.
To reach fixed approximation-ratio thresholds (0.2–0.6), HUBO-QAOA uses 89.6–100% fewer CNOTs and 86.1–100% fewer RZ gates than QUBO-QAOA across all benchmarked sizes.
At equal QAOA depth HUBO produces better average objective values in all three problems, e.g., 12.1 vs 15.8 minutes walking time for the GAP instance.
The full cost unitary is implemented with only single- and two-qubit gates, so the method is directly compatible with current device constraints despite higher-order Hamiltonian terms.

Reading between the lines

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

The exponential qubit saving is structural and does not depend on QAOA; it should transfer to any algorithm that needs to encode m-valued variables, including quantum annealing or imaginary-time evolution.
The ≥89.6% CNOT figure combines a deterministic per-layer advantage with an empirical convergence-rate comparison; under a different optimizer or with fixed instead of per-encoding-tuned penalty weights, the total-gate saving could be smaller, though still nonzero.
A natural stress test is to apply the same construction to problems with inequality constraints involving more than two variables, where QUBO typically requires extra slack variables; HUBO's direct projector penalties may avoid that overhead entirely.
The Gray-code compilation implies a general rule: any set of Z-terms sharing the same qubit block can be implemented with one CNOT per new subset, so the reported per-layer counts are lower bounds for any Hamiltonian with similar locality.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Two things you should know. First, the deterministic part of this paper is solid: mapping n variables with m values to n·ceil(log2 m) qubits instead of n·m, and compiling each QAOA layer to explicit CNOT counts, gives real per-layer savings (roughly 32–68% on the three example instances). The coefficient construction via Walsh–Hadamard transform is clean, the O(n^2 m^2) per-layer gate scaling is derived, and the Gray-code circuit optimization is a sensible, if known, tool. They ship PyHUBO, which is a useful artifact. Second, the headline 'decreases total CNOT gate counts by at least 89.6%' does not come from those compiled circuits. It comes from the number of QAOA layers needed to reach a target approximation ratio, and Appendix D states they ran each encoding 100 times and picked the run with the lowest layer requirement. Minima over 100 runs can systematically favor whichever encoding has smaller run-to-run variance, and the Lagrange multipliers are tuned separately for each encoding. The stress-test note lands: the distribution of layer counts is never reported, so the 89.6% number is not robust. My guess is HUBO still genuinely needs fewer layers here—the fixed-depth averages in Figures 7, 10, and 13 look better—but the magnitude of the claimed savings is uncertain.

Other soft spots, in proportion. The benchmarks are tiny: n up to 5, m fixed at 4 (a power of two), so non-power-of-two m is never tested and the scaling plots have five points without error bars on the threshold measurements. The asymptotic gate scaling is the same class for both encodings, O(n^2 m^2); the advantage is constant-factor plus the exponential qubit reduction. The abstract could leave the impression that the gate-complexity class improves, which it does not. None of these are fatal, but they should be fixed before the 'practical alternative' framing is accepted at face value.

The authors are unusually transparent about their selection protocol, and the deterministic math is correct. This deserves peer review. The right referee will push for average/percentile layer counts, a pre-registered or at least fixed lambda selection, tests with m not equal to a power of two, and a careful separation of per-layer circuit facts from empirical QAOA performance. With those revisions this becomes a useful reference for anyone working on encoding comparisons in quantum optimization.

Referee Report

3 major / 5 minor

Summary. The paper proposes a systematic HUBO encoding for combinatorial optimization problems with n variables, each taking m values, using d = ceil(log2 m) qubits per variable instead of the n*m qubits of a one-hot QUBO encoding. The authors derive the Pauli expansion of the cost Hamiltonian via a Walsh-Hadamard transform (Eqs. 15-23), implement the diagonal cost unitary with Gray-code parity circuits using only CNOT and RZ gates, and prove O(n^2 m^2) per-layer scaling. They benchmark QUBO-QAOA and HUBO-QAOA on small Gate Assignment, Maximum k-Colorable Subgraph, and Integer Programming instances, reporting qubit counts, per-layer gate counts, and total gates needed to reach target approximation ratios. The central advertised result is that HUBO reduces qubit requirements and cuts total CNOT counts by at least 89.6% after compilation for all tested instances. An open-source package, PyHUBO, is released.

Significance. If the empirical claims hold, the paper offers a practical and broadly applicable alternative to QUBO for QAOA-style optimization: the qubit reduction from n*m to n*log m is clean and deterministic, the Pauli/Hadamard construction is parameter-free, and the Gray-code circuit synthesis is explicit and machine-checkable in principle. The per-layer deterministic gate counts in Table 2 show real, if modest, HUBO advantages (32-68% CNOT reduction for the three concrete instances), and the asymptotic scaling in Appendix C is useful. The 89.6-100% CNOT savings, however, are not a property of the encodings alone: they depend on empirical QAOA convergence, on best-of-100 run selection, and on per-encoding penalty tuning. Since that headline number is the paper's main selling point, its evidential basis needs to be substantially strengthened before the central claim can be accepted.

major comments (3)

[Appendix D / Figs. 8, 11, 14] The headline 'at least 89.6% CNOT reduction after compilation' is not supported by the deterministic per-layer counts in Table 2, which show only 32-68% reductions. The larger figure comes from the number of layers needed to reach target thresholds, and the protocol in Appendix D states that for these benchmarks the authors 'ran the QAOA algorithm 100 times and picked the QAOA experiment with the lowest layer requirements.' The distribution of required layers is not reported, and the Lagrange multipliers lambda are tuned iteratively per encoding without a fixed protocol. If the two encodings have different run-to-run variance, the minimum over 100 runs can systematically favor one encoding (here HUBO) even when typical performance is similar. Please report medians/quantiles, success probabilities as a function of layers, and use a symmetric, pre-specified lambda-selection rule. Without t
[Abstract and Sec. 2] The claim that HUBO 'exponentially reduces qubit requirements' is not accurate as stated. QUBO uses n*m qubits and HUBO uses n*ceil(log2 m) qubits, so the ratio is m/ceil(log2 m), which is polynomial in m. The correct statement is that the qubit count is reduced from linear to logarithmic in m. This wording appears in the abstract and is repeated in Sec. 2 and the Conclusion; it should be corrected to avoid overstating the advantage.
[Sec. 2.3 / Fig. 14] The paper states that QUBO-QAOA was 'not computationally feasible' at the n=5, m=4 IP instance, which is only 20 qubits, while QUBO-QAOA is reportedly run on a 16-qubit reduced instance. This is surprising and unexplained: statevector simulation of 20 qubits is routine in PennyLane. If the largest IP instance is excluded for QUBO, then the percentage savings quoted for IP (94.4-100%) apply only to the smaller instances; the text should state this explicitly and justify the claimed infeasibility.

minor comments (5)

[Sec. 1.1] The sentence 'without loss of generality, we only consider linear and quadratic COPs' is not literally WLOG; higher-order objectives are simply outside the scope. Please rephrase.
[Sec. 1.2.2 / Eq. (16)] The binary-to-decimal mapping is ambiguous when values are indexed from 1 to m. Since a d-bit string decodes to 0..2^d-1, the penalty in Eq. (16) may be off by one. Please define the offset explicitly (e.g., value index v = binary + 1 or v = binary).
[Appendix A] The stated complexity O(n^2 m^6) for computing quadratic HUBO coefficients overstates the cost of the Walsh-Hadamard transform. H^{⊗d} can be applied to a vector of length 2^d in O(d 2^d) time, so the per-pair cost is O(d^2 2^{2d}) = O(m^2 log^2 m), giving O(n^2 m^2 log^2 m) overall. Please correct or clarify the complexity model.
[Appendix A, Eq. (28)] Typo: 'co + c1' should be 'c0 + c1'.
[Table 2] Please state explicitly whether the reported QUBO gate counts include the one-hot penalty terms and any constraint penalties. This is important for reproducing the per-layer comparisons.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; HUBO construction is an exact transform of the classical objective and resource counts are explicit, parameter-independent circuit counts.

full rationale

The derivation chain is self-contained. The HUBO coefficients in Eq. (23) are obtained by substituting the Pauli expansion of projectors, Eqs. (18) and (21), into the objective Hamiltonian Eq. (15); no fitted or optimized constant is inserted into this step, and the same coefficients are used to build the circuits. The qubit-count comparison (n×m vs n⌈log2 m⌉) and the per-layer CNOT/RZ counts in Table 2 follow from the explicit encodings and circuit constructions, and the asymptotic scalings in App. C are derived for both encodings from the same worst-case coefficient counts. The Gray-code circuit optimization is attributed to external results [72,74], not to a self-citation, and the only self-reference, the PyHUBO package [31], is a software artifact rather than a load-bearing premise. The concern raised by a skeptic—that the 89.6–100% savings figures rest on 'the QAOA experiment with the lowest layer requirements' (App. D) and per-encoding lambda tuning—is an evidence-quality/statistical-validity issue about the representativeness of best-of-100 selection, not a circular reduction: the resource counts are not equal by construction to a fitted parameter, and the concrete per-layer counts independently support a resource advantage. No circular step is present.

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

The central resource claims do not depend on exotic new physics; all ingredients are standard linear algebra and circuit synthesis. The main fitted ingredients are penalty multipliers, QAOA angles, and the choice of target approximation ratios. No new particles, forces, or conserved quantities are introduced.

free parameters (3)

Penalty multipliers lambda = not reported (tuned per instance)
Sec. 1.3: 'The Lagrange multipliers lambda ... are chosen iteratively before running the QAOA benchmarking. Only after identifying lambda values that ensure ... feasible solutions ... do we proceed.' The selected values are not listed, and they affect feasibility and gate counts because penalty terms add circuit terms.
QAOA variational parameters gamma, beta = not reported (optimized per instance and layer)
Sec. 1.3 uses gradient descent with Zhou initialization. The threshold-to-convergence gate counts in Figs. 8, 11, 14 depend on these optimized parameters.
Target approximation ratios for scaling benchmarks = 0.50 (GAP), 0.20 (MkCS), 0.30 (IP)
Chosen per problem class in Secs. 2.1-2.3; different thresholds change the reported gate-count savings, so they are effective free degrees of freedom in the comparison.

assumptions (4)

domain assumption Polynomial objective of a COP can be written as a sum of linear and quadratic terms (Eq. 1) without loss of generality.
The framework is derived for linear+quadratic objectives; higher-order objectives are excluded from benchmarking.
domain assumption Constraints can be enforced by adding lambda times a violation indicator to the Hamiltonian, with lambda large enough that the ground state is feasible (Eqs. 3-4).
Used to build both QUBO and HUBO Hamiltonians; in QAOA, finite lambda only approximately enforces feasibility, and the authors tune lambda empirically instead of proving a bound.
standard math Walsh-Hadamard expansion of projectors (Eq. 18) and the Gray-code parity circuit of Welch et al. [74] implement exp(i gamma J_T Z_T) using one CNOT per Gray-code edge.
Appendix A derives the expansion; Appendix B cites [74] for optimality of the Gray-code circuit. Both are standard but load-bearing for the CNOT count claims.
domain assumption Sampling 10,000 bitstrings gives an approximation ratio within 2% with 99% probability (Hoeffding), and averaging 100 independent QAOA optimizations is representative.
Appendix D. Relies on Monte Carlo sampling and ignores optimizer failure modes; the best-of-100 selection for thresholds is a further unmodeled choice.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Resource-Efficient Quantum Optimization via Higher-Order Encoding." pith.science (2026). https://pith.science/paper/TPB2ACKN

@misc{pith2026251117545,
  author       = {Pith},
  title        = {Pith review of: Resource-Efficient Quantum Optimization via Higher-Order Encoding},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TPB2ACKN}},
  note         = {Machine review of arXiv:2511.17545}
}

read the original abstract

Quantum approaches to combinatorial optimization problems (COPs) are often limited by the resource demands of Quadratic Unconstrained Binary Optimization (QUBO) encodings, which enlarge circuits through penalty terms and increase qubit and gate counts. We show that Higher-Order Unconstrained Binary Optimization (HUBO) enables a more resource-efficient formulation. Our method systematically constructs HUBO Hamiltonians and, compared to a QUBO formulation in benchmarks on Gate Assignment (GAP), Maximum k-Colorable Subgraph (MkCS), and Integer Programming (IP) problems, significantly reduces qubit requirements and decreases total CNOT gate counts by at least 89.6% for all tested instances. These results highlight HUBO as a practical alternative for quantum optimization on near-term devices. To promote adoption, we release an open-source Python library that automates HUBO model construction, extends beyond the examples presented in this work, and broadens access to resource-efficient quantum optimization.

Figures

Figures reproduced from arXiv: 2511.17545 by the authors.

**Figure 2.** Illustration of the GAP with m = 4 airportgates and n = 3 flights. Two of the flights have passengers who require a transfer connection, which is represented by the two-way symbol. A third flight has only arriving and departing passengers, illustrated by the luggage symbol. The goal is to assign airport-gates to flight such that the total passenger walking time is minimized. assigning flight i to airport-gate v … view at source ↗

**Figure 3.** Example instance for the MkCS problem: a [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

**Figure 4.** Schematic representation of the QAOA al [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗

Figures from the paper (7 more)

**Figure 6.** Figure 6: Upper panel: Airport-Gate layout for the [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]

**Figure 10.** Figure 10: Average approximation ratio achieved by QAOA as a function of total gate count for HUBO and QUBO encodings. Results are shown for the same graph with five vertices and nine edges as in [PITH_FULL_IMAGE:figures/full_fig_p011_10.png]

**Figure 11.** Figure 11: Scaling of quantum resource requirements for [PITH_FULL_IMAGE:figures/full_fig_p012_11.png]

**Figure 13.** Figure 13: Average approximation ratio versus total gate [PITH_FULL_IMAGE:figures/full_fig_p013_13.png]

**Figure 16.** Figure 16: Gray code traversal for optimal implementation of a 4-qubit HUBO Hamiltonian. Each vertex of the [PITH_FULL_IMAGE:figures/full_fig_p017_16.png]

**Figure 17.** Figure 17: Non-optimized implementation of the cost unitary for a three-qubit HUBO Hamiltonian [PITH_FULL_IMAGE:figures/full_fig_p017_17.png]

**Figure 18.** Figure 18: Optimal quantum circuit for implementing the cost unitary of a three-qubit HUBO Hamiltonian using [PITH_FULL_IMAGE:figures/full_fig_p018_18.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

80 extracted references · 21 canonical work pages

[1]

M. Marzec. Portfolio optimization: Applications in quantum computing, 2016. URLhttps: //onlinelibrary.wiley.com/doi/abs/10.1002/9781118593486.ch4

work page doi:10.1002/9781118593486.ch4 2016
[2]

Perdomo-Ortiz, N

A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, and A. Aspuru-Guzik. Finding low- energy conformations of lattice protein models by quantum annealing.Scientific Reports, 2(1): 571, August 2012. ISSN 2045-2322. DOI: 10.1038/srep00571. URLhttps://www.nature.com/ articles/srep00571

doi:10.1038/srep00571 2012
[3]

R. J. Boucherie, A. Braaksma, and H. Tijms.Operations Research. WORLD SCIENTIFIC, 2021. DOI: 10.1142/12343

work page doi:10.1142/12343 2021
[4]

Crescenzi and V

P. Crescenzi and V. Kann. A compendium of NP optimization problems, 1995. URLhttps: //cs.pwr.edu.pl/zielinski/lectures/om/compendium.pdf

1995
[5]

Fu and P

Y. Fu and P. W. Anderson. Application of statistical mechanics to NP-complete problems in combinatorial optimisation.Journal of Physics A: Mathematical and General, 19(9):1605, June
[6]

Kirkpatrick, Jr

S. Kirkpatrick, Jr. Gelatt, C. D., and M. P. Vecchi. Optimization by simulated annealing.Science, 220(4598):671–680, 1983. DOI: 10.1126/science.220.4598.671

doi:10.1126/science.220.4598.671 1983
[7]

Glover, E

F. Glover, E. TaiUard, and D. de Werra. A user’s guide to tabu search.Annals of Operations Research, 41(1):1–28, March 1993. ISSN 1572-9338. DOI: 10.1007/BF02078647

work page doi:10.1007/bf02078647 1993
[8]

IBM ILOG CPLEX Optimization Studio, November 2024

IBM CPLEX. IBM ILOG CPLEX Optimization Studio, November 2024. URLhttps://www. ibm.com/products/ilog-cplex-optimization-studio

2024

Show all 80 references

[9]

Gurobi optimization, July 2025

Gurobi Optimization. Gurobi optimization, July 2025. URLhttps://www.gurobi.com/

2025
[10]

Xu and L

L. Xu and L. Liberti. Relaxations for binary polynomial optimization via signed certificates, 2024. URLhttps://arxiv.org/abs/2405.13447

2024 arXiv
[11]

Puchinger, G

J. Puchinger, G. R. Raidl, and U. Pferschy. The Multidimensional Knapsack Problem: Structure and Algorithms.INFORMS Journal on Computing, 22(2):250–265, May 2010. ISSN 1091-9856, 1526-5528. DOI: 10.1287/ijoc.1090.0344

2010
[12]

Packebusch and S

T. Packebusch and S. Mertens. Low Autocorrelation Binary Sequences.Journal of Physics A: Mathematical and Theoretical, 49(16):165001, April 2016. ISSN 1751-8113, 1751-8121. DOI: 10.1088/1751-8113/49/16/165001

2016 doi
[13]

Danilova, P

M. Danilova, P. Dvurechensky, A. Gasnikov, E. Gorbunov, S. Guminov, D. Kamzolov, and I. Shibaev. Recent Theoretical Advances in Non-Convex Optimization. In Ashkan Nikeghbali, Panos M. Pardalos, Andrei M. Raigorodskii, and Michael Th. Rassias, editors,High-Dimensional Optimizat...

2022 doi
[14]

Burer and A

S. Burer and A. N. Letchford. Non-convex mixed-integer nonlinear programming: A survey.Sur- veys in Operations Research and Management Science, 17(2):97–106, July 2012. ISSN 1876-7354. DOI: 10.1016/j.sorms.2012.08.001. URLhttps://www.sciencedirect.com/science/article/ pii/S187...

2012 doi
[15]

C. A. Floudas, I. G. Akrotiriankis, S. Caratzoulas, C. A. Meyer, and J. Kallrath. Global op- timization in the 21st century: Advances and challenges.Computers & Chemical Engineering, 20 29(6):1185–1202, May 2004. ISSN 0098-1354. DOI: 10.1016/j.compchemeng.2005.02.006. URL http...

2004 doi
[16]

Albash and D

T. Albash and D. A. Lidar. Adiabatic quantum computation.Reviews of Modern Physics, 90(1): 015002, January 2018. ISSN 0034-6861, 1539-0756. DOI: 10.1103/RevModPhys.90.015002

2018 doi
[17]

Ebadi, A

S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner, V. Vuletić, and M. D. Lukin. Quant...

2022 doi
[18]

Farhi, J

E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm, 2014. URLhttps://arxiv.org/abs/1411.4028

2014 arXiv
[19]

A. Lucas. Ising formulations of many NP problems.Frontiers in Physics, 2, February 2014. ISSN 2296-424X. DOI: 10.3389/fphy.2014.00005

2014
[20]

Goswami, R

K. Goswami, R. Mukherjee, H. Ott, and P. Schmelcher. Solving optimization problems with local light shift encoding on Rydberg quantum annealers.Physical Review Research, 6(2):023031, April
[21]

C. Lai, C. Blank, P. Schmelcher, and R. Mukherjee. Towards arbitrary qubo optimization: Anal- ysis of classical and quantum-activated feedforward neural networks, 2024

2024
[22]

Zaman, K

M. Zaman, K. Tanahashi, and S. Tanaka. Pyqubo: Python library for mapping combinatorial optimization problems to qubo form.IEEE Transactions on Computers, 71(4):838–850, 2022. DOI: 10.1109/TC.2021.3063618

2022
[23]

Dominguez, J

F. Dominguez, J. Unger, M. Traube, B. Mant, C. Ertler, and W. Lechner. Encoding-independent optimization problem formulation for quantum computing.Frontiers in Quantum Science and Technology, 2, September 2023. ISSN 2813-2181. DOI: 10.3389/frqst.2023.1229471. URLhttp: //dx.doi...

2023
[24]

J. A. Montañez-Barrera, D. Willsch, A. Maldonado-Romo, and K. Michielsen. Unbalanced penal- ization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms.Quantum Science and Technology, 9(2):025022, April 2024. ISSN 2058-

2024
[25]

S. V. Romero, A.-M. Visuri, A. Gomez Cadavid, A. Simen, E. Solano, and N. N. Hegade. Bias-field digitized counterdiabatic quantum algorithm for higher-order binary optimization.Communica- tions Physics, 8(1), August 2025. ISSN 2399-3650. DOI: 10.1038/s42005-025-02270-3. URL ht...

2025 doi
[26]

A. Glos, A. Krawiec, and Z. Zimborás. Space-efficient binary optimization for variational quantum computing.npj Quantum Information, 8(1):39, April 2022. ISSN 2056-6387. DOI: 10.1038/s41534- 022-00546-y. URLhttps://www.nature.com/articles/s41534-022-00546-y

2022 doi
[27]

S. V. Romero, A. Gomez Cadavid, P. Nikačević, E. Solano, N. N. Hegade, M. A. Lopez-Ruiz, C. Girotto, M. Yamada, P. Kl. Barkoutsos, A. Kaushik, and M. Roetteler. Protein folding with an all-to-all trapped-ion quantum computer, 2025. URLhttps://arxiv.org/abs/2506.07866

2025 arXiv
[28]

Yahui, E

C. Yahui, E. Epifanovsky, K. Jansen, A. Kaushik, and S. Kühn. Simulating the flight gate assignment problem on a trapped ion quantum computer, 2023. URLhttps://arxiv.org/abs/ 2309.09686

2023 arXiv
[29]

Wintersperger, F

K. Wintersperger, F. Dommert, T. Ehmer, A. Hoursanov, J. Klepsch, W. Mauerer, G. Reuber, T. Strohm, M. Yin, and S. Luber. Neutral atom quantum computing hardware: performance and end-user perspective.EPJ Quantum Technology, 10(1), August 2023. ISSN 2196-0763. DOI: 10.1140/epjq...

2023 doi
[30]

Fauseweh

B. Fauseweh. Quantum many-body simulations on digital quantum computers: State-of-the-art and future challenges.Nature Communications, 15(1):2123, March 2024. ISSN 2041-1723. DOI: 10.1038/s41467-024-46402-9

2024 doi
[31]

F. Koch. PyHUBO, October 2025. URLhttps://github.com/frederikKoch/PyHUBO. 21

2025
[32]

Schrijver.Combinatorial Optimization: Polyhedra and Efficiency, volume B

A. Schrijver.Combinatorial Optimization: Polyhedra and Efficiency, volume B. Journal of Computer and System Sciences - JCSS, 2003. URLhttps://link.springer.com/book/ 9783540443896

2003
[33]

T. G. Crainic, M. Gendreau, and A. Frangioni, editors.Combinatorial Optimization and Applica- tions: A Tribute to Bernard Gendron, volume 358 ofInternational Series in Operations Research & Management Science. Springer Nature Switzerland, Cham, 2024. ISBN 978-3-031-57602-7 978...

2024 doi
[34]

J. Chen, H. Westerheim, Z. Holmes, I. Luo, T. Nuradha, D. Patel, S. Rethinasamy, K. Wang, and M. M. Wilde. Slack-variable approach for variational quantum semidefinite programming.Physical Review A, 112(2):022607, August 2025. ISSN 2469-9926, 2469-9934. DOI: 10.1103/lwxq-4myj

2025 doi
[35]

QuantumbridgeanalyticsI:Atutorialonformulatingand using QUBO models.Annals of Operations Research, 314(1):141–183, July 2022

F.Glover, G.Kochenberger, andY.Du. QuantumbridgeanalyticsI:Atutorialonformulatingand using QUBO models.Annals of Operations Research, 314(1):141–183, July 2022. ISSN 1572-9338. DOI: 10.1007/s10479-022-04634-2

2022 doi
[36]

Bouras, M

A. Bouras, M. A. Ghaleb, U. S. Suryahatmaja, and A. M. Salem. The Airport Gate Assignment Problem: A Survey.The Scientific World Journal, 2014:1–27, 2014. ISSN 2356-6140, 1537-744X. DOI: 10.1155/2014/923859. URLhttp://www.hindawi.com/journals/tswj/2014/923859/

2014 doi
[38]

Bentert, R

M. Bentert, R. van Bevern, and R. Niedermeier. Inductive $k$-independent graphs and $c$- colorable subgraphs in scheduling: A review.Journal of Scheduling, 22(1):3–20, February 2019. ISSN 1094-6136, 1099-1425. DOI: 10.1007/s10951-018-0595-8

2019 doi
[39]

M. M. Halldórsson, J. Y. Halpern, L. (Erran) Li, and V. S. Mirrokni. On spectrum sharing games. InProceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, pages 107–114, St. John’s Newfoundland Canada, July 2004. ACM. ISBN 978-1- 58113-802-3...

2004
[40]

Hertz, R

A. Hertz, R. Montagné, and F. Gagnon. Constructive algorithms for the partial directed weighted improper coloring problem.Journal of Graph Algorithms and Applications, 20(2):159–188, Febru- ary 2016. ISSN 1526-1719. DOI: 10.7155/jgaa.00389

2016 doi
[41]

Koster and M

A.M.C.A. Koster and M. Scheffel. A Routing and Network Dimensioning Strategy to re- duce Wavelength Continuity Conflicts in All-Optical Networks, November 2006. URLhttps: //optimization-online.org/?p=10032

2006
[42]

D. Liu, J. Li, X. Cheng, S. Zhang, Y. Chang, and L. Yan. Efficient hybrid variational quantum algorithm for solving graph coloring problem, 2025. URLhttps://arxiv.org/abs/2504.21335

2025 arXiv
[43]

Quintero, D

R. Quintero, D. Bernal, T. Terlaky, and L. F. Zuluaga. Characterization of qubo reformulations for the maximumk-colorable subgraph problem, 2021. URLhttps://arxiv.org/abs/2101.09462

2021 arXiv
[44]

Z. Wang, N. C. Rubin, J. M. Dominy, and E. G. Rieffel. $XY$-mixers: Analytical and numerical results for QAOA.Physical Review A, 101(1):012320, January 2020. ISSN 2469-9926, 2469-9934. DOI: 10.1103/PhysRevA.101.012320

2020 doi
[45]

Streif, M

M. Streif, M. Leib, F. Wudarski, E. Rieffel, and Z. Wang. Quantum algorithms with local particle number conservation: Noise effects and error correction.Physical Review A, 103(4):042412, April
[46]

Sotirov, O

R. Sotirov, O. Kuryatnikova, and J. Vera. The maximumk-colorable subgraph problem and related problems, 2021. URLhttps://arxiv.org/abs/2001.09644

2021 arXiv
[47]

L. Wolsey. Integer programming. InInteger Programming, chapter 1, pages 1–23. John Wiley & Sons, Ltd, 2020. ISBN 978-1-119-60647-5. DOI: 10.1002/9781119606475.ch1

2020 doi
[48]

Yves and A

P. Yves and A. W. Laurence.Production Planning by Mixed Integer Programming. Springer Series in Operations Research and Financial Engineering. Springer New York, 2006. ISBN 978-0-387- 29959-4. DOI: 10.1007/0-387-33477-7. 22

2006 doi
[49]

Magatão, L.V.R Arruda, and F Neves Jr

L. Magatão, L.V.R Arruda, and F Neves Jr. A Mixed Integer Programming Approach for Schedul- ing Commodities in a Pipeline. In Johan Grievink and Jan van Schijndel, editors,Computer Aided Chemical Engineering, volume 10 ofEuropean Symposium on Computer Aided Process Engineering...

2002 doi
[50]

Goswami, P

K. Goswami, P. Schmelcher, and R. Mukherjee. Qudit-based scalable quantum algorithm for solving the integer programming problem, 2025. URLhttps://arxiv.org/abs/2508.13906

2025 arXiv
[51]

Svensson, M

M. Svensson, M. Andersson, M. Grönkvist, P. Vikstål, D. Dubhashi, G. Ferrini, and G. Johans- son. Hybrid Quantum-Classical Heuristic to Solve Large-Scale Integer Linear Programs.Physical Review Applied, 20(3):034062, September 2023. ISSN 2331-7019. DOI: 10.1103/PhysRevAp- plie...

2023 doi
[52]

Sharma and H.C

M. Sharma and H.C. Lau. Cutting slack: Quantum optimization with slack-free methods for combinatorial benchmarks, 2025. URLhttps://arxiv.org/abs/2507.12159

2025 arXiv
[53]

Tanahashi, S

K. Tanahashi, S. Takayanagi, T. Motohashi, and S. Tanaka. Application of ising machines and a software development for ising machines.Journal of the Physical Society of Japan, 88(6):061010,
[54]

Hadfield

S. Hadfield. On the representation of Boolean and real functions as Hamiltonians for quantum computing.ACM Transactions on Quantum Computing, 2(4):1–21, December 2021. ISSN 2643- 6809, 2643-6817. DOI: 10.1145/3478519

2021 doi
[55]

Farhi, J

E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda. A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem.Science, 292 (5516):472–475, April 2001. ISSN 0036-8075, 1095-9203. DOI: 10.1126/science.1057726

2001 doi
[56]

McArdle, T

S. McArdle, T. Jones, S. Endo, Y. Li, S. C. Benjamin, and X. Yuan. Variational ansatz-based quantum simulation of imaginary time evolution.npj Quantum Information, 5(1):75, September
[57]

M. J. S. Beach, R. G. Melko, T. Grover, and T. H. Hsieh. Making trotters sprint: A varia- tional imaginary time ansatz for quantum many-body systems.Physical Review B, 100(9):094434, September 2019. ISSN 2469-9950, 2469-9969. DOI: 10.1103/PhysRevB.100.094434

2019 doi
[58]

P. J. Love. Cooling with imaginary time.Nature Physics, 16(2):130–131, February 2020. ISSN 1745-2481. DOI: 10.1038/s41567-019-0709-z

2020 doi
[59]

Peruzzo, J

A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien. A variational eigenvalue solver on a photonic quantum processor.Nature Communications, 5(1):4213, July 2014. ISSN 2041-1723. DOI: 10.1038/ncomms5213

2014 doi
[60]

Tilly, H

J. Tilly, H. Chen, S. Cao, D. Picozzi, K. Setia, Y. Li, E. Grant, L. Wossnig, I. Rungger, G. H. Booth, and J. Tennyson. The Variational Quantum Eigensolver: A review of meth- ods and best practices.Physics Reports, 986:1–128, November 2022. ISSN 0370-1573. DOI: 10.1016/j.physr...

2022 doi
[61]

Zhou, S.-T

L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin. Quantum Approximate Optimiza- tion Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices.Physical Review X, 10(2):021067, June 2020. ISSN 2160-3308. DOI: 10.1103/PhysRevX.10.021067

2020 doi
[62]

DOI: 10.1038/s41534-019-0187-2

ISSN 2056-6387. DOI: 10.1038/s41534-019-0187-2

doi
[63]

Blekos, D

K. Blekos, D. Brand, A. Ceschini, C.-H. Chou, R.-H. Li, K. Pandya, and A. Summer. A review on Quantum Approximate Optimization Algorithm and its variants.Physics Reports, 1068:1–66, June 2024. ISSN 0370-1573. DOI: 10.1016/j.physrep.2024.03.002. URLhttps://linkinghub. elsevier....

2024 doi
[64]

Golden, A

J. Golden, A. Bärtschi, D. O’Malley, and S. Eidenbenz. Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization. In2023 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 496–505, Septemb...

2023
[65]

Weidenfeller, L

J. Weidenfeller, L. C. Valor, J. Gacon, C. Tornow, L. Bello, S. Woerner, and D. J. Egger. Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware. Quantum, 6:870, December 2022. ISSN 2521-327X. DOI: 10.22331/q-2022-12-07-870

2022 doi
[66]

Kurowski, T

K. Kurowski, T. Pecyna, M. Slysz, R. Różycki, G. Waligóra, and J. Węglarz. Applica- tion of quantum approximate optimization algorithm to job shop scheduling problem.Euro- pean Journal of Operational Research, 310(2):518–528, October 2023. ISSN 0377-2217. DOI: 10.1016/j.ejor.2...

2023 doi
[67]

Wang, H.-L

S.-S. Wang, H.-L. Liu, Y.-Q. Song, F. Gao, S.-J. Qin, and Q.-Y. Wen. Quantum alternating oper- ator ansatz for solving the minimum exact cover problem.Physica A: Statistical Mechanics and its Applications, 626:129089, September 2023. ISSN 0378-4371. DOI: 10.1016/j.physa.2023.129089

2023
[68]

Basso, D

J. Basso, D. Gamarnik, S. Mei, and L. Zhou. Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models. In2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 335–343, October 2022. DOI: 10.1109/FOCS...

2022
[69]

Blondel, Q

M. Blondel, Q. Berthet, M. Cuturi, R. Frostig, S. Hoyer, F. Llinares-López, F. Pedregosa, and J.-P. Vert. Efficient and modular implicit differentiation, 2022. URLhttps://arxiv.org/abs/ 2105.15183

2022 arXiv
[70]

Bergholm, J

V. Bergholm, J. Izaac, M. Schuld, C. Gogolin, S. Ahmed, V. Ajith, M. S. Alam, G. Alonso-Linaje, B. AkashNarayanan, A. Asadi, J. M. Arrazola, U. Azad, S. Banning, C. Blank, T. R. Bromley, B. A. Cordier, J. Ceroni, A. Delgado, O. Di Matteo, A. Dusko, T. Garg, D. Guala, A. Hayes,...

2022 arXiv
[71]

Schulz, D

S. Schulz, D. Willsch, and K. Michielsen. Guided quantum walk.Physical Review Research, 6(1): 013312, March 2024. ISSN 2643-1564. DOI: 10.1103/PhysRevResearch.6.013312

2024 doi
[72]

Verchère, S

Z. Verchère, S. Elloumi, and A. Simonetto. Optimizing variational circuits for higher-order binary optimization, 2023. URLhttps://arxiv.org/abs/2307.16756

2023 arXiv
[73]

M. Amy, P. Azimzadeh, and M. Mosca. On the CNOT-complexity of CNOT-PHASE cir- cuits.Quantum Science and Technology, 4(1):015002, September 2018. ISSN 2058-9565. DOI: 10.1088/2058-9565/aad8ca

2018 doi
[74]

Sachdeva, G

N. Sachdeva, G. S. Hartnett, S. Maity, S. Marsh, Y. Wang, A. Winick, R. Dougherty, D. Canuto, Y. Q. Chong, M. Hush, P. S. Mundada, C. D. B. Bentley, M. J. Biercuk, and Y. Baum. Quantum optimization using a 127-qubit gate-model ibm quantum computer can outperform quantum an- ne...

2024
[75]

Hoeffding

W. Hoeffding. Probability Inequalities for Sums of Bounded Random Variables.Journal of the American Statistical Association, 58(301):13–30, March 1963. ISSN 0162-1459. DOI: 10.1080/01621459.1963.10500830. 24

1963
[80]

Welch, D

J. Welch, D. Greenbaum, S. Mostame, and A. Aspuru-Guzik. Efficient quantum circuits for diagonal unitaries without ancillas.New Journal of Physics, 16(3):033040, March 2014. ISSN 1367-2630. DOI: 10.1088/1367-2630/16/3/033040

2014 doi
[1986]

DOI: 10.1088/0305-4470/19/9/033

ISSN 0305-4470. DOI: 10.1088/0305-4470/19/9/033

doi
[2019]

DOI: 10.7566/JPSJ.88.061010

doi
[2021]

DOI: 10.1103/PhysRevA.103.042412

ISSN 2469-9926, 2469-9934. DOI: 10.1103/PhysRevA.103.042412

doi
[2024]

DOI: 10.1103/PhysRevResearch.6.023031

ISSN 2643-1564. DOI: 10.1103/PhysRevResearch.6.023031

doi
[9565]

DOI: 10.1088/2058-9565/ad35e4

doi

Pith tools

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

[1] [1]

M. Marzec. Portfolio optimization: Applications in quantum computing, 2016. URLhttps: //onlinelibrary.wiley.com/doi/abs/10.1002/9781118593486.ch4

work page doi:10.1002/9781118593486.ch4 2016

[2] [2]

Perdomo-Ortiz, N

A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, and A. Aspuru-Guzik. Finding low- energy conformations of lattice protein models by quantum annealing.Scientific Reports, 2(1): 571, August 2012. ISSN 2045-2322. DOI: 10.1038/srep00571. URLhttps://www.nature.com/ articles/srep00571

doi:10.1038/srep00571 2012

[3] [3]

R. J. Boucherie, A. Braaksma, and H. Tijms.Operations Research. WORLD SCIENTIFIC, 2021. DOI: 10.1142/12343

work page doi:10.1142/12343 2021

[4] [4]

Crescenzi and V

P. Crescenzi and V. Kann. A compendium of NP optimization problems, 1995. URLhttps: //cs.pwr.edu.pl/zielinski/lectures/om/compendium.pdf

1995

[5] [5]

Fu and P

Y. Fu and P. W. Anderson. Application of statistical mechanics to NP-complete problems in combinatorial optimisation.Journal of Physics A: Mathematical and General, 19(9):1605, June

[6] [6]

Kirkpatrick, Jr

S. Kirkpatrick, Jr. Gelatt, C. D., and M. P. Vecchi. Optimization by simulated annealing.Science, 220(4598):671–680, 1983. DOI: 10.1126/science.220.4598.671

doi:10.1126/science.220.4598.671 1983

[7] [7]

Glover, E

F. Glover, E. TaiUard, and D. de Werra. A user’s guide to tabu search.Annals of Operations Research, 41(1):1–28, March 1993. ISSN 1572-9338. DOI: 10.1007/BF02078647

work page doi:10.1007/bf02078647 1993

[8] [8]

IBM ILOG CPLEX Optimization Studio, November 2024

IBM CPLEX. IBM ILOG CPLEX Optimization Studio, November 2024. URLhttps://www. ibm.com/products/ilog-cplex-optimization-studio

2024