pith. sign in

arxiv: 2412.15572 · v2 · pith:DLCFKOZUnew · submitted 2024-12-20 · 🧮 math.OC · quant-ph

Classical Combinatorial Optimization Scaling for Random Ising Models on 2D Heavy-Hex Graphs

Elijah Pelofske , Andreas B\"artschi , Stephan Eidenbenz This is my paper

Pith reviewed 2026-05-23 07:24 UTC · model grok-4.3

classification 🧮 math.OC quant-ph
keywords Ising modelheavy-hex graphcombinatorial optimizationsimulated annealingGurobitime-to-solutionclassical scalingQAOA
0
0 comments X

The pith

Sparse Ising models on heavy-hex graphs allow classical exact solvers to scale linearly or quadratically up to 100,000 variables

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

The paper measures runtimes of classical algorithms on random Ising models placed on heavy-hex graphs, both with and without added geometrically local cubic terms. Gurobi finds exact solutions in linear or weakly quadratic average-case time even at the largest sizes tested, while simulated annealing shows exponential time-to-solution scaling when cubic terms are absent. The authors attribute the efficiency to the low connectivity of the graphs. A reader would care because these models were chosen to match the constraints of near-term quantum hardware and algorithms such as QAOA. The results indicate that quantum advantage will require shifting to denser interaction graphs.

Core claim

Because of the sparsity of these Ising models, the classical algorithms are able to find optimal solutions efficiently even for large instances (i.e. 100,000 variables). The Ising models both with and without geometrically local cubic terms exhibit average-case linear-time or weakly quadratic scaling when solved exactly using Gurobi, and the Ising models with no cubic terms show evidence of exponential-time Time-to-Solution scaling when sampled using simulated annealing.

What carries the argument

Sparsity of the interaction graph in Ising models on heavy-hex lattices, which limits variable dependencies and permits efficient exact solving by Gurobi

If this is right

  • These sparse problems remain classically tractable at scales relevant to current hardware
  • Quantum algorithms require more densely connected problems to demonstrate practical advantage over classical methods
  • The choice of classical solver strongly affects reported scaling and must be optimized in any quantum-classical comparison
  • Different classical algorithms exhibit exponentially different runtimes on identical instances

Where Pith is reading between the lines

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

  • Hardware-native problems on present quantum devices may stay easy for classical exact solvers
  • Systematic tests on graphs with increasing density could locate the crossover to classical hardness
  • Benchmark studies should routinely include multiple classical solvers to avoid underestimating classical performance

Load-bearing premise

The random instances of Ising models on heavy-hex graphs are representative of the combinatorial optimization problems that near-term quantum algorithms and hardware would actually encounter.

What would settle it

Demonstration that Gurobi solve times on the same family of heavy-hex Ising instances grow exponentially with the number of variables once sizes exceed 100,000

Figures

Figures reproduced from arXiv: 2412.15572 by Andreas B\"artschi, Elijah Pelofske, Stephan Eidenbenz.

Figure 1
Figure 1. Figure 1: FIG. 1: Examples of heavy-hex graph structures with 100 nodes (left), 1000 nodes (middle), and 2000 nodes (right). [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2: Normalized random sampling energy distributions, shown as density histograms (y-axis) for increasing [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3: Gurobi runtime scaling (log scale y-axis) as a function of Ising model problem size (x-axis), where the [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4: Gurobi runtime scaling (log scale y-axis) as a function of Ising model problem size (x-axis) for the instances [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5: Simulated annealing TTS scaling (log scale y-axis) as a function of Ising model problem size (x-axis) for the [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6: Optimal solution magnetization (y-axis) as a function of system size (x-axis), for the two cubic term [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗
read the original abstract

Motivated by near term quantum computing hardware limitations, combinatorial optimization problems that can be addressed by current quantum algorithms and noisy hardware with little or no overhead are used to probe capabilities of quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA). In this study, a specific class of near term quantum computing hardware defined combinatorial optimization problems, Ising models on heavy-hex graphs both with and without geometrically local cubic terms, are examined for their classical computational hardness via empirical computation time scaling quantification. Specifically the Time-to-Solution metric using the classical heuristic simulated annealing is measured for finding optimal variable assignments (ground states), as well as the time required for the optimization software Gurobi to find an optimal variable assignment. Because of the sparsity of these Ising models, the classical algorithms are able to find optimal solutions efficiently even for large instances (i.e. $100,000$ variables). The Ising models both with and without geometrically local cubic terms exhibit average-case linear-time or weakly quadratic scaling when solved exactly using Gurobi, and the Ising models with no cubic terms show evidence of exponential-time Time-to-Solution scaling when sampled using simulated annealing. These findings point to the necessity of developing and testing more complex, namely more densely connected, optimization problems in order for quantum computing to ever have a practical advantage over classical computing. Our results are another illustration that different classical algorithms can indeed have exponentially different running times, thus making the identification of the best practical classical technique important in any quantum computing vs. classical computing comparison.

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 / 1 minor

Summary. The paper examines the classical tractability of random Ising models defined on heavy-hex graphs (with and without geometrically local cubic terms) by empirically measuring solve times with Gurobi and time-to-solution (TTS) with simulated annealing on instances up to 100,000 variables. It reports linear or weakly quadratic average-case scaling for exact Gurobi solutions in both cases and exponential TTS scaling for simulated annealing on the quadratic (no-cubic) models, attributing the efficiency to sparsity and arguing that denser problems are required to demonstrate quantum advantage over classical methods.

Significance. If the reported scalings are reproducible, the work supplies concrete average-case evidence that hardware-native sparse Ising models remain classically easy even at large sizes, thereby strengthening the case for using denser benchmark ensembles when comparing quantum heuristics such as QAOA against classical solvers. The explicit demonstration that different classical algorithms can exhibit exponentially different runtimes on the same ensemble is also a useful methodological reminder.

major comments (2)
  1. [Methods / Instance Generation] The central scaling claims rest on an ensemble of randomly generated instances, yet the manuscript provides no description of the instance-generation procedure (distribution of J_ij and h_i couplings, probability and placement of cubic terms, graph embedding details) nor the number of instances per size or random seeds used. Without these details the reported linear/weakly-quadratic versus exponential distinction cannot be independently verified or assessed for possible post-hoc selection bias.
  2. [Results / Scaling Analysis] The scaling plots and TTS fits lack error bars, confidence intervals, or goodness-of-fit statistics (e.g., R² or p-values for the exponential model). This omission is load-bearing because the distinction between “linear/weakly quadratic” and “exponential” regimes is the primary empirical result used to support the conclusion about quantum-advantage benchmarks.
minor comments (1)
  1. [Abstract and Results] The abstract states both “linear-time or weakly quadratic scaling” for Gurobi; the main text should clarify whether the quadratic regime appears only for the cubic-term instances or for both ensembles.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive comments, which highlight opportunities to strengthen the reproducibility and statistical presentation of our empirical results. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Methods / Instance Generation] The central scaling claims rest on an ensemble of randomly generated instances, yet the manuscript provides no description of the instance-generation procedure (distribution of J_ij and h_i couplings, probability and placement of cubic terms, graph embedding details) nor the number of instances per size or random seeds used. Without these details the reported linear/weakly-quadratic versus exponential distinction cannot be independently verified or assessed for possible post-hoc selection bias.

    Authors: We agree that the original manuscript lacked sufficient detail on instance generation. In the revised version we will add a dedicated subsection describing the full procedure: the uniform random distributions chosen for the quadratic couplings J_ij and linear fields h_i, the probability and geometric placement rules for the cubic terms on the heavy-hex lattice, the embedding of the logical graph onto the hardware-native connectivity, the number of independent instances generated at each problem size, and the random seeds used for reproducibility. These additions will enable independent verification and eliminate concerns about selection bias. revision: yes

  2. Referee: [Results / Scaling Analysis] The scaling plots and TTS fits lack error bars, confidence intervals, or goodness-of-fit statistics (e.g., R² or p-values for the exponential model). This omission is load-bearing because the distinction between “linear/weakly quadratic” and “exponential” regimes is the primary empirical result used to support the conclusion about quantum-advantage benchmarks.

    Authors: We acknowledge the absence of error bars and fit statistics in the original plots. The revised manuscript will include error bars (standard deviation across instances) on all scaling curves. We will also report quantitative goodness-of-fit measures, specifically R² values and, where appropriate, p-values or confidence intervals for the linear, quadratic, and exponential models fitted to the Gurobi and simulated-annealing data. These additions will provide the statistical support needed to substantiate the reported scaling distinctions. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper contains no mathematical derivations, fitted predictions, uniqueness theorems, or self-citations that bear load on the central claims. It generates random Ising instances on heavy-hex graphs, runs Gurobi (exact MIP solver) and simulated annealing, and directly measures wall-clock times and TTS scaling on those instances up to 100k variables. All reported results are empirical measurements on an explicitly defined random ensemble; no step reduces by construction to its own inputs or to prior self-authored results. The conclusion that these sparse models are classically tractable follows immediately from the observed linear/weakly-quadratic Gurobi scaling and exponential SA TTS, without any intermediate modeling assumptions that could introduce circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is an empirical benchmarking study reporting runtime measurements; the abstract introduces no mathematical derivations, fitted parameters, background axioms, or new postulated entities.

pith-pipeline@v0.9.0 · 5810 in / 1255 out tokens · 27456 ms · 2026-05-23T07:24:39.349505+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms

    quant-ph 2025-09 conditional novelty 5.0

    Systematic numerical study of QAOA parameter transfer on heavy-hex Ising models with local cubic terms shows transferred angles from small instances yield improving expectation values up to 49 layers on instances up t...

Reference graph

Works this paper leans on

58 extracted references · 58 canonical work pages · cited by 1 Pith paper · 3 internal anchors

  1. [1]

    This order reduction is performed using the heuristic order reduction method in the Python 3 module dimod[45]

    The cubic ZZZ terms in the higher order Ising models are order-reduced by introducing auxiliary variables, and quadratic interactions with those auxiliary variables, that preserve the optimal solution(s) to the original problem. This order reduction is performed using the heuristic order reduction method in the Python 3 module dimod[45]. This order reduct...

    work page

  2. [2]

    In order to convert variable states from spins into binary, with the higher order terms, the Python 3 module dimod is also used, which introduces additional higher order terms

    Formulate the polynomial as a binary Integer Linear Program (ILP), where the variable states of the optimization problem are first converted into binary states. In order to convert variable states from spins into binary, with the higher order terms, the Python 3 module dimod is also used, which introduces additional higher order terms. The higher order te...

    work page 2000

  3. [3]

    A Quantum Approximate Optimization Algorithm

    E. Farhi, J. Goldstone, and S. Gutmann, A Quantum Approximate Optimization Algorithm (2014), arXiv:1411.4028 [quant-ph]. 9

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  4. [4]

    Hadfield, Z

    S. Hadfield, Z. Wang, B. O’Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, From the Quantum Approximate Opti- mization Algorithm to a Quantum Alternating Operator Ansatz, Algorithms 12, 34 (2019)

    work page 2019

  5. [5]

    M. P. Harrigan, K. J. Sung, M. Neeley, K. J. Satzinger, F. Arute, K. Arya, J. Atalaya, J. C. Bardin, R. Barends, S. Boixo, M. Broughton, B. B. Buckley, D. A. Buell, B. Burkett, N. Bushnell, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, S. Demura, A. Dunsworth, D. Eppens, A. Fowler, B. Foxen, C. Gidney, M. Giustina, R. Graff, S. Habegger, A. Ho, S....

    work page 2021

  6. [6]

    Shaydulin, C

    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, E...

    work page doi:10.1126/sciadv.adm6761 2024

  7. [7]

    Wurtz and D

    J. Wurtz and D. Lykov, Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs, Phys. Rev. A 104, 052419 (2021)

    work page 2021

  8. [8]

    The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case, April 2020

    E. Farhi, D. Gamarnik, and S. Gutmann, The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case (2020), arXiv:2004.09002 [quant-ph]

    work page arXiv 2020

  9. [9]

    Farhi, D

    E. Farhi, D. Gamarnik, and S. Gutmann, The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples (2020), arXiv:2005.08747 [quant-ph]

    work page arXiv 2020

  10. [10]

    Farhi, J

    E. Farhi, J. Goldstone, S. Gutmann, and L. Zhou, The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size, Quantum 6, 759 (2022)

    work page 2022

  11. [11]

    Boulebnane and A

    S. Boulebnane and A. Montanaro, Solving boolean satisfiability problems with the quantum approximate optimization algorithm (2022), arXiv:2208.06909 [quant-ph]

    work page arXiv 2022

  12. [12]

    Montanaro and L

    A. Montanaro and L. Zhou, Quantum speedups in solving near-symmetric optimization problems by low-depth QAOA (2024), arXiv:2411.04979 [quant-ph]

    work page arXiv 2024

  13. [13]

    Preskill, Quantum computing in the nisq era and beyond, Quantum 2, 79 (2018)

    J. Preskill, Quantum computing in the nisq era and beyond, Quantum 2, 79 (2018)

    work page 2018

  14. [14]

    Tasseff, T

    B. Tasseff, T. Albash, Z. Morrell, M. Vuffray, A. Y. Lokhov, S. Misra, and C. Coffrin, On the emerging potential of quantum annealing hardware for combinatorial optimization, Journal of Heuristics 30, 325 (2024)

    work page 2024

  15. [15]

    R. S. Andrist, M. J. A. Schuetz, P. Minssen, R. Yalovetzky, S. Chakrabarti, D. Herman, N. Kumar, G. Salton, R. Shaydulin, Y. Sun, M. Pistoia, and H. G. Katzgraber, Hardness of the maximum-independent-set problem on unit-disk graphs and prospects for quantum speedups, Physical Review Research 5, 10.1103/physrevresearch.5.043277 (2023)

    work page doi:10.1103/physrevresearch.5.043277 2023

  16. [16]

    Pelofske, A

    E. Pelofske, A. B¨ artschi, and S. Eidenbenz, Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers, in High Performance Computing (Springer Nature Switzerland, 2023) p. 240–258

    work page 2023

  17. [17]

    Pelofske, A

    E. Pelofske, A. B¨ artschi, and S. Eidenbenz, Short-Depth QAOA circuits and Quantum Annealing on Higher-Order Ising Models, npj Quantum Information 10.1038/s41534-024-00825-w (2024)

    work page doi:10.1038/s41534-024-00825-w 2024

  18. [18]

    Pelofske, A

    E. Pelofske, A. B¨ artschi, L. Cincio, J. Golden, and S. Eidenbenz, Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs, npj Quantum Information 10.1038/s41534-024-00906-w (2024), arXiv:2312.00997 [quant-ph]

    work page doi:10.1038/s41534-024-00906-w 2024

  19. [19]

    H. G. Katzgraber, F. Hamze, and R. S. Andrist, Glassy chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines, Phys. Rev. X 4, 021008 (2014)

    work page 2014

  20. [20]

    Y. Kim, A. Eddins, S. Anand, K. X. Wei, E. Van Den Berg, S. Rosenblatt, H. Nayfeh, Y. Wu, M. Zaletel, K. Temme, et al. , Evidence for the utility of quantum computing before fault tolerance, Nature 618, 500 (2023)

    work page 2023

  21. [21]

    Kechedzhi, S

    K. Kechedzhi, S. V. Isakov, S. Mandr` a, B. Villalonga, X. Mi, S. Boixo, and V. Smelyanskiy, Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments, arXiv preprint (2023), arXiv:2306.15970

    work page arXiv 2023

  22. [22]

    Beguˇ si´ c and G

    T. Beguˇ si´ c and G. K.-L. Chan, Fast classical simulation of evidence for the utility of quantum computing before fault tolerance, arXiv preprint (2023), arXiv:2306.16372

    work page arXiv 2023

  23. [23]

    Tindall, M

    J. Tindall, M. Fishman, M. Stoudenmire, and D. Sels, Efficient tensor network simulation of IBM’s kicked Ising experiment, arXiv preprint (2023), arXiv:2306.14887

    work page arXiv 2023

  24. [24]

    Beguˇ si´ c, J

    T. Beguˇ si´ c, J. Gray, and G. K.-L. Chan, Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance, arXiv preprint (2023), arXiv:2308.05077

    work page arXiv 2023

  25. [25]

    H.-J. Liao, K. Wang, Z.-S. Zhou, P. Zhang, and T. Xiang, Simulation of IBM’s kicked Ising experiment with Projected Entangled Pair Operator, arXiv preprint (2023), arXiv:2308.03082

    work page arXiv 2023

  26. [26]

    M. S. Rudolph, E. Fontana, Z. Holmes, and L. Cincio, Classical surrogate simulation of quantum systems with LOWESA, arXiv preprint (2023), arXiv:2308.09109

    work page arXiv 2023

  27. [27]

    Patra, S

    S. Patra, S. S. Jahromi, S. Singh, and R. Orus, Efficient tensor network simulation of IBM’s largest quantum processors, arXiv preprint (2023), arXiv:2309.15642

    work page arXiv 2023

  28. [28]

    Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual (2024)

    work page 2024

  29. [29]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt Jr, and M. P. Vecchi, Optimization by simulated annealing, science 220, 671 (1983)

    work page 1983

  30. [30]

    Crosson and A

    E. Crosson and A. W. Harrow, Simulated quantum annealing can be exponentially faster than classical simulated annealing, in 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2016) p. 714–723. 10

    work page 2016

  31. [31]

    Palubeckis, Multistart tabu search strategies for the unconstrained binary quadratic optimization problem, Annals of Operations Research 131, 259 (2004)

    G. Palubeckis, Multistart tabu search strategies for the unconstrained binary quadratic optimization problem, Annals of Operations Research 131, 259 (2004)

    work page 2004

  32. [32]

    Z. Zhu, A. J. Ochoa, and H. G. Katzgraber, Efficient cluster algorithm for spin glasses in any space dimension, Physical Review Letters 115, 10.1103/physrevlett.115.077201 (2015)

    work page doi:10.1103/physrevlett.115.077201 2015

  33. [33]

    J., Hertzberg, J

    C. Chamberland, G. Zhu, T. J. Yoder, J. B. Hertzberg, and A. W. Cross, Topological and Subsystem Codes on Low-Degree Graphs with Flag Qubits, Physical Review X 10, 10.1103/physrevx.10.011022 (2020)

    work page doi:10.1103/physrevx.10.011022 2020

  34. [34]

    Het´ enyi and J

    B. Het´ enyi and J. R. Wootton, Creating Entangled Logical Qubits in the Heavy-Hex Lattice with Topological Codes, PRX Quantum 5, 040334 (2024)

    work page 2024

  35. [35]

    & Bermudez, A

    C. Benito, E. L´ opez, B. Peropadre, and A. Bermudez, Comparative study of quantum error correction strategies for the heavy-hexagonal lattice (2025), arXiv:2402.02185 [quant-ph]

    work page arXiv 2025

  36. [36]

    S. V. Barron, D. J. Egger, E. Pelofske, A. B¨ artschi, S. Eidenbenz, M. Lehmkuehler, and S. Woerner, Provable bounds for noise-free expectation values computed from noisy samples, Nature Computational Science 10.1038/s43588-024-00709-1 (2024), arXiv:2312.00733 [quant-ph]

    work page doi:10.1038/s43588-024-00709-1 2024

  37. [37]

    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 annealers for nontrivial binary optimization problems (2024), arXiv:2406.01743 [quant-ph]

    work page arXiv 2024

  38. [38]

    C. C. McGeoch, K. Chern, P. Farr´ e, and A. K. King, A comment on comparing optimization on D-Wave and IBM quantum processors (2024), arXiv:2406.19351 [quant-ph]

    work page arXiv 2024

  39. [39]

    A. A. Hagberg, D. A. Schult, and P. J. Swart, Exploring Network Structure, Dynamics, and Function using NetworkX, in 7th Python in Science Conference SciPy’08 (2008) pp. 11–15

    work page 2008

  40. [40]

    Lukic, A

    J. Lukic, A. Galluccio, E. Marinari, O. C. Martin, and G. Rinaldi, Critical thermodynamics of the two-dimensional ±j ising spin glass, Phys. Rev. Lett. 92, 117202 (2004)

    work page 2004

  41. [41]

    C. K. Thomas, D. A. Huse, and A. A. Middleton, Zero- and low-temperature behavior of the two-dimensional ±j ising spin glass, Phys. Rev. Lett. 107, 047203 (2011)

    work page 2011

  42. [42]

    Achterberg, R

    T. Achterberg, R. E. Bixby, Z. Gu, E. Rothberg, and D. Weninger, Presolve reductions in mixed integer programming, INFORMS Journal on Computing 32, 473 (2020)

    work page 2020

  43. [43]

    Achterberg1´ u, R

    T. Achterberg1´ u, R. E. Bixby, Z. Gu, E. Rothberg, and D. Weninger, Multi-row presolve reductions in mixed integer programming (2014)

    work page 2014

  44. [44]

    E. R. Bixby, M. Fenelon, Z. Gu, E. Rothberg, and R. Wunderling, MIP: Theory and practice—closing the gap, in IFIP Conference on System Modeling and Optimization (Springer, 1999) pp. 19–49

    work page 1999

  45. [45]

    Z. Gu, G. L. Nemhauser, and M. W. Savelsbergh, Sequence independent lifting in mixed integer programming, Journal of Combinatorial Optimization 4, 109 (2000)

    work page 2000

  46. [46]

    Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization, Operations Research Proceedings 10.1007/978-3-319-89920-6 (2018), arXiv:1803.03455

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/978-3-319-89920-6 2018

  47. [47]

    https://github.com/dwavesystems/dimod

    work page

  48. [48]

    R. J. Forrester and N. Hunt-Isaak, Computational comparison of exact solution methods for 0-1 quadratic programs: Recommendations for practitioners, Journal of Applied Mathematics 2020, 1 (2020)

    work page 2020

  49. [49]

    Padberg, The boolean quadric polytope: Some characteristics, facets and relatives, Mathematical Programming 45, 139 (1989)

    M. Padberg, The boolean quadric polytope: Some characteristics, facets and relatives, Mathematical Programming 45, 139 (1989)

    work page 1989

  50. [50]

    Glover, Improved linear integer programming formulations of nonlinear integer problems, Management Science 22, 455 (1975)

    F. Glover, Improved linear integer programming formulations of nonlinear integer problems, Management Science 22, 455 (1975)

    work page 1975

  51. [51]

    Sherali and C

    H. Sherali and C. Smith, An improved linearization strategy for zero-one quadratic programming problems, Optimization Letters 1, 33 (2007)

    work page 2007

  52. [52]

    A note on QUBO instances defined on Chimera graphs

    S. Dash, A note on QUBO instances defined on Chimera graphs (2013), arXiv:1306.1202 [math.OC]

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  53. [53]

    https://github.com/dwavesystems/dwave-neal

    work page

  54. [54]

    T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, and M. Troyer, Defining and detecting quantum speedup, Science 345, 420–424 (2014)

    work page 2014

  55. [55]

    D. S. Steiger, T. F. Rønnow, and M. Troyer, Heavy Tails in the Distribution of Time to Solution for Classical and Quantum Annealing, Phys. Rev. Lett. 115, 230501 (2015)

    work page 2015

  56. [56]

    Pearson, A

    A. Pearson, A. Mishra, I. Hen, and D. A. Lidar, Analog errors in quantum annealing: doom and hope, npj Quantum Information 6, 10.1038/s41534-020-00297-8 (2020)

    work page doi:10.1038/s41534-020-00297-8 2020

  57. [57]

    Virtanen, R

    P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, ˙I. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen,...

    work page 2020

  58. [58]

    Note that here we are measuring the net magnetization of the single optimal solution found, per problem instance, found by the Gurobi software

    work page