Pith. sign in

REVIEW 3 major objections 5 minor 28 references

A preconditioned inexact infeasible quantum interior point method for linear optimization

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

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

Pith's one-line read A predicted-optimal-partition preconditioner cuts the Newton-system condition number from quadratic to linear in 1/μ, giving a quantum IPM with Õ(n^{3.5}) QRAM queries and Õ(n³m) classical operations.

desk verdict Useful condition number analysis for a preconditioned II-QIPM, but Theorem 1's complexity claim rests on an unproven accuracy propagation from the solved system to the MNES residual. read the letter →

arxiv 2412.11307 v1 pith:FXEMMPBN submitted 2024-12-15 math.OC

Zeguan Wu , Xiu Yang , Tamás Terlaky This is my paper · ORCID
classification math.OC MSC 90C0590C5168Q12
keywords quantuminteriorpointmethodslinearoptimizationpreconditioningsystemalgorithmsinexactinfeasibleconditionnumberoptimalpartitionblock-encoding
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

An inexact infeasible quantum interior point method (II-QIPM) solves linear programs by replacing the classical Newton-system solver with a quantum linear system algorithm (QLSA) plus quantum state tomography (QTA). The bottleneck is that the condition number of the Newton system grows like the square of the reciprocal of the central-path parameter $\mu$, so the QLSA slows down badly near optimality. This paper tries to establish that a preconditioner built from a predicted optimal partition of the variables lowers that growth to $O(1/\mu)$, and that the resulting algorithm reaches an $\epsilon$-approximate solution in $\tilde O(n^{3.5}\bar\omega^{13}\epsilon^{-6}\kappa_A^5\|A\|_F^6(\|\hat A\|_2+\|\hat b\|_2))$ queries to QRAM plus $\tilde O(n^3 m)$ classical arithmetic operations. If the theorem is right, this gives the best accuracy dependence among inexact infeasible QIPMs and improves on the previous II-QIPM by a factor $O(\bar\omega^6/\epsilon^3)$ in the regime $\|A\|_F=O(\|A\|_2)$.

What carries the argument

The load-bearing object is the reduced preconditioned augmented system (RP-RAS), $\Xi\Delta y=\xi$, whose coefficient matrix is the normalized $(1,1)$ block of the preconditioned augmented system. The preconditioner is fixed by $\hat H=\hat h I$ with $\hat h=\gamma_1\sigma_0^2(A)/\omega^2$ and $\hat Z=B^T\hat H^{-1}B+D_1$; the paper shows $\sigma_0(Y)=\Omega(\mu)$, $\sigma_1(Y)\le 1+\frac{(1-\gamma_1)n+\gamma_1}{\gamma_1\hat h}\sigma_1^2(A)$, hence $\kappa(Y)=O(1/\mu)$, and $\kappa(\hat Z)=O(1/\mu)$. These bounds are what convert the QLSA and QTA accuracy requirements into the claimed per-iteration and total query complexities.

What would settle it

For a small linear program with a known optimal partition, implement Algorithm 2, record $\kappa(\Xi)$ at successive $\mu$ values, and test whether it grows like $O(1/\mu)$ rather than faster; also reconstruct the MNES residual after solving (RP-RAS) with the accuracies set by (7) and check whether $\|r\|_2\le\eta\sqrt{\mu/n}$ at every iteration. A counterexample to either scaling would refute Theorem 1's bound.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1. For an LO problem with integer data and a strictly feasible solution, Algorithm 2 produces an $\epsilon$-approximate solution, meaning $x^T s \le n\epsilon$ and $\|(r_p,r_d)\|_2\le\epsilon$, with $\tilde O(n^2\cdot n^{1.5}\bar\omega^{13}\epsilon^{-6}\kappa_A^5\|A\|_F^6(\|\hat A\|_2+\|\hat b\|_2))$ queries to QRAM and $\tilde O(n^3m)$ classical arithmetic operations. The argument works by partitioning the variables by size of $x[i]$, so the diagonal matrix $D$ splits into entries of order $\mu$ and entries of order $1/\mu$, applying the preconditioning reduction of [5] to the augmented system, and then solving the reduced preconditioned system (RP-RAS) with a QLSA followed by QTA. The proof's key quantitative step is bounding the singular values of the preconditioned coefficient matrices: $\sigma_0(Y)=\Omega(\mu)$ and $\kappa(Y)=O(1/\mu)$, with $\kappa(\hat Z)=O(1/\mu)$, which upgrades the conditioning from $O(1/\mu^2)$ to $O(1/\mu)$ and drives all subsequent query-count improvements.

Load-bearing premise

The complexity bound rests on the assertion, made only by "similar analysis shows", that setting QLSA and QTA accuracies by equation (7) — which was derived for the un-preconditioned modified normal equation system — also guarantees the residual bound $\|r\|_2\le\eta\sqrt{\mu/n}$ when the Newton direction is actually obtained from the preconditioned reduced system (RP-RAS).

Editorial extensions

If this is right

  • Per-iteration conditioning: the Newton linear systems solved by the QLSA have condition number $O(1/\mu)$ instead of $O(1/\mu^2)$, so the quantum solver's cost grows more slowly as the iterates approach optimality.
  • Total query complexity: reaching an $\epsilon$-approximate solution needs $\tilde O(n^2\cdot n^{1.5}\bar\omega^{13}\epsilon^{-6}\kappa_A^5\|A\|_F^6(\|\hat A\|_2+\|\hat b\|_2))$ queries to QRAM and $\tilde O(n^3 m)$ classical arithmetic operations.
  • Accuracy improvement: the dependence on $\epsilon$ is $O(\epsilon^{-6})$, quadratically better than the prior II-QIPM's $O(\epsilon^{-9})$ in the regime $\|A\|_F=O(\|A\|_2)$.
  • Dimension behavior: the method's dimension dependence is better than that of other inexact infeasible interior-point methods, keeping the quantum route attractive for large $n$ when QRAM is available.

Reading between the lines

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

  • If the missing error-propagation proof goes through, the same optimal-partition preconditioner should also reduce the condition-number blow-up in feasible QIPMs and in semidefinite-optimization QIPMs, where a similar $O(1/\mu^2)$ degradation appears; that is an extension, not a claim of this paper.
  • The partition rule in Definition 2 presumes the predicted partition is correct early enough; a natural stress test is whether a wrong guess before the optimal partition is revealed breaks Lemma 3.2's bounds or only delays the improvement.
  • Because the total classical cost is $\tilde O(n^3 m)$, the practical bottleneck shifts to building the block-encodings and to QRAM access; a natural next check is whether the same query count survives with bounded-precision QRAM.
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 Algorithm 2, a preconditioned inexact infeasible quantum interior-point method for linear optimization. It adapts the Chai–Toh preconditioning framework to the modified normal equations used by the II-QIPM of [19], partitions variables by Definition 2, solves the reduced preconditioned augmented system (RP-RAS) with a QLSA and a QTA, and claims that the condition number of the Newton linear systems improves from O(1/μ²) to O(1/μ). Theorem 1 asserts a per-iteration QRAM query complexity of Õ(n^1.5 ω̄^13 / ϵ^6 κ_A^5 ∥A∥_F^6 (∥Â∥_2 + ∥b̂∥_2)) and a total complexity of Õ(n^2 · (n^1.5 ...)) queries to QRAM plus Õ(n^3 m) classical arithmetic operations.

Significance. If the main theorem is correct, the paper would give the best accuracy dependence among II-QIPMs and would demonstrate a concrete preconditioning recipe with explicit block-encoding lemmas. The condition-number analysis in Lemmas 3.2–3.7 is largely structured and self-contained, and the block-encoding lemmas in Section 3.3 are a useful contribution. The central obstacle is that the quantum-solver accuracy is taken from equation (7), which was derived in Section 2.3 for solving (MNES) directly, and is applied without proof to the different system (RP-RAS) that Algorithm 2 actually solves. The final complexity claim is therefore not established as written.

major comments (3)
  1. [Section 3.4, proof of Theorem 1] The proof uses equation (7) as the required QLSA/QTA accuracy, but equation (7) was derived in Section 2.3 for the MNES residual r = M_MNES z − v_MNES, where the quantum state approximates the normalized solution of (MNES). Algorithm 2 line 7 solves the different system (RP-RAS), ΞΔy = ξ; the error produced by the QLSA/QTA is naturally an error in Δy, not in z. No inequality is derived that bounds the MNES residual (or the quantity ∥Sν∥∞ that enters Lemma 2.1) from the residual of (RP-RAS) or from the QTA error for that system. The sentence 'Similar analysis shows...' at the end of Section 3.4 is an assertion, not a proof, and it does not give the needed quantitative propagation factor. Because the 1/ϵ^6 factor and the convergence of Algorithm 2 both rest on this accuracy condition, this is a load-bearing gap.
  2. [Theorem 1, statement of residual] Theorem 1 states that the QLSA/QTA produce a solution satisfying ∥rhat^k∥2 ≤ η√(µk/n), but rhat^k is never defined. If rhat^k denotes the residual of (RP-RAS), Lemma 2.1 cannot be invoked because that lemma concerns the MNES residual r = M_MNES z − v_MNES. If rhat^k denotes the MNES residual, the proof must show how solving (RP-RAS) to a given QTA accuracy yields that bound. The definition and the corresponding error-propagation lemma should be supplied explicitly.
  3. [Theorem 1, displayed total complexity] The displayed total QRAM query count appears to be arithmetically inconsistent with the per-iteration count. The proof gives a per-iteration count containing a factor n^1.5 and then states the total as n^2 times that per-iteration factor, which is n^3.5. Since Algorithm 2 is an infeasible IPM and Section 1 states that infeasible IPMs require O(n log(1/ϵ)) iterations, the total would be n^2.5 up to log factors if the per-iteration count is correct. Please reconcile these exponents; the dimension-dependence claim in the abstract depends on this calculation.
minor comments (5)
  1. [Section 3.2, after Lemma 3.6] The sentence 'We have proved that the condition number of the coefficient matrix of (MNES) is O(1/µ)' is inaccurate; Lemma 3.6 bounds κ(Y) for Y = (P_c^{-1}K)_11, the coefficient matrix of (RP-RAS), not for the MNES coefficient matrix.
  2. [Equation (8)] The expression ∥(x, 0 × y, s)∥∞ is malformed; the middle component should be the m-dimensional zero vector, and it should be written as a vector tuple rather than '0 × y'.
  3. [Proof of Lemma 3.7 / Theorem 1] The lower bound σ1(Ẑ) ≥ 1/(2ĥ) uses a coordinate vector e1 and implicitly assumes that the first column of A is nonzero; with Assumption 1 this can be guaranteed by permuting columns, but the permutation should be stated explicitly.
  4. [Lemma 3.17] The displayed formula for C_RPRAS is hard to parse because of missing parentheses and the placement of the norm term; please rewrite it in a clearer standard form.
  5. [Section 1 and Section 3.4] The introduction claims an O(1/ϵ^3) speed-up over [19] without iterative refinement, while the later text states this improvement holds when ∥A∥_F = O(∥A∥_2); that condition should be attached to the introduction's claim.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular reduction; heavy reuse of self-cited [19] accuracy equation is a dependency concern, and the RP-RAS to MNES residual transfer is an omitted proof rather than circularity.

full rationale

The derivation chain is not circular in the sense defined in this review. The novel content--the Chai-Toh preconditioner adaptation, the condition-number bounds kappa(Y) = O(1/mu) and kappa(Zhat) = O(1/mu), and the block-encoding lemmas--is derived from matrix inequalities in Lemmas 3.2-3.7 and does not assume Theorem 1. The main theorem does import two results from the same group's prior II-QIPM [19]: Lemma 2.1 and equation (7), which sets the QLSA/QTA accuracy, and the proof of Theorem 4.2 used to bound ||v_MNES||_2/sqrt(mu). This is a load-bearing self-citation, but it is not circular under hard rule 4: the cited results are parameter-free, have stated assumptions (Assumptions 1-3 and the central-path neighborhood), and do not contain the preconditioned result being proved. They are prior derived statements, not fitted inputs. The genuine weakness is a correctness gap, not a circular reduction: Algorithm 2 solves (RP-RAS), while equation (7) was derived for the (MNES) residual, and the proof never derives the propagation from the residual of Xi Delta y = xi to ||r||_2 in (3). The sentence 'Similar analysis shows...' (Section 3.4) is an omitted proof, and Theorem 1 refers to an undefined rhat^k. But an omitted implication is the opposite of a self-referential one: the claimed bound does not follow by construction; it simply is not established. No enumerated circularity pattern is exhibited with a concrete equation-level reduction. Score 2 reflects the heavy but legitimate reliance on [19] and the acknowledged unproven accuracy transfer, not circularity.

Assumptions & free parameters 5 free parameters · 8 assumptions · 0 invented entities

The complexity theorem depends on standard IPM assumptions, a problem-dependent bound ω*, the QRAM model, and a specific partition rule. The most fragile item is the transfer of the accuracy equation (7) from the MNES system to the RP-RAS system, which is asserted without proof. No parameters are fitted to data and no new physical entities are postulated.

free parameters (5)
  • γ1
    Central path neighborhood parameter in Definition 2 and Algorithm 2; chosen in (0,1). Its exact value does not affect the asymptotic complexity.
  • η
    Inexact Newton direction residual tolerance parameter, chosen with 0 < η < β1; it sets the target accuracy in equation (7).
  • β1, β2
    Parameters with η < β1 < β2 < 1 controlling central path reduction and step acceptance; they are user-chosen constants.
  • γ2
    Initial neighborhood parameter set as max{1, ||(r_p^0, r_d^0)||_2 / μ^0}; it is determined by initial residuals rather than fitted.
  • ω*
    Bound on the infinity norm of all optimal solutions used to set x^0 and s^0 and to certify infeasibility; assumed known, no computation method is specified.
assumptions (8)
  • domain assumption Assumption 1: entries of A, b, c are integers
    Used in Theorem 1 to bound σ1(Ẑ) from below via integer data; standard in IPM complexity results.
  • domain assumption Assumption 2: strict feasibility, there exists (x,y,s) with Ax=b, A^T y+s=c, (x,s)>0
    Standard IPM assumption; ensures the central path exists; can be enforced by self-dual embedding.
  • domain assumption Assumption 3: A = [A_B A_N] with A_B nonsingular and κ(A_B) ≤ κ(A)
    Allows the M_B transformation and MNES formulation; authors argue it is not restrictive via a canonical form.
  • domain assumption QRAM access and efficient construction of submatrices and diagonal matrix powers
    Section 3.3 assumes data stored in QRAM and polylogarithmic block-encoding of constructed matrices; this is the standard QRAM model in QIPM papers.
  • domain assumption Known upper bound ω* on optimal solutions is available
    Algorithm 2 initializes (x^0,y^0,s^0) = (ω* e, 0, ω* e); without a known bound the algorithm cannot be started.
  • ad hoc to paper Partition rule Definition 2 places D entries in the claimed ranges
    The preconditioner and Lemmas 3.2-3.7 depend on this specific threshold x[i] ≥ sqrt([(1−γ1)n+γ1]μ); it is an algorithmic choice tailored to the analysis.
  • ad hoc to paper Equation (7) gives the correct QLSA/QTA accuracy for solving (RP-RAS)
    The theorem proof applies an accuracy formula derived for direct MNES solves to the preconditioned system solve without a full derivation; this is a gap in the proof.
  • ad hoc to paper Cost of finding a basis A_B is dominated by solving the Newton system
    Section 2.3 states this to ignore the basis construction cost; the authors say it is w.l.o.g. via reformulation but do not detail the reformulation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A preconditioned inexact infeasible quantum interior point method for linear optimization." pith.science (2026). https://pith.science/paper/FXEMMPBN

@misc{pith2026241211307,
  author       = {Pith},
  title        = {Pith review of: A preconditioned inexact infeasible quantum interior point method for linear optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FXEMMPBN}},
  note         = {Machine review of arXiv:2412.11307}
}
read the original abstract

Quantum Interior Point Methods (QIPMs) have been attracting significant interests recently due to their potential of solving optimization problems substantially faster than state-of-the-art conventional algorithms. In general, QIPMs use Quantum Linear System Algorithms (QLSAs) to substitute classical linear system solvers. However, the performance of QLSAs depends on the condition numbers of the linear systems, which are typically proportional to the square of the reciprocal of the duality gap in QIPMs. To improve conditioning, a preconditioned inexact infeasible QIPM (II-QIPM) based on optimal partition estimation is developed in this work. We improve the condition number of the linear systems in II-QIPMs from quadratic dependence on the reciprocal of the duality gap to linear, and obtain better dependence with respect to the accuracy when compared to other II-QIPMs. Our method also attains better dependence with respect to the dimension when compared to other inexact infeasible Interior Point Methods.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 24 canonical work pages

  1. [19]

    Efficient Use of Quantum Linear System Algorithms in Interior Point Methods for Linear Optimization

    M. Mohammadisiahroudi, R. Fakhimi, and T. Terlaky. Efficient use of quantum linear system algorithms in interior point methods for linear optimization. arXiv preprint arXiv:2205.01220, 2022

    work page Pith review arXiv 2022

  2. [1]

    Al-Jeiroudi and J

    G. Al-Jeiroudi and J. Gondzio. Convergence analysis of the inexact infeasible interior-point method for linear optimization. Journal of Optimization Theory and Applications , 141(2):231– 247, 2009

    work page 2009

  3. [2]

    Augustino, G

    B. Augustino, G. Nannicini, T. Terlaky, and L. F. Zuluaga. Quantum interior point methods for semidefinite optimization. Quantum, 7:1110, 2023

    work page 2023

  4. [3]

    Bertsimas and J

    D. Bertsimas and J. N. Tsitsiklis. Introduction to Linear Optimization . Athena Scientific, Belmont, MA, 1997

    work page 1997

  5. [4]

    J. R. Bunch and B. N. Parlett. Direct methods for solving symmetric indefinite systems of linear equations. SIAM Journal on Numerical Analysis , 8(4):639–655, 1971

    work page 1971

  6. [5]

    Chai and K.-C

    J.-S. Chai and K.-C. Toh. Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming. Computational Optimization and Applications , 36(2):221–247, 2007

    work page 2007

  7. [6]

    Chakraborty, A

    S. Chakraborty, A. Gily´ en, and S. Jeffery. The power of block-encoded matrix pow- ers: improved regression techniques via faster Hamiltonian simulation. arXiv preprint arXiv:1804.01973, 2018

    arXiv 2018

  8. [7]

    A. M. Childs, R. Kothari, and R. D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, 46(6):1920–1950, 2017

    work page 1920

Show all 28 references
  1. [8]

    D. E. Crabtree and E. V. Haynsworth. An identity for the Schur complement of a matrix. Proceedings of the American Mathematical Society, 22(2):364–366, 1969. 26

    1969

  2. [9]

    A. M. Dalzell, S. McArdle, M. Berta, P. Bienias, C.-F. Chen, A. Gily´ en, C. T. Hann, M. J. Kas- toryano, E. T. Khabiboulline, A. Kubica, et al. Quantum algorithms: A survey of applications and end-to-end complexities. arXiv preprint arXiv:2310.03011 , 2023

    arXiv

  3. [10]

    R. S. Dembo, S. C. Eisenstat, and T. Steihaug. Inexact Newton methods. SIAM Journal on Numerical Analysis, 19(2):400–408, 1982

    1982

  4. [11]

    Gily´ en, Y

    A. Gily´ en, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and be- yond: exponential improvements for quantum matrix arithmetics [full version]. arXiv preprint arXiv:1806.01838, 4, 2018

    2018 arXiv

  5. [12]

    G¨ uler, D

    O. G¨ uler, D. den Hertog, C. Roos, T. Terlaky, and T. Tsuchiya. Degeneracy in interior point methods for linear programming: a survey. Annals of Operations Research, 46:107–138, 1993

    1993

  6. [13]

    A. W. Harrow, A. Hassidim, and S. Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103(15):150502, 2009

    2009

  7. [14]

    R. A. Horn and C. R. Johnson. Matrix Analysis . Cambridge University Press, Cambridge, UK, 2012

    2012

  8. [15]

    Karmarkar

    N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4:373–395, 1984

    1984

  9. [16]

    C. T. Kelley. Iterative Methods for Linear and Nonlinear Equations . SIAM, Philadelphia, PA, 1995

    1995

  10. [17]

    Kerenidis and A

    I. Kerenidis and A. Prakash. A quantum interior point method for LPs and SDPs. ACM Transactions on Quantum Computing , 1(1):1–32, 2020

    2020

  11. [18]

    Mohammadisiahroudi, F

    M. Mohammadisiahroudi, F. Fakhimi, Z. Wu, and T. Terlaky. An inexact feasible interior point method for linear optimization with high adaptability to quantum computers. Technical Report: 21T-006, Lehigh University , 2021

    2021

  12. [20]

    R. D. Monteiro and J. W. O’Neal. Convergence analysis of a long-step primal-dual infeasible interior-point LP algorithm based on iterative linear solvers. Georgia Institute of Technology, 2003

    2003

  13. [21]

    Nesterov and A

    Y. Nesterov and A. Nemirovskii. Interior-Point Polynomial Algorithms in Convex Program- ming. SIAM, Philadelphia, PA, 1994

    1994

  14. [22]

    P´ olik and T

    I. P´ olik and T. Terlaky. Interior point methods for nonlinear optimization. In G. Di Pillo and F. Schoen, editors, Nonlinear Optimization, volume 1989, pages 215–276, Berlin, Heidelberg,

    1989

  15. [23]

    F. A. Potra. An infeasible-interior-point predictor-corrector algorithm for linear programming. SIAM Journal on Optimization , 6(1):19–32, 1996. 27

    1996

  16. [24]

    C. Roos. A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM Journal on Optimization , 16(4):1110–1136, 2006

    2006

  17. [25]

    C. Roos, T. Terlaky, and J.-P. Vial. Theory and Algorithms for Linear Optimization: An Interior Point Approach . John Wiley & Sons, Chichester, 1997

    1997

  18. [26]

    R. L. Smith. Some interlacing properties of the Schur complement of a Hermitian matrix. Linear Algebra and Its Applications , 177:137–144, 1992

    1992

  19. [27]

    van Apeldoorn, A

    J. van Apeldoorn, A. Cornelissen, A. Gily´ en, and G. Nannicini. Quantum tomography using state-preparation unitaries. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1265–1318. SIAM, 2023

    2023

  20. [28]

    Z. Wu, M. Mohammadisiahroudi, B. Augustino, X. Yang, and T. Terlaky. An inexact feasible quantum interior point method for linearly constrained quadratic optimization.Entropy, 25(2), 2023. 28

    2023

Pith tools

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