pith. machine review for the scientific record. sign in

arxiv: 2604.21123 · v1 · submitted 2026-04-22 · 🪐 quant-ph

Recognition: unknown

Qubit-efficient and gate-efficient encodings of graph partitioning problems for quantum optimization

Tristan Zaborniak , Prashanti Priya Angara , Vikram Khipple Mulligan , Hausi M\"uller , Ulrike Stege
Authors on Pith no claims yet

Pith reviewed 2026-05-09 23:48 UTC · model grok-4.3

classification 🪐 quant-ph
keywords graph partitioningquantum optimizationHUBOQAOAlogarithmic encodinggraph coloringminimum k-cutpenalty coefficients
0
0 comments X

The pith

A logarithmic encoding with lexicographic penalties formulates graph partitioning problems like coloring and k-cut as HUBO using ceiling log2 k bits per vertex while proving conditions that make the lowest energy state optimal.

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

The paper develops an encoding for problems that assign vertices to partitions while minimizing the number of partitions used. Each k-valued assignment variable is represented with only ceiling of log base 2 of k binary variables instead of k. A new penalty system orders the penalties lexicographically so that the total number of partitions is minimized implicitly without extra indicator variables. Sufficient conditions on all penalty coefficients, including after quadratization, are derived to guarantee that feasible and optimal solutions correspond to the lowest energy. This reduces qubit count and two-qubit gate count compared with one-hot encoding and improves solution quality on quantum annealers for minimum graph coloring as problem size grows.

Core claim

The central construction encodes each k-valued vertex variable with ceiling log2 k bits and introduces a lexicographic penalty system that implicitly minimizes the number of partitions without dedicated indicator variables. Provably sufficient conditions are given on all penalty coefficients, including those from Rosenberg quadratization, that guarantee the lowest-energy solution is both feasible and optimal. The same conditions are derived for one-hot encoding to allow direct comparison, and the logarithmic version reduces two-qubit gate count per QAOA layer from Theta of |V| times k squared plus |E| times k to Theta of |E| times k times ceiling log2 k.

What carries the argument

Logarithmic encoding of each k-valued vertex variable using ceiling log2 k bits together with a lexicographic penalty system that orders terms to minimize partition count implicitly.

If this is right

  • The two-qubit gate count per QAOA layer scales as Theta of |E| times k times ceiling log2 k instead of Theta of |V| k squared plus |E| k.
  • Solution quality and time-to-solution improve on quantum annealers for minimum graph coloring relative to one-hot encoding, with larger gains as problem size increases.
  • The encoding applies directly to the optimization versions of minimum graph coloring, minimum k-cut, and community detection.
  • Analogous penalty conditions hold for one-hot encoding, enabling controlled comparisons between the two approaches.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach may allow quantum solvers to handle larger instances of NP-hard partitioning problems before hardware limits are reached.
  • The lexicographic penalty idea could extend to other label-assignment problems that require minimizing the number of distinct labels used.
  • As problem size grows, the gate-count advantage suggests logarithmic encodings will outperform one-hot encodings on devices with limited connectivity.

Load-bearing premise

The derived sufficient conditions on the penalty coefficients can be satisfied in practice without making the resulting energy landscape too difficult for a quantum solver to reach its global minimum.

What would settle it

For a small minimum graph coloring instance encoded with the logarithmic method, the configuration that achieves the lowest energy on a quantum annealer or QAOA simulator is either infeasible or uses more colors than the known optimum.

Figures

Figures reproduced from arXiv: 2604.21123 by Hausi M\"uller, Prashanti Priya Angara, Tristan Zaborniak, Ulrike Stege, Vikram Khipple Mulligan.

Figure 1
Figure 1. Figure 1: Small example graph colored improperly (upper row, violating [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Upper left: TTS as a function of |V |. Upper right: Post￾quadratization logical qubits per encoding; inset: pre-quadratization. Lower left: Physical qubits after minor embedding. Lower right: Chain length variance; inset: average chain length. 3) Performance Measures: We evaluate the encodings us￾ing three complementary metrics: Time-to-Solution, which captures end-to-end solver performance; survival-time … view at source ↗
read the original abstract

We introduce a qubit- and gate-efficient higher-order unconstrained binary optimization (HUBO) encoding for graph partitioning problems requiring label-count minimization. This widely applicable class of problems includes minimum graph coloring, minimum $k$-cut, and community detection. To the best of our knowledge, this is the first work to address the optimization versions of these problems in a quantum setting, rather than only their decision counterparts. Our construction encodes each $k$-valued vertex variable using $\lceil \log_2 k \rceil$ bits and employs a novel lexicographic penalty system that implicitly minimizes partition count without requiring dedicated indicator variables. We derive provably sufficient conditions on all penalty coefficients, including those arising from Rosenberg quadratization, guaranteeing feasibility and optimality of the lowest-energy solution. Analogous conditions are derived for a one-hot encoding to enable controlled comparison. We also show that our encoding reduces two-qubit gate count per QAOA layer from $\Theta(|V||k|^2 + |E||k|)$ for the one-hot encoding to $\Theta(|E| \cdot |k| \lceil\log_2 |k|\rceil)$. Benchmarking on a quantum annealer demonstrates that our logarithmic encoding significantly improves solution quality and time-to-solution for minimum graph coloring relative to one-hot encoding, with greater advantage as problem size increases.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces a qubit-efficient encoding for graph partitioning problems (minimum graph coloring, minimum k-cut, community detection) that uses ⌈log₂ k⌉ qubits per vertex rather than one-hot encoding. It employs a novel lexicographic penalty system to implicitly minimize the number of partitions without extra indicator variables, derives provably sufficient conditions on all penalty coefficients (including post-Rosenberg quadratization) to guarantee that the lowest-energy state is feasible and optimal, provides analogous conditions for one-hot encoding, reduces QAOA two-qubit gate count to Θ(|E| · |k| ⌈log₂ |k|⌉), and reports annealer benchmarks showing improved solution quality and time-to-solution for graph coloring with increasing advantage at larger sizes.

Significance. If the derived sufficient conditions are correct and the reported benchmarks employ coefficients satisfying those conditions, the work offers a concrete advance in encoding combinatorial optimization problems for near-term quantum hardware by cutting qubit count and gate overhead while preserving optimality guarantees. The explicit penalty bounds, the focus on optimization (rather than decision) versions, and the direct gate-count comparison to one-hot encoding are strengths. The approach could enable larger instances on current annealers or gate-model devices, provided the penalty scaling does not render the ground-state gap inaccessible.

major comments (2)
  1. [§4] §4 (penalty coefficient derivation): the lower bounds on the objective, adjacency, and auxiliary penalties (including Rosenberg terms) are linear in the number of terms and maximum degree. For |V| ≳ 50 and k ≳ 8 these bounds already exceed typical D-Wave dynamic range and precision; the resulting spectral gap scales as 1/poly(|V|), making the probability of reaching the claimed global minimum exponentially small within reported annealing times or QAOA depths. This directly affects whether the optimality guarantee is practically realizable.
  2. [Benchmarking section] Benchmarking section: the experiments compare logarithmic and one-hot encodings under identical (already large) penalty values but do not state whether those values meet the derived sufficient conditions or are chosen heuristically. If the latter, the optimality guarantee does not apply to the reported solutions, undermining the claim that the encoding improves solution quality while preserving feasibility and optimality.
minor comments (2)
  1. [Abstract] The abstract and introduction should explicitly reference the specific prior works on logarithmic encodings for quantum optimization that were considered when claiming novelty.
  2. Notation for the partition-count objective and the lexicographic penalty terms is introduced without a consolidated table; a single table listing all symbols, their meanings, and the corresponding penalty lower bounds would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and valuable feedback on our manuscript. The comments raise important points about the practical realizability of the derived penalty bounds and the clarity of the benchmarking setup. We address each major comment below and outline revisions to strengthen the presentation of these aspects while preserving the core contributions on qubit-efficient encodings and optimality guarantees.

read point-by-point responses

  1. Referee: [§4] §4 (penalty coefficient derivation): the lower bounds on the objective, adjacency, and auxiliary penalties (including Rosenberg terms) are linear in the number of terms and maximum degree. For |V| ≳ 50 and k ≳ 8 these bounds already exceed typical D-Wave dynamic range and precision; the resulting spectral gap scales as 1/poly(|V|), making the probability of reaching the claimed global minimum exponentially small within reported annealing times or QAOA depths. This directly affects whether the optimality guarantee is practically realizable.

    Authors: We agree that the sufficient conditions yield penalty lower bounds that scale linearly with the number of terms and maximum degree, which can exceed typical hardware precision for |V| ≳ 50 and k ≳ 8. This scaling is inherent to penalty-based formulations of combinatorial problems and leads to a polynomially shrinking gap, reducing the success probability under fixed annealing times or QAOA depths. The optimality guarantee remains valid when the conditions are met, but we acknowledge the practical challenge for large instances. In the revised manuscript we will add a dedicated paragraph in §4 (and a brief note in the conclusions) discussing this scaling behavior, noting it as a general limitation of penalty methods, and outlining possible mitigations such as coefficient normalization, adaptive penalty tuning, or hybrid classical post-processing. These additions clarify applicability without altering the theoretical results. revision: partial

  2. Referee: [Benchmarking section] Benchmarking section: the experiments compare logarithmic and one-hot encodings under identical (already large) penalty values but do not state whether those values meet the derived sufficient conditions or are chosen heuristically. If the latter, the optimality guarantee does not apply to the reported solutions, undermining the claim that the encoding improves solution quality while preserving feasibility and optimality.

    Authors: The penalty coefficients employed in the benchmarking were selected to satisfy the sufficient conditions derived in §4 for the specific graph instances (with |V| ≤ 20). We will revise the benchmarking section to explicitly state this fact, report the exact numerical values used for each instance, and include a short verification that they meet or exceed the lower bounds. This ensures the optimality and feasibility guarantees apply to the presented results. We regret the lack of explicit statement in the original submission and thank the referee for catching this omission. revision: yes

Circularity Check

0 steps flagged

Derivation of penalty bounds and encoding is self-contained with no reduction to inputs

full rationale

The paper constructs an explicit logarithmic encoding and lexicographic penalty system, then derives sufficient lower bounds on all coefficients (including post-Rosenberg terms) via direct comparison of feasible vs. infeasible configurations. These bounds are proven mathematically from the problem structure without fitting parameters, self-referential definitions, or load-bearing self-citations for the optimality claim. The central guarantee follows from the explicit inequalities rather than renaming or smuggling prior ansatzes. No step reduces the claimed result to its own inputs by construction.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard assumptions of quantum optimization solvers plus the new encoding construction; no free parameters are explicitly fitted in the abstract, but penalty coefficients must satisfy derived inequalities.

free parameters (1)
  • penalty coefficients
    Sufficient conditions are derived, but specific numerical values must still be chosen to meet the inequalities for any given instance.
axioms (1)
  • domain assumption Quantum solver (annealer or QAOA) finds the global lowest-energy state of the HUBO.
    The optimality guarantee assumes the hardware reaches the true minimum rather than a local one.

pith-pipeline@v0.9.0 · 5560 in / 1292 out tokens · 33372 ms · 2026-05-09T23:48:37.991530+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

52 extracted references · 33 canonical work pages · 1 internal anchor

  1. [1]

    An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory,

    N. Pirnay, V . Ulitzsch, F. Wilde, J. Eisert, and J.-P. Seifert, “An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory,”Science Advances, Mar. 2024. [Online]. Available: https: //doi.org/10.1126/sciadv.adj5170

    work page doi:10.1126/sciadv.adj5170 2024

  2. [2]

    Convergence and efficiency proof of quantum imaginary time evolution for bounded order systems,

    T. Hartung and K. Jansen, “Convergence and efficiency proof of quantum imaginary time evolution for bounded order systems,” 2025. [Online]. Available: https://doi.org/10.48550/arxiv.2506.03014

    work page doi:10.48550/arxiv.2506.03014 2025

  3. [3]

    Scaling advantage in approximate optimization with quantum annealing,

    H. Munoz-Bauza and D. Lidar, “Scaling advantage in approximate optimization with quantum annealing,”Physical Review Letters, vol. 134, no. 16, Apr. 2025. [Online]. Available: https://doi.org/10.1103/ PhysRevLett.134.160601

    2025

  4. [4]

    Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem

    R. Shaydulin, C. Li, S. Chakrabarti, M. DeCross, D. Herman, N. Kumar, J. Larson, D. Lykov, P. Minssen, Y . Sun, Y . Alexeev, J. M. Dreiling, J. P. Gaebler, T. M. Gatterman, J. A. Gerber, K. Gilmore, D. Gresh, N. Hewitt, C. V . Horst, S. Hu, J. Johansen, M. Matheny, T. Mengle, M. Mills, S. A. Moses, B. Neyenhuis, P. Siegfried, R. Yalovetzky, and M. Pistoia...

    work page doi:10.1126/sciadv.adm6761 2024

  5. [5]

    Quantum computing in the NISQ era and beyond,

    J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum, vol. 2, p. 79, 2018. [Online]. Available: https://doi.org/10. 22331/q-2018-08-06-79

    2018

  6. [6]

    Surface codes: Towards practical large -scale quantum computation, Physical Review A 86 (2012) 032324, https://doi.org/10.1103/PhysRevA.86.032324

    A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, “Surface codes: Towards practical large-scale quantum computation,” Physical Review A, vol. 86, no. 3, p. 032324, 2012. [Online]. Available: https://doi.org/10.1103/PhysRevA.86.032324

    work page doi:10.1103/physreva.86.032324 2012

  7. [7]

    T. R. Jensen and B. Toft,Graph Coloring Problems. Wiley, Dec

  8. [8]

    Available: http://dx.doi.org/10.1002/9781118032497

    [Online]. Available: http://dx.doi.org/10.1002/9781118032497

    work page doi:10.1002/9781118032497

  9. [9]

    Community detection in graphs.Physics Reports486, 75–174 (2010)

    S. Fortunato, “Community detection in graphs,”Physics Reports, vol. 486, no. 3, pp. 75–174, Feb. 2010. [Online]. Available: https://doi.org/10.1016/j.physrep.2009.11.002

    work page doi:10.1016/j.physrep.2009.11.002 2010

  10. [10]

    Calinescu,Multiway Cut

    G. Calinescu,Multiway Cut. Boston, United States of America: Springer, 2008, pp. 567–569. [Online]. Available: https://doi.org/10. 1007/978-0-387-30162-4_253

    2008

  11. [11]

    Kadowaki and H

    T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse Ising model,”Physical Review E, vol. 58, no. 5, p. 5355, 1998. [Online]. Available: https://doi.org/10.1103/PhysRevE.58.5355

    work page doi:10.1103/physreve.58.5355 1998

  12. [12]

    A Quantum Approximate Optimization Algorithm

    E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,”arXiv:1411.4028, 2014. [Online]. Available: https://doi.org/10.48550/arXiv.1411.4028

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1411.4028 2014

  13. [13]

    Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution,

    M. Motta, C. Sun, A. T. K. Tan, M. J. O’Rourke, E. Ye, A. J. Minnich, F. G. S. L. Brandão, and G. K.-L. Chan, “Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution,”Nature Physics, vol. 16, no. 2, p. 205–210, Nov. 2019. [Online]. Available: http://dx.doi.org/10.1038/s41567-019-0704-4

    work page doi:10.1038/s41567-019-0704-4 2019

  14. [14]

    Grover adaptive search for constrained polynomial binary optimization,

    A. Gilliam, S. Woerner, and C. Gonciulea, “Grover adaptive search for constrained polynomial binary optimization,”Quantum, vol. 5, p. 428, Apr. 2021. [Online]. Available: https://doi.org/10.22331/ q-2021-04-08-428

    2021

  15. [15]

    Optimization by decoded quantum interferometry,

    S. P. Jordan, N. Shutty, M. Wootters, A. Zalcman, A. Schmidhuber, R. King, S. V . Isakov, T. Khattar, and R. Babbush, “Optimization by decoded quantum interferometry,”Nature, vol. 646, no. 8086, p. 831–836, Oct. 2025. [Online]. Available: https://doi.org/10.1038/ s41586-025-09527-5

    2025

  16. [16]

    Lucas, Ising formulations of many np problems, Frontiers in Physics2, 10.3389/fphy.2014.00005 (2014)

    A. Lucas, “Ising formulations of many NP problems,”Frontiers in Physics, vol. 2, Feb. 2014. [Online]. Available: http://doi.org/10.3389/ fphy.2014.00005

    work page arXiv 2014

  17. [17]

    Combining spectral and textural information in uav hyperspectral images to estimate rice grain yield

    A. Verma and M. Lewis, “Penalty and partitioning techniques to improve performance of QUBO solvers,”Discrete Optimization, vol. 44, p. 100594, May 2022. [Online]. Available: https://doi.org/10.1016/j. disopt.2020.100594

    work page doi:10.1016/j 2022

  18. [18]

    Domain wall encoding of discrete variables for quantum annealing and QAOA,

    N. Chancellor, “Domain wall encoding of discrete variables for quantum annealing and QAOA,”Quantum Science and Technology, vol. 4, no. 4, p. 045004, 2019. [Online]. Available: https://doi.org/10. 1088/2058-9565/ab33c2

    2019

  19. [19]

    In:2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pp

    Z. Tabi, K. H. El-Safty, Z. Kallus, P. Hága, T. Kozsik, A. Glos, and Z. Zimborás, “Quantum optimization for the graph coloring problem with space-efficient embedding,” in2020 IEEE International Conference on Quantum Computing and Engineering (QCE), 2020, pp. 56–62. [Online]. Available: https://doi.org/10.1109/QCE49297.2020.00018

    work page doi:10.1109/qce49297.2020.00018 2020

  20. [20]

    Space-efficient binary optimization for variational quantum computing,

    A. Glos, A. Krawiec, and Z. Zimborás, “Space-efficient binary optimization for variational quantum computing,”npj Quantum Information, vol. 8, no. 1, 2022. [Online]. Available: https://doi.org/10. 1038/s41534-022-00546-y

    2022

  21. [21]

    Toward quantum computational biomolecular structure prediction,

    T. Zaborniak, “Toward quantum computational biomolecular structure prediction,” Ph.D. dissertation, University of Victoria, 2025. [Online]. Available: https://hdl.handle.net/1828/22736

    2025

  22. [22]

    Qubit-efficient encoding schemes for binary optimisation problems,

    B. Tan, M.-A. Lemonde, S. Thanasilp, J. Tangpanitanon, and D. G. Angelakis, “Qubit-efficient encoding schemes for binary optimisation problems,”Quantum, vol. 5, p. 454, May 2021. [Online]. Available: http://dx.doi.org/10.22331/q-2021-05-04-454

    work page doi:10.22331/q-2021-05-04-454 2021

  23. [23]

    Exponential qubit reduction in optimization for financial transaction settlement,

    E. X. Huber, B. Y . L. Tan, P. R. Griffin, and D. G. Angelakis, “Exponential qubit reduction in optimization for financial transaction settlement,”EPJ Quantum Technology, vol. 11, no. 1, Aug. 2024. [Online]. Available: http://doi.org/10.1140/epjqt/s40507-024-00262-w

    work page doi:10.1140/epjqt/s40507-024-00262-w 2024

  24. [24]

    Qubit efficient quantum algorithms for the vehicle routing problem on noisy intermediate-scale quantum processors,

    I. D. Leonidas, A. Dukakis, B. Tan, and D. G. Angelakis, “Qubit efficient quantum algorithms for the vehicle routing problem on noisy intermediate-scale quantum processors,”Advanced Quantum Technologies, vol. 7, no. 5, Apr. 2024. [Online]. Available: http: //dx.doi.org/10.1002/qute.202300309

    work page doi:10.1002/qute.202300309 2024

  25. [25]

    NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization,

    M. R. Perelshtein, A. I. Pakhomchik, A. A. Melnikov, M. Podobrii, A. Termanova, I. Kreidich, B. Nuriev, S. Iudin, C. W. Mansell, and V . M. Vinokur, “NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization,”Quantum, vol. 7, p. 1186, Nov. 2023. [Online]. Available: http://dx.doi.org/10.22331/ q-2023-11-21-1186

    2023

  26. [26]

    Towards large-scale quantum optimization solvers with few qubits,

    M. Sciorilli, L. Borges, T. L. Patti, D. García-Martín, G. Camilo, A. Anandkumar, and L. Aolita, “Towards large-scale quantum optimization solvers with few qubits,”Nature Communications, vol. 16, no. 1, Jan. 2025. [Online]. Available: http://doi.org/10.1038/ s41467-024-55346-z

    2025

  27. [27]

    Compressed space quantum approximate op- timization algorithm for constrained combinatorial optimization,

    T. Shirai and N. Togawa, “Compressed space quantum approximate op- timization algorithm for constrained combinatorial optimization,”IEEE Transactions on Quantum Engineering, vol. 6, pp. 1–14, 2025

    2025

  28. [28]

    Accelerating grover adaptive search: Qubit and gate count reduction strategies with higher order formulations,

    Y . Sano, K. Mitarai, N. Yamamoto, and N. Ishikawa, “Accelerating grover adaptive search: Qubit and gate count reduction strategies with higher order formulations,”IEEE Transactions on Quantum Engineering, vol. 5, pp. 1–12, 2024. [Online]. Available: https: //doi.org/10.1109/TQE.2024.3393437

    work page doi:10.1109/tqe.2024.3393437 2024

  29. [29]

    Solving various np-hard problems using exponentially fewer qubits on a quantum computer,

    Y . Chatterjee, E. Bourreau, and M. J. Ran ˇci´c, “Solving various np-hard problems using exponentially fewer qubits on a quantum computer,” Physical Review A, vol. 109, no. 5, May 2024. [Online]. Available: http://doi.org/10.1103/PhysRevA.109.052441

    work page doi:10.1103/physreva.109.052441 2024

  30. [30]

    Understanding domain-wall encoding theoretically and experimentally,

    J. Berwald, N. Chancellor, and R. Dridi, “Understanding domain-wall encoding theoretically and experimentally,”Philosophical Transactions of the Royal Society A, vol. 381, no. 20210410, 2022. [Online]. Available: https://doi.org/10.1098/rsta.2021.0410

    work page doi:10.1098/rsta.2021.0410 2022

  31. [31]

    Performance of domain-wall encoding for quantum annealing,

    J. Chen, T. Stollenwerk, and N. Chancellor, “Performance of domain-wall encoding for quantum annealing,”IEEE Transactions on Quantum Engineering, vol. 2, pp. 1–14, 2021. [Online]. Available: https://doi.org/10.1109/TQE.2021.3094280

    work page doi:10.1109/tqe.2021.3094280 2021

  32. [32]

    Cerezoet al., Variational quantum al- gorithms, Nat

    M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, “Variational quantum algorithms,”Nature Reviews Physics, vol. 3, no. 9, p. 625–644, Aug. 2021. [Online]. Available: http://dx.doi.org/10.1038/s42254-021-00348-9

    work page doi:10.1038/s42254-021-00348-9 2021

  33. [33]

    Grover adaptive search with fewer queries,

    H. Ominato, T. Ohyama, and K. Yamaguchi, “Grover adaptive search with fewer queries,”IEEE Access, vol. 12, p. 74619–74632, 2024. [Online]. Available: https://doi.org/10.1109/ACCESS.2024.3403200

    work page doi:10.1109/access.2024.3403200 2024

  34. [34]

    C. C. McGeoch,Adiabatic Quantum Computation and Quantum Annealing: Theory and Practice. Springer, 2014. [Online]. Available: http://dx.doi.org/10.1007/978-3-031-02518-1

    work page doi:10.1007/978-3-031-02518-1 2014

  35. [36]

    Phase Gadget Synthesis for Shallow Circuits,

    [Online]. Available: https://arxiv.org/abs/1906.01734

    work page arXiv 1906

  36. [37]

    McArdle, T

    S. McArdle, X. Yuan, and S. C. Benjamin, “Variational quantum simulation of imaginary time evolution with applications in chemistry and beyond,”npj Quantum Information, vol. 5, no. 1, p. 75, 2019. [Online]. Available: https://doi.org/10.1038/s41534-019-0187-2

    work page doi:10.1038/s41534-019-0187-2 2019

  37. [38]

    A fast quantum mechanical algorithm for database search,

    L. K. Grover, “A fast quantum mechanical algorithm for database search,” inProceedings of the 28th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, 1996, p. 212–219. [Online]. Available: https://doi.org/10.1145/237814.237866 11

    work page doi:10.1145/237814.237866 1996

  38. [39]

    Mathematical foundation of quantum annealing,

    S. Morita and H. Nishimori, “Mathematical foundation of quantum annealing,”Journal of Mathematical Physics, vol. 49, no. 12, Dec

  39. [40]

    Available: http://dx.doi.org/10.1063/1.2995837

    [Online]. Available: http://dx.doi.org/10.1063/1.2995837

    work page doi:10.1063/1.2995837

  40. [41]

    On colouring the nodes of a network,

    R. L. Brooks, “On colouring the nodes of a network,”Mathematical Proceedings of the Cambridge Philosophical Society, vol. 37, no. 2, p. 194–197, Apr. 1941. [Online]. Available: http://dx.doi.org/10.1017/ S030500410002168X

    1941

  41. [42]

    Brèves communications. 0-1 optimization and non- linear programming,

    I. G. Rosenberg, “Brèves communications. 0-1 optimization and non- linear programming,”Revue Française D’Automatique, Informatique, Recherche Opérationnelle, vol. 6, no. 2, pp. 95–97, 1972. [Online]. Available: https://doi.org/10.1051/ro/197206V200951

    work page doi:10.1051/ro/197206v200951 1972

  42. [43]

    Compressed quadratization of higher order binary optimization problems,

    A. Mandal, A. Roy, S. Upadhyay, and H. Ushijima-Mwesigwa, “Compressed quadratization of higher order binary optimization problems,” inProceedings of the 17th ACM International Conference on Computing Frontiers. Association for Computing Machinery, May 2020, p. 126–131. [Online]. Available: http://doi.org/10.1145/3387902. 3392627

    work page doi:10.1145/3387902 2020

  43. [44]

    Zephyr topology of D-Wave quantum processors,

    K. Boothby, A. D. King, and J. Raymond, “Zephyr topology of D-Wave quantum processors,” D-Wave Systems Inc., White Paper 14-1056A-A, September 2021, D-Wave Technical Report Series. [Online]. Available: https://www.dwavesys.com/media/2uznec4s/ 14-1056a-a_zephyr_topology_of_d-wave_quantum_processors.pdf

    2021

  44. [45]

    Context-aware minor-embedding for quantum annealing processors,

    J. P. Pinilla Gomez, “Context-aware minor-embedding for quantum annealing processors,” Ph.D. dissertation, University of British Columbia, 2024. [Online]. Available: https://hdl.handle.net/2429/88270

    2024

  45. [46]

    A practical heuristic for finding graph minors,

    J. Cai, W. G. Macready, and A. Roy, “A practical heuristic for finding graph minors,” 2014. [Online]. Available: https://arxiv.org/abs/1406. 2741

    2014

  46. [47]

    Gilbert and S

    V . Gilbert and S. Louise,Quantum Annealers Chain Strengths: A Simple Heuristic to Set Them All. Springer, 2024, p. 292–306. [Online]. Available: https://doi.org/10.1007/978-3-031-63778-0_21

    work page doi:10.1007/978-3-031-63778-0_21 2024

  47. [48]

    Gagliolo and C

    M. Gagliolo and C. Legrand,Algorithm Survival Analysis. Springer, 2010, p. 161–184. [Online]. Available: https://doi.org/10. 1007/978-3-642-02538-9_7

    2010

  48. [49]

    Nonparametric estimation from incomplete observations,

    E. L. Kaplan and P. Meier, “Nonparametric estimation from incomplete observations,”Journal of the American Statistical Association, vol. 53, no. 282, p. 457–481, Jun. 1958. [Online]. Available: https://doi.org/10.1080/01621459.1958.10501452

    work page doi:10.1080/01621459.1958.10501452 1958

  49. [50]

    Survival analysis: Up from kaplan–meier–greenwood,

    O. S. Miettinen, “Survival analysis: Up from kaplan–meier–greenwood,” European Journal of Epidemiology, vol. 23, no. 9, p. 585–592, Sep

  50. [51]

    Available: https://doi.org/10.1007/s10654-008-9278-7

    [Online]. Available: https://doi.org/10.1007/s10654-008-9278-7

    work page doi:10.1007/s10654-008-9278-7

  51. [52]

    Comparing three generations of D-Wave quantum annealers for minor embedded combinatorial optimization problems,

    E. Pelofske, “Comparing three generations of D-Wave quantum annealers for minor embedded combinatorial optimization problems,” Quantum Science and Technology, vol. 10, no. 2, p. 025025, 2025. [Online]. Available: https://doi.org/10.1088/2058-9565/adb029

    work page doi:10.1088/2058-9565/adb029 2025

  52. [53]

    Embedding-aware noise modeling of quantum annealing,

    S.-G. Jeong, M. D. Cong, D.-I. Noh, Q.-V . Pham, and W.-J. Hwang, “Embedding-aware noise modeling of quantum annealing,” 2025. [Online]. Available: https://doi.org/10.48550/arXiv.2510.04594 12

    work page doi:10.48550/arxiv.2510.04594 2025