Pith. sign in

REVIEW 3 major objections 5 minor 42 references

QUBO Refinement: Achieving Superior Precision through Iterative Quantum Formulation with Limited Qubits

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

Pith's one-line read An iterative QUBO refinement algorithm using two qubits per variable at each step is claimed to solve a linear system to up to 16 decimal places, far beyond the two-decimal precision of existing QUBO solvers.

desk verdict The per-step QUBO arithmetic is correct and the two-qubit refinement trick is neat, but the 16-decimal claim is not in the data and the paper's own Fig. 4 undercuts the convergence argument. read the letter →

arxiv 2411.16138 v1 pith:AVDE5CYK submitted 2024-11-25 quant-ph

classification quant-ph
keywords QUBOiterativerefinementquantumannealinglinearsystemsprecisionqubitencodingnumericalcomputinghybridsolver
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proposes an iterative scheme for solving linear systems on quantum annealers. Instead of encoding the full precision of each variable in one large binary expansion, the algorithm uses two qubits per variable at each step, finds the minimum of a QUBO, moves the search center to that minimum, shrinks the step size, and repeats. The paper claims this reaches up to 16 decimal places of accuracy on a linear system with irrational coefficients, whereas existing QUBO simulators and hybrid solvers were limited to about two decimal places. The value of the claim is that precision becomes a function of iteration count rather than qubit count, which would make high-precision quantum optimization practical on today's limited hardware. The paper also shows a failure case for an ill-conditioned matrix, where the center jumps far from the solution and the algorithm needs many iterations.

What carries the argument

The machinery is an iterative refinement loop on the QUBO formulation of least squares. For each variable the paper writes $x_i = c_i + 2^\ell(q_{i,\ell}^+ - q_{i,\ell}^-)$, where $q^+,q^-$ are the two qubits at scale $\ell$ and $c_i$ is the current center. The least-squares objective $\|Ax-b\|^2 = x^T A^T A x - 2b^T A x + b^T b$ is expanded into a QUBO in the qubits, solved, and the resulting minimizer becomes the new center; $\ell$ is then decreased and the process repeats. The loop is what carries the argument: precision is accumulated by recentering rather than by lengthening the binary expansion, so the coefficients in the QUBO matrix stay within the physical accuracy of the annealer at every step.

What would settle it

Run the algorithm on the paper's $2\times2$ irrational system and record the error at each $\ell$; if the error does not go below $10^{-16}$ as $\ell$ decreases past $-40$, the 16-decimal-place claim is not supported. Alternatively, apply the algorithm to a matrix with condition number 129.44 and check whether the center jumps to $(-16384,16384)$ as in the paper's Fig. 4 and whether the promised many iterations eventually terminate.

Watch

Extended reading notes

Core claim

The paper's central claim is that an iterative QUBO refinement algorithm can solve a linear system $Ax=b$ to up to 16 decimal places while using only two qubits per variable at each step. The authors demonstrate this on a $2\times2$ system with irrational matrix entries $(\sqrt2, -\sqrt3, \sqrt5, \sqrt7)$ and a specially chosen $b$, running 101 iterations from $\ell=20$ down to $\ell=-40$; the error between the QUBO minimum and the true solution falls from $3.22\times10^3$ at $\ell=15$ to $3.27\times10^{-13}$ at $\ell=-40$. A second experiment with six qubits per variable reaches the same solution in 39 iterations. The paper presents this as overcoming the physical limitations of bias and coupler accuracy, because each step's QUBO has a smaller dynamic range than a single monolithic encoding would.

Load-bearing premise

The load-bearing premise is that the global minimum of the QUBO at each coarse step lies in the basin of the true solution, so recentering onto that minimum and shrinking the step size converges; the paper's own condition-number-129.44 example, where the center jumps to $(-16384,16384)$, shows this premise can fail without a stated bound on the many iterations needed.

Editorial extensions

If this is right

  • Any QUBO-based numerical solver can trade qubit count per variable for iteration count, making high-precision quantum optimization feasible with small logical registers at each step.
  • The reported error table shows roughly two orders of magnitude of accuracy gained per five steps of $\ell$, from $10^{-2}$ at $\ell=0$ down to $10^{-13}$ at $\ell=-40$.
  • With a hybrid solver handling up to about two million variables, the paper estimates the algorithm can target linear systems up to roughly $333{,}333\times333{,}333$ using the paper's reported $3n$-qubit accounting.
  • Using six qubits per variable instead of two cuts the required iterations from 101 to 39, so the method exposes a direct qubits-versus-iterations trade-off.
  • The method inherits a condition-number sensitivity: for a matrix with condition number 129.44 the greedy center update can jump away from the solution, and the paper reports that many iterations are then needed.

Reading between the lines

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

  • A testable extension is to replace the greedy recentering with a backtracking or wider-search step when the condition number is high; the paper identifies the jump failure but does not specify a recovery strategy.
  • The two-qubit representation is essentially a one-bit signed-digit encoding, and the paper itself notes the representation is redundant; comparing this encoding with balanced or redundant number systems could reduce the many-iterations cases without adding qubits.
  • The accuracy ceiling of 16 digits is tied to the hardware's QUBO coefficient precision, so a natural stress test is to solve a system whose exact solution requires coefficients beyond that range and check whether iterative refinement still converges.
  • The paper does not benchmark against classical iterative refinement of a floating-point solve; a direct comparison would isolate whether the quantum step contributes accuracy or just a recentering that a classical presolve could do.
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.

Referee Report

3 major / 5 minor

Summary. The paper proposes an iterative QUBO refinement algorithm for solving linear systems. Each variable is represented at each step by two qubits corresponding to x_i = 2^l(q_i^+ - q_i^-), the QUBO is solved on a coarse grid, the center is moved to the minimizer, and the exponent l is decreased. The authors test the method on a 2x2 linear system with irrational coefficients using a hybrid QPU solver and claim accuracy up to 16 decimal places while using only a constant number of qubits per variable. The paper also discusses a failure mode for an ill-conditioned matrix in Section IV.

Significance. If the claims were fully substantiated, the algorithm would be a practical way to obtain high precision from QUBO solvers with limited qubit counts, which is an important problem for quantum optimization. The per-step QUBO equations (15)-(17) are algebraically correct for a single exponent, and the provided GitHub repository strengthens reproducibility. However, the headline precision claim is not supported by the reported data, and the greedy refinement procedure has no convergence guarantee; Figure 4 shows a concrete instability where the center jumps far from the solution. As presented, the contribution is a heuristic with a promising numerical example rather than a validated high-precision method.

major comments (3)
  1. [Section III, Table 1] The paper's headline claim of 'up to 16 decimal places' is not demonstrated by the experimental results. The smallest error reported in Table 1 is 3.27e-13 at m = -40, which is approximately 13 decimal digits, not 16. The abstract and Section III explicitly state that solutions of up to 16 decimal places were determined, but no table entry or described run shows an error at or below 1e-16. The 101-iteration run mentioned in Section III is not fully tabulated; the last shown exponent is -40, so the reader cannot verify the 16-digit claim. The authors should either provide the full iteration history or a plot of error versus iteration and should temper the abstract and introduction claims to match the reported data.
  2. [Section IV, Fig. 4] The algorithm's convergence is not proven, and Fig. 4 provides a concrete counterexample to the implicit basin-containment assumption. In the 2x2 example with condition number 129.44, the center jumps from (0,0) to (-16384,16384) when the exponent decreases from 2^17 to 2^16, far from the true solution. Because Section II-B decreases the step size l unconditionally after each QUBO solve, a jump of this kind can place the center outside the basin of attraction at a scale that the subsequent finer grids cannot correct. The text acknowledges that 'many iterations' are needed but gives no bound, no condition-number threshold, and no convergence analysis. The statement in Section IV that 'the proposed algorithm can always determine a solution if there exists one' is therefore unsupported and is not consistent with the behavior shown in Fig. 4.
  3. [Section II-B, Eqs. (18)-(19)] The core iterative step assumes that the global minimizer of the QUBO on the coarse grid at level l lies in the same monotone basin as the continuous solution, so that recentering at that minimum and shrinking l converges. No such property is established. The algorithm's free parameters - the starting exponent m, the exponent decrement (here 1 or 3), and the number of qubits per variable - are chosen ad hoc for the test problem (m=20, decrement 1), and the paper does not explain how these should be set for a general linear system or how they affect the attainable precision. Without a proof or a systematic parameter study, the robustness of the method for general problems is not established.
minor comments (5)
  1. [Section II-B, Eq. (19)] The notation O is used for the previous center point but is not defined; it should be a vector such as c_l to avoid confusion with the origin.
  2. [Sections II-B and III] The paper states both '3n qubits' (Section II-B) and 'two qubits for each xi' (Section IV), while Section III uses 'four qubits are used when calculating a 2 x 2 matrix.' The relationship between these statements should be clarified.
  3. [Table 1] The header 'THE NUMBER OF QUBIT COMBINATIONS OBTAINED WHEN THE STEP OF x IS EXPRESSED IN INTERVALS OF 5' is unclear, and the column '#Occurrences' is not defined in the text.
  4. [Section II-B, after Eq. (17)] The sentence introducing y_i and c_i should explicitly define C = (c_1, ..., c_n) and replace the ad hoc notation to make the substitution x = y + C consistent with the subsequent formulas.
  5. [Figure 1 caption] The phrase 'The algorithm can obtain zero when the eccentricity e of the curve is 0 < e < 1' is vague; it should explain what becomes zero and how this relates to the algorithm's behavior.

Circularity Check

0 steps flagged · score 2.0 of 10

No construction-level circularity: the iterative refinement is validated against a known analytic solution, and the central error reduction is not fitted; the 16-decimal headline is self-cited and unsupported by Table 1, but it is not derived from the algorithm's own inputs.

full rationale

The core derivation is self-contained: the QUBO least-squares encoding (Eqs. 12-14), the two-qubit representation x_i = 2^l(q^+ - q^-), and the center-shift iteration using the residual b - Ac are explicit algebraic transformations, and the final error in Table 1 is measured against the closed-form solution x = (1024*pi, -32*e) of the linear system (20). No parameter is fitted to the target solution, and no equation defines the claimed precision in terms of the precision being claimed. The main concerns are correctness and support, not circularity: the smallest reported error is 3.27e-13, not 1e-16; Fig. 4 shows a case where the center jumps to (-16384, 16384), contradicting the claim that the algorithm 'can always determine a solution'; and the '16 decimal places' claim relies on the self-cited QPU precision of reference [30] rather than on an error bound derived in this paper. These issues lower confidence but do not make the derivation reduce to its own inputs. Score 2 reflects the minor self-citations and self-referential precision framing without a construction-level circular step.

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

The central claim rests on the solver's reliability and on the unproven convergence of the greedy grid refinement, plus hand-picked parameters (starting exponent, step decrement, qubits per variable). No new physical entities are introduced.

free parameters (3)
  • Starting exponent m = 20
    Chosen to cover the magnitude of the expected solution (~10^3); not fitted to the solution but a hand-picked algorithm parameter.
  • Exponent decrement step = 1 (first experiment), 3 (second experiment)
    The algorithm reduces the exponent by 1 or 3 at each iteration; the choice affects number of iterations and accuracy.
  • Qubits per variable = 2 in first experiment, 6 in second
    The number of binary variables per unknown in the QUBO at each iteration; a design choice.
assumptions (3)
  • domain assumption The hybrid/QPU solver returns the true global minimum of each small QUBO problem.
    The algorithm's movement depends on the solver finding the global minimum energy at each step; this is not verified and is known to be unreliable on real annealers.
  • ad hoc to paper The greedy step-by-step reduction of the exponent converges to the solution for the tested linear system.
    No proof is given; the paper's own ill-conditioned example (Fig. 4) shows the greedy search can move to a wrong point.
  • domain assumption The objective function Ax-b is well-conditioned enough that the coarse grid tracks the global minimum.
    The paper's success depends on the contour eccentricity being close to 0, which is not true for general matrices.

how reviews work

0 comments
Cite this review

Pith. "Pith review of QUBO Refinement: Achieving Superior Precision through Iterative Quantum Formulation with Limited Qubits." pith.science (2026). https://pith.science/paper/AVDE5CYK

@misc{pith2026241116138,
  author       = {Pith},
  title        = {Pith review of: QUBO Refinement: Achieving Superior Precision through Iterative Quantum Formulation with Limited Qubits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AVDE5CYK}},
  note         = {Machine review of arXiv:2411.16138}
}
read the original abstract

In the era of quantum computing, the emergence of quantum computers and subsequent advancements have led to the development of various quantum algorithms capable of solving linear equations and eigenvalues, surpassing the pace of classical computers. Notably, the hybrid solver provided by the D-wave system can leverage up to two million variables. By exploiting this technology, quantum optimization models based on quadratic unconstrained binary optimization (QUBO) have been proposed for applications, such as linear systems, eigenvalue problems, RSA cryptosystems, and CT image reconstruction. The formulation of QUBO typically involves straightforward arithmetic operations, presenting significant potential for future advancements as quantum computers continue to evolve. A prevalent approach in these developments is the binarization of variables and their mapping to multiple qubits. These methods increase the required number of qubits as the range and precision of each variable increase. Determining the optimal value of a QUBO model becomes more challenging as the number of qubits increases. Furthermore, the accuracies of the existing Qiskit simulator, D-Wave system simulator, and hybrid solver are limited to two decimal places. Problems arise because the qubits yielding the optimal value for the QUBO model may not necessarily correspond to the solution of a given problem. To address these issues, we propose a new iterative algorithm. The novel algorithm sequentially progresses from the highest to the lowest exponent in binarizing each number, whereby each number is calculated using two variables, and the accuracy can be computed up to a maximum of 16 decimal places.

Figures

Figures reproduced from arXiv: 2411.16138 by the authors.

Figure 2
Figure 2. [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 39 canonical work pages

  1. [1]

    Noisy intermediate-scale quantum algorithms

    Kishor B, et al. Noisy intermediate-scale quantum algorithms. Reviews of Modern Physics 2022:94:015004

  2. [2]

    Simulating physics with computers

    Feynman RP. Simulating physics with computers . Int J Theor Phys 1982:21:467–488

  3. [3]

    Quantum computation and quantum information

    Nielsen MA, Chuang IL. Quantum computation and quantum information. Phys. Today 2001:54(2):60

  4. [4]

    Polynomial-time algorithms for prime factorization and discrete l ogarithms on a quantum computer

    Shor PW. Polynomial-time algorithms for prime factorization and discrete l ogarithms on a quantum computer . SIAM Review 1999:41:303–32. https://doi.org/10.1137/S0036144598347011. Figure 4. Example of inefficient iterative QUBO formulation algorithm . The red star is the solution of the linear system, and the two equilibrium lines of the same color repres...

  5. [5]

    The dashed line indicates the movement of the center

    Each circle represents the center that the new algorithm is searching for at each step. The dashed line indicates the movement of the center. This example may find points farther from the solution than in the previous step because the point of minimum energy at a particular step is the point with the minimum vertical distance on a straight line through th...

  6. [6]

    A fast quantum mechanical algorithm for database search

    Grover LK. A fast quantum mechanical algorithm for database search. In: Annual ACM Symposium on Theory of Computing 1996, p. 212– 9

  7. [7]

    Universal quantum simulators

    Lloyd S. Universal quantum simulators. Science 1996:273:1073–8 https://www.science.org/doi/pdf/10.1126/science.273.5278.1073

  8. [8]

    Quantum machine learning

    Biamonte J, Wittek P, Pancotti N, Rebentrost P, Wiebe N, Lloyd S. Quantum machine learning. Nature 2017:549:195–202

Show all 42 references
  1. [9]

    Quantum machine learning with D-wave quantum computer

    Hu F, Wang B-N Wang N, Wang C. Quantum machine learning with D-wave quantum computer. Quantum Engineering 2019:1(2)

  2. [10]

    Quantum Engineering 2 2020:e34

    Zhang Y, Ni Q, Recent advances in quantum machine learning . Quantum Engineering 2 2020:e34

  3. [11]

    Integrating machine learning algorithms with quantum annealing solvers for online fraud detection

    Wang H, Wang W, Liu Y, Alidaee B. Integrating machine learning algorithms with quantum annealing solvers for online fraud detection. IEEE Access 2022:10:75908–17

  4. [12]

    Quantum machine learning: A tutorial

    Martí n-Guerrero JD, Lamata L. Quantum machine learning: A tutorial. Neurocomputing 2022:470:457-461

  5. [13]

    Decomposition algorithms for solving np-hard problems on a quantum annealer

    Pelofske E, Hahn G, Djidjev H. Decomposition algorithms for solving np-hard problems on a quantum annealer. Journal of Signal Processing Systems 2021:93:405–420

  6. [14]

    Efficiently embedding QUBO problems on adiabatic quantum computers

    Date P, Patton R, Schuman C, Potok T. Efficiently embedding QUBO problems on adiabatic quantum computers . Quantum Information Processing 2019:18:1–31

  7. [15]

    QUBO formulations of three NP problems

    Mahasinghe A, Fernando V, Samarawickrama P. QUBO formulations of three NP problems. Journal of Information and Optimization Sciences 2021:42:1625–1648

  8. [16]

    Classifying and benchmarking quantum annealing algorithms based on quadratic unconstrained binary optimization for solving np-hard problems

    Jiang JR, Chu C-W. Classifying and benchmarking quantum annealing algorithms based on quadratic unconstrained binary optimization for solving np-hard problems. IEEE Access 2023:99:1

  9. [17]

    Support vector machines on the d -wave quantum annealer

    Willsch D, Willsch M, De Raedt H, Michielsen K. Support vector machines on the d -wave quantum annealer . Computer Physics Communications 2020:248:107006

  10. [18]

    In: IGARSS 2020-2020 IEEE International Geoscience and Remote Sensing Symposium IEEE

    Cavallaro G, Willsch D, Willsch M, Michielsen K, Riedel M Approaching remote sensing image classification with ensembles of support vector machines on the d-wave quantum annealer. In: IGARSS 2020-2020 IEEE International Geoscience and Remote Sensing Symposium IEEE. 2020, p.1973–1976

  11. [19]

    QUBO formulations for training machine learning models

    Arthur D, Date P, Pusey-Nazzaro L. QUBO formulations for training machine learning models. Scientific Reports 2021:11:1–10

  12. [20]

    Adiabatic quantum linear regression

    Date P, Potok T. Adiabatic quantum linear regression . Scientific Reports 2021:11:21905

  13. [21]

    Balanced k -means clustering on an adiabatic quantum computer

    Arthur D, Date P. Balanced k -means clustering on an adiabatic quantum computer. Quantum Information Processing 2021:20:1–30

  14. [22]

    Distance-based clustering using QUBO formulations

    Matsumoto N, Hamakawa Y, Tatsumura K, Kudo K. Distance-based clustering using QUBO formulations. Scientific Reports 2022:12:2669

  15. [23]

    Quantum algorithm for linear systems of equations

    Harrow AW, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 2009:103:150502

  16. [24]

    Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations

    Ambainis A. Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations . In: 29th International Symposium Theoretical Asp ects of Computer Science (STACS 2012), 2012, p.636–47

  17. [25]

    Quantum algorithm for systems of linear equations with exponentially improved dependence on precision

    Childs AM, Kothari R, Somma RD. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing 2017:46:1920–1950

  18. [26]

    Quantum linear system algorithm for dense matrices

    Wossnig L, Zhao Z, Prakash A. Quantum linear system algorithm for dense matrices. Physical Review Letters 2018:120:050502

  19. [27]

    Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing

    Subaşı Y, Somma RD, Orsucci D. Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing . Physical Review Letters 2019:122:060504

  20. [28]

    A survey on HHL algorithm: From theory to application in quantum machine learning

    Bojia D, et al. A survey on HHL algorithm: From theory to application in quantum machine learning. Physics Letters A 2020:384(24):126595

  21. [29]

    QUBO formulations for numerical quantum computing

    Jun K. QUBO formulations for numerical quantum computing . 2021, arXiv preprint arXiv:2106.10819v4

  22. [30]

    HUBO formulations for solving the eigenvalue problem

    Jun K, Lee H. HUBO formulations for solving the eigenvalue problem. Results in Control and Optimization 2023:11:100222

  23. [31]

    HUBO and QUBO models for prime factorization

    Jun K, Lee H. HUBO and QUBO models for prime factorization . Scientific Reports 2023:13:10080

  24. [32]

    A highly accurate quantum optimization algorithm for ct image reconstruction based on sinogram patterns

    Jun K. A highly accurate quantum optimization algorithm for ct image reconstruction based on sinogram patterns . Scientific Reports 2023:13:14407

  25. [33]

    Parallel quantum annealing

    Pelofske, E, Hahn G, Djidjev HN. Parallel quantum annealing . Scientific Reports 2022:12(1):4499

  26. [34]

    Solving larger optimization problems using parallel quantum annealing

    Pelofske E, Hahn G, Djidjev HN. Solving larger optimization problems using parallel quantum annealing. 2022 arXiv preprint arXiv:2205.12165

  27. [35]

    Quantum annealing: The fastest route to quantum computation? The European Physical Journal Special Topics 2015:224(1):75-88

    Laumann CR., et al. Quantum annealing: The fastest route to quantum computation? The European Physical Journal Special Topics 2015:224(1):75-88

  28. [36]

    Larger sparse quadratic assignment problem optimization using quantum annealing and a bit - flip heuristic algorithm

    Kuramata, M, Katsuki R, Nakata K. Larger sparse quadratic assignment problem optimization using quantum annealing and a bit - flip heuristic algorithm. In: 2021 IEEE 8th International Conference on Industrial Engineering and Applications (ICIEA); 2021

  29. [37]

    QUBO Formulations for a System of Linear Equations

    Jun K. QUBO Formulations for a System of Linear Equations. Results in Control and Optimization 2024: 100380

  30. [38]

    Range dependent Hamiltonian Algorithm for numerical QUBO formulation

    Lee H, Jun K. Range dependent Hamiltonian Algorithm for numerical QUBO formulation. arXiv preprint arXiv:2202.07692; 2022

  31. [39]

    The unconstrained binary quadratic programming problem: a survey

    Kochenberger G, Hao J-K, Glover F, Lewis M, Lu Z, Wang H. The unconstrained binary quadratic programming problem: a survey . Journal of Combinatorial Optimization 2014:28:58–81

  32. [40]

    A tutorial on formulating and using QUBO models

    Glover F, Kochenberger G, Du Y. A tutorial on formulating and using QUBO models. arXiv preprint arXiv:1811.11538; 2018

  33. [41]

    A QUBO formulation of minimum multicut problem instances in trees for d - wave quantum annealers

    Cruz-Santos W, Venegas -Andraca SE, Lanzagorta M. A QUBO formulation of minimum multicut problem instances in trees for d - wave quantum annealers. Scientific Reports 2019:9:1–12

  34. [42]

    Quantum Information Processing 2022:21:141.Transl

    Willsch D, Willsch M, Gonzalez Calaza CD, Jin F, De Raedt H, Svensson M, Michielsen K, Benchmarking advantage and D -wave 2000Q quantum annealers with exact cover problems. Quantum Information Processing 2022:21:141.Transl. J. Magn. Japan, vol. 2, pp. 740–741, August 1987 [Dig...

Pith tools

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