Pith. sign in

REVIEW 4 major objections 4 minor 36 references

A quantum dual logarithmic barrier method for linear optimization

T0 review · 4 major / 4 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 The paper claims that an inexact feasible dual logarithmic barrier method, with Newton systems solved by quantum linear system algorithms and iterative refinement, reaches a $\zeta$-optimal solution in $O(\sqrt{n}\log(n\mu_0/\zeta))$…

desk verdict New dual-only quantum IPM with real potential, but Lemma 3.2's false inequality breaks the central iteration bound; needs major revision before it can be trusted. read the letter →

arxiv 2412.15977 v1 pith:SDHGEF2Q submitted 2024-12-20 math.OC

Zeguan Wu , Pouya Sampourmahani , Mohammadhossein Mohammadisiahroudi , Tamás Terlaky This is my paper · ORCID
classification math.OC MSC 90C0590C5181P68
keywords quantuminteriorpointmethodduallogarithmicbarrierlinearoptimizationsystemalgorithmtomographyiterativerefinementinexactNewtonsublinearcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper tries to establish that the dual logarithmic barrier method for linear optimization can be made quantum without sacrificing feasibility or the classical iteration count. It replaces each exact Newton step by an inexact direction produced by a quantum linear system algorithm (QSVT) plus quantum tomography, and shows that the iterates still converge quadratically toward the central path while remaining dual feasible. The main results are an iteration bound of $O(\sqrt{n}\log(n\mu_0/\zeta))$ and, after a dual-only iterative refinement scheme, a quantum query complexity of $\widetilde{O}(m\sqrt{n}\kappa_0)$ to QRAM. For problems with $n \ge \vartheta m^2$, the query count becomes sublinear in the number of variables, which would make large 'tall' linear programs accessible to quantum speedup without the stringent tallness condition required by the closest prior work.

What carries the argument

The object carrying the argument is the normal equation system (NES) of the dual logarithmic barrier method, $(AS^{-2}A^T)\Delta y = \mu^{-1} r_p$ with $r_p = b - \mu A S^{-1}e$, together with the proximity measure $\delta(s,\mu)=\|s^{-1}\Delta s\|_2$ that measures how far the current dual slack $s$ is from the $\mu$-center. The algorithm builds the NES at each iteration, uses QSVT to prepare a quantum state proportional to its solution, reads a classical unit vector with quantum tomography, and rescales it by $\lambda_*$ to form the inexact Newton step. The two technical workhorses are Lemma 3.2, which bounds the next proximity measure $\delta(s_+,\mu_+)^2$ in terms of $\delta(s,\mu)^4$ plus error terms, and Theorem 3.3, which turns that bound into the $4\sqrt{n}\log(n\mu_0/\zeta)$ iteration count. Iterative refinement works through a dual-only refining problem (DIR) whose initial feasible point is built from the previous solution, so every re-solve keeps the condition number of the Newton systems bounded by the initial condition number.

What would settle it

Set up a small linear program with $n=2$ and a starting point on its central path with $\delta(s,\mu)=0.5$, add an inexact direction whose relative error is exactly $0.1\delta(s,\mu)$ as the paper allows, and compute $\delta(s_+,\mu_+)$ directly; if any coordinate of $(s^{-1}\Delta s)^2$ comes out below $0.25$, or if $\delta(s_+,\mu_+)$ exceeds $0.5$, the $O(\sqrt{n})$ iteration claim is not supported by the proof as written.

Watch

Extended reading notes

Core claim

In the paper's own terms, the central discovery is that the normal equation system $(AS^{-2}A^T)\Delta y = \mu^{-1}(b - \mu A S^{-1} e)$ can be solved inexactly by a quantum linear system algorithm and the resulting direction still drives the dual logarithmic barrier method to the central path quadratically. The proximity measure $\delta(s,\mu)=\|s^{-1}\Delta s\|_2$ is shown to contract quadratically in each step, and with $\theta=1/(4\sqrt{n})$ the proximity bound stays below $0.5$ for the whole run, yielding at most $\lceil 4\sqrt{n}\log(n\mu_0/\zeta)\rceil$ iterations. The rescaling of the unit vector output by quantum tomography is chosen as $\lambda_* = r_p^T \bar{\Delta y}/(\mu \|S^{-1}A^T\bar{\Delta y}\|_2^2)$, and the proof that the resulting error is small enough uses a trigonometric bound involving $\kappa(AS^{-2}A^T)$. Iterative refinement is then used to remove the dependence of the condition number on the final precision, giving the $\widetilde{O}(m\sqrt{n}\kappa_0)$ query bound.

Load-bearing premise

The proof that the method keeps its iterates close to the central path depends on Lemma 3.2's assertion that a certain combination of the squared Newton step and the error term has nonnegative inner product; that assertion rests on the inequality $(s^{-1}\Delta s)^2 \ge 0.25 e$, which the text does not justify.

Editorial extensions

If this is right

  • Each quantum iteration needs only a coarse direction solve: the tomography accuracy is tied to the current proximity measure, so the per-iteration quantum cost does not grow as the target accuracy tightens.
  • For problems with $m \le \sqrt{n}$, the total QRAM query count $\widetilde{O}(m\sqrt{n}\kappa_0)$ is sublinear in $n$, and the classical cost $O(m n^{1.5}\log(n\mu_0/\zeta))$ beats the plain dual barrier method's $O(n^{2.5})$ for large $n$.
  • Because dual feasibility is preserved by the barrier framework, the algorithm avoids the normal-equation preprocessing or orthogonal-subspace modification that earlier quantum interior point methods need to stay primal feasible.
  • The dual-only iterative refinement reaches an exact optimal solution through $O(\log\zeta/\log\hat{\zeta})$ low-precision solves, so the quantum cost depends on the initial condition number rather than on $1/\zeta$.
  • Under the tallness condition $n \ge \vartheta m^2$, the algorithm improves on the closest prior quantum IPM, which only achieves a sublinear query count under the far stronger condition $n \ge \gamma m^{10}$.

Reading between the lines

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

  • Assuming the main iteration bound holds, the dual-only refinement template should extend to semidefinite optimization, where the dual barrier is a matrix function and the NES becomes a Schur complement; a numerical check would be to run the inexact scheme on small SDO instances and monitor whether $\delta$ remains below $0.5$ with the allowed relative error $0.1\delta$.
  • A direct experiment on random tall LOs with $m \le \sqrt{n}$, comparing the quantum-style directions (simulated by adding noise with relative norm $0.1\delta$) against exact Newton directions, would show how much of the theory's allowed error is actually needed in practice; the true tolerance may be much looser.
  • The sublinear query claim is contingent on QRAM and block encoding; a concrete prediction is that a fault-tolerant implementation would spend most of its runtime on the $\kappa_0$ factor, so preconditioning the input matrix $A$ appears to be the main lever for a practical speedup.
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

4 major / 4 minor

Summary. The paper proposes an inexact-feasible dual logarithmic barrier method for linear optimization, in which the normal equation system at each iteration is solved by a quantum linear system algorithm (QSVT) followed by quantum tomography, and iterative refinement is used to reduce the dependence on the final precision. The central theoretical claims are an O(sqrt(n) log(n mu0/zeta)) iteration complexity for the inexact method (Theorem 3.3), a per-iteration QRAM query bound based on QSVT/QTA (Theorem 3.7), and a final query complexity tilde-O(m sqrt(n) kappa0) for the iterative-refinement variant (Theorem 3.13). The paper also claims that for problems with n >= m^2 the quantum complexity has a sublinear dependence on dimension.

Significance. If the main results were established, the paper would make a useful contribution to quantum interior-point methods: a dual-only framework that avoids the primal-feasibility modifications needed in some prior QIPMs, a local quadratic convergence result for inexact directions (Theorem 3.1), and a detailed quantitative comparison with existing classical and quantum IPMs in Tables 1 and 2. The iterative-refinement idea is sensible and the presentation of the normal-equation structure is mostly clear. However, the central iteration-complexity theorem rests on Lemma 3.2, whose proof contains a false componentwise inequality; the per-iteration quantum complexity is imported from external sources without proof; and the Section 3.2 accuracy analysis contains algebraic errors. These are load-bearing issues for the main claims, so the paper cannot be accepted in its current form.

major comments (4)
  1. [Lemma 3.2, Eq. (2)] The proof of Lemma 3.2 contains an invalid lower bound. With a = s^{-1}Delta s and b = s^{-1}E^C_{Delta s}, the hypotheses give |a_i| <= delta(s,mu) <= 0.5 and ||b||_2 <= 0.1 delta(s,mu) <= 0.05, hence a_i^2 <= 0.25, not a_i^2 >= 0.25. Equation (2) nevertheless estimates the vector e - a^2 - (a-e)b componentwise from below and multiplies by (0.5)^2 e, which amounts to assuming a_i^2 >= 0.25. The claimed intermediate conclusion h^T(e-h) >= 0 is false: for n = 1, a = 0.05, b = 0.005, all assumptions hold and h = a^2 + (a-1)b = -0.00225 < 0, so h(e-h) < 0. Lemma 3.2 is the step that keeps delta(s,mu) <= 0.5 in Theorem 3.3 and yields the O(sqrt(n) log(n mu0/zeta)) iteration count; without it the central complexity claim is not proven.
  2. [Section 3.2, Proposition 3.4] The derivation of the quantum accuracy condition has an algebraic error. Let u = S^{-1}A^T Delta y and v = S^{-1}A^T E^Q_{Delta y}. The exact expression is cos(psi) = (||u||^2/||Delta y|| + u^T v) / (||u|| ||u/||Delta y|| + v||), not the displayed fraction with denominator ||Delta y|| ||u|| ||v|| + ||u||^2. The subsequent sufficient condition 0.005 ||Delta y||_{AS^{-2}A^T} >= 1.995 ||Delta y|| ||S^{-1}A^T Delta y|| ||S^{-1}A^T E^Q_{Delta y}|| and the comparison with 1/sqrt(kappa(AS^{-2}A^T)) do not follow; the displayed equality with denominator ||AS^{-2}A^T|| ||Delta y||_2^2 also omits a square root and has the wrong power of ||Delta y||. The final bound on ||E^Q_{Delta y}|| may be correct, but the proof as written does not establish Proposition 3.4.
  3. [Theorem 3.7 and Section 3.3] The per-iteration QRAM complexity in Theorem 3.7 is imported from Mohammadisiahroudi [2024] (a PhD thesis) without proof, and the uniform condition-number bound kappa(A(S^{(k)})^{-2}A^T) = O(kappa0) for all iterative-refinement iterations is taken from Mohammadisiahroudi et al. [2023a] (to appear). These external results are load-bearing for the final query complexity tilde-O(m sqrt(n) kappa0) in Theorem 3.13. Since they are not established in this manuscript and at least one is not yet published, the paper should either prove these statements or state them explicitly as assumptions with precise hypotheses.
  4. [Abstract and Section 3.2] The claim of sublinear query complexity under n >= m^2 is not supported by the stated bound. If m = Theta(sqrt(n)), then tilde-O(m sqrt(n) kappa0) is tilde-O(n kappa0), which is linear in n. Sublinearity requires m = o(sqrt(n)), i.e. n/m^2 -> infinity, not merely n >= m^2. In addition, the phrase 'quadratically more constraints than variables' appears to reverse the roles of n and m; the condition used elsewhere is n >= m^2, meaning variables are quadratically more numerous than constraints. The abstract and Table 2 should be corrected accordingly.
minor comments (4)
  1. [Theorem 3.3, proof] The termination condition is written as n mu0 (1 - theta)^K >= (1 - theta) epsilon; since 1 - theta < 1, the left side decreases in K, so the inequality should presumably be <=. As written it does not imply the stated ceiling for K.
  2. [Lemma 3.2] The proof repeatedly uses the loose bound ||s^{-1}E|| <= 0.5 although the hypothesis gives ||s^{-1}E|| <= 0.1 delta(s,mu) <= 0.05; using the tighter bound would make the estimates clearer, though it does not by itself repair Eq. (2).
  3. [Table 1 and surrounding text] The text states that Apers and Gribling [2023] has 'O(n^7.5) complexity', but Table 1 lists several query counts for their algorithm; the derivation of n^7.5 should be given, or the statement should be removed.
  4. [Section 2.4] The accuracy parameter epsilon is used for the IPM target, while the QLSP error is denoted epsilon_QLSP; later the QTA error and the quantum-direction error are denoted differently. Using distinct symbols throughout would improve readability.

Circularity Check

2 steps flagged · score 4.0 of 10

The quantum query-complexity claims rest on two load-bearing same-group citations, while the classical DLBM iteration analysis is independent.

  1. self citation load bearing [Section 3.2, proof of Theorem 3.7 (per-iteration QSVT-NES complexity).]
    "According to Mohammadisiahroudi [2024], since the normal equation can be rewritten as (AS−1)(AS−1)T ∆y = (AS−1) 1/µ (Sx0−µe), the normal equation systems can be solved using quantum singular value transformation (QSVT) Gilyén [2019], Gilyén et al. [2019] with the complexity of ~On,κ(AS−1),1/ε (κ(AS−1)‖AS−1‖F). Furthermore, iterative refinement can mitigate the linear dependence on ‖AS−1‖F into polylogarithmic dependence Mohammadisiahroudi [2024]."

    The paper's per-iteration quantum query count mκ²(AS−1), and hence the total query counts in Theorems 3.8 and 3.13, are not derived in this paper. They are imported verbatim from coauthor Mohammadisiahroudi's PhD thesis, with no proof reproduced and no independent verification supplied. The central quantum speedup claim therefore reduces at its key step to a same-author citation rather than to the present analysis: if that cited complexity were removed, Theorem 3.7 would have no proof in this manuscript.

  2. self citation load bearing [Section 3.3, paragraph immediately before Lemma 3.12 (uniform condition-number bound for iterative refinement).]
    "Thus, we can conclude that all NES systems in iterations of Algorithm 3 have the O(κ0) uniform condition number bound Mohammadisiahroudi et al. [2023a]."

    The headline query complexity ~O(m√n κ0) in Theorem 3.13 is obtained only by replacing per-iteration condition numbers κ(A(S^(k))−2A^T) with the initial κ0. That uniform bound is asserted solely by reference to a same-group paper with overlapping authors, without stating the cited theorem's hypotheses or proving it here. The complexity claim's condition-number dependence is therefore imported from the authors' own prior work; absent that citation, the stated O(m√n κ0) bound does not follow from the equations developed in this paper.

full rationale

The classical inexact-feasible DLBM layer is not definitionally circular: the proximity measure, quadratic convergence analysis, and O(√n log(nµ0/ζ)) iteration bound are developed internally from Roos et al.'s classical theory, and no fitted quantity is renamed as a prediction. The circularity burden is concentrated in the quantum layer, where the QSVT-NES per-iteration complexity and the uniform O(κ0) bound for iterative refinement are load-bearing imports from same-group publications rather than results proved or verified here. These are significant self-citations, but they are not reductions by definition: the cited works are prior theorems, not the present paper's own outputs, and the core iteration analysis retains independent content. Separately, Lemma 3.2's proof appears to use the componentwise lower bound (s−1Δs)² ≥ 0.25e, which does not follow from |s−1Δs| ≤ 0.5; that is a correctness gap in the written derivation of δ(s+,µ+)², but it is not a circularity and is not counted in the score here. Overall, score 4 reflects load-bearing same-group citations while acknowledging the independent classical derivation.

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

The algorithm relies on several same-group, partially unpublished results for its core complexity statements and on an invalid inequality in the convergence proof. No new physical entities are introduced.

free parameters (3)
  • θ (barrier update step) = 1/(4√n)
    Hand-chosen to make the proximity invariant δ ≤ 0.5 hold in Theorem 3.3; the proof's constants depend on this value.
  • QLSA/QTA accuracy constant = 0.005/1.995 ≈ 0.0025
    Hand-chosen to ensure sin ψ ≤ 0.1 in Proposition 3.4.
  • residual error threshold = 0.1
    Hand-chosen in Lemma 3.2 to bound the inexactness; larger values would break the proof.
assumptions (5)
  • domain assumption Interior Point Condition (Assumption 1): existence of (x0, y0, s0) with Ax0=b, A^T y0+s0=c, (x0,s0)>0
    Required for any feasible IPM; if it fails, an embedding is needed but not analyzed here.
  • domain assumption Access to QRAM and efficient block encoding of the Newton matrix
    Assumed in Section 2.4; QRAM construction remains experimental.
  • standard math QSVT and QTA complexities from Gilyén et al. and van Apeldoorn et al. are correct
    External results used as black boxes.
  • ad hoc to paper Uniform condition-number bound O(κ0) for all NES systems during iterative refinement
    Imported from Mohammadisiahroudi et al. [2023a], a same-group paper that is only 'to appear', and not proven here.
  • ad hoc to paper QSVT-based NES solving complexity from Mohammadisiahroudi [2024]
    The key per-iteration query bound is referenced to an unpublished same-group PhD thesis.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A quantum dual logarithmic barrier method for linear optimization." pith.science (2026). https://pith.science/paper/SDHGEF2Q

@misc{pith2026241215977,
  author       = {Pith},
  title        = {Pith review of: A quantum dual logarithmic barrier method for linear optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SDHGEF2Q}},
  note         = {Machine review of arXiv:2412.15977}
}
abstract

Quantum computing has the potential to speed up some optimization methods. One can use quantum computers to solve linear systems via Quantum Linear System Algorithms (QLSAs). QLSAs can be used as a subroutine for algorithms that require solving linear systems, such as the dual logarithmic barrier method (DLBM) for solving linear optimization (LO) problems. In this paper, we use a QLSA to solve the linear systems arising in each iteration of the DLBM. To use the QLSA in a hybrid setting, we read out quantum states via a tomography procedure which introduces considerable error and noise. Thus, this paper first proposes an inexact-feasible variant of DLBM for LO problems and then extends it to a quantum version. Our quantum approach has quadratic convergence toward the central path with inexact directions and we show that this method has the best-known $\mathcal{O}(\sqrt{n} \log (n \mu_0 /\zeta))$ iteration complexity, where $n$ is the number of variables, $\mu_0$ is the initial duality gap, and $\zeta$ is the desired accuracy. We further use iterative refinement to improve the time complexity dependence on accuracy. For LO problems with quadratically more constraints than variables, the quantum complexity of our method has a sublinear dependence on dimension.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 31 canonical work pages

  1. [1]

    Apers and S

    S. Apers and S. Gribling. Quantum speedups for linear programming via interior point methods. arXiv preprint arXiv:2311.03215, 2023

    arXiv 2023

  2. [2]

    Applegate, O

    D. Applegate, O. Hinder, H. Lu, and M. Lubin. Faster first-order primal-dual methods for linear programming using restarts and sharpness. Mathematical Programming, 201 0 (1): 0 133--184, 2023

    work page 2023

  3. [3]

    Augustino, M

    B. Augustino, M. Mohammadisiahroudi, T. Terlaky, and L. F. Zuluaga. An inexact-feasible quantum interior point method for second-order cone optimization. Lehigh ISE Technical Report, 2021

    work page 2021

  4. [4]

    Augustino, G

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

    work page 2023

  5. [5]

    Bellavia, J

    S. Bellavia, J. Gondzio, and M. Porcelli. An inexact dual logarithmic barrier method for solving sparse semidefinite programs. Mathematical Programming, 178: 0 109--143, 2019

    work page 2019

  6. [6]

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

    work page 1971

  7. [7]

    P. A. Casares and M. A. Martin-Delgado. A quantum interior-point predictor--corrector algorithm for linear programming. Journal of Physics A: Mathematical and Theoretical, 53 0 (44): 0 445305, 2020

    work page 2020

  8. [8]

    Chakraborty, A

    S. Chakraborty, A. Gily \'e n, and S. Jeffery. The power of block-encoded matrix powers: improved regression techniques via faster H amiltonian simulation. arXiv preprint arXiv:1804.01973, 2018

    arXiv 2018

Show all 36 references
  1. [9]

    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 0 (6): 0 1920--1950, 2017

    1920

  2. [10]

    M. B. Cohen, Y. T. Lee, and Z. Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM (JACM), 68 0 (1): 0 1--39, 2021

    2021

  3. [11]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014

    2014 arXiv

  4. [12]

    Gily \'e n

    A. Gily \'e n. Quantum singular value transformation & its algorithmic applications. PhD thesis, University of Amsterdam, 2019

    2019

  5. [13]

    Gily \'e n, Y

    A. Gily \'e n, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193--204, 2019

    2019

  6. [14]

    Giovannetti, S

    V. Giovannetti, S. Lloyd, and L. Maccone. Quantum random access memory. Physical Review Letters, 100 0 (16): 0 160501, 2008

    2008

  7. [15]

    A. M. Gleixner, D. E. Steffy, and K. Wolter. Iterative refinement for linear programming. INFORMS Journal on Computing, 28 0 (3): 0 449--464, 2016

    2016

  8. [16]

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

    2009

  9. [17]

    Karmarkar

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

    1984

  10. [18]

    Kerenidis and A

    I. Kerenidis and A. Prakash. Quantum recommendation systems. arXiv preprint arXiv:1603.08675, 2016

    2016 arXiv

  11. [19]

    Kerenidis and A

    I. Kerenidis and A. Prakash. A quantum interior point method for LP s and SDP s. ACM Transactions on Quantum Computing, 1 0 (1): 0 1--32, 2020

    2020

  12. [20]

    Y. T. Lee and A. Sidford. Efficient inverse maintenance and faster algorithms for linear programming. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 230--249, 2015. doi:10.1109/FOCS.2015.23

    2015 doi

  13. [21]

    H. Lu. First-order methods for linear programming. arXiv preprint arXiv:2403.14535, 2024

    2024 arXiv

  14. [22]

    Mohammadisiahroudi

    M. Mohammadisiahroudi. Quantum Computing and Optimization Methods. PhD thesis, Lehigh University, 2024

    2024

  15. [23]

    Mohammadisiahroudi, B

    M. Mohammadisiahroudi, B. Augustino, P. Sampourmahani, and T. Terlaky. Quantum computing inspired iterative refinement for semidefinite optimization. arXiv preprint arXiv:2312.11253, 2023 a . To apear in Mathematical Programming

    2023 arXiv

  16. [24]

    Mohammadisiahroudi, R

    M. Mohammadisiahroudi, R. Fakhimi, Z. Wu, and T. Terlaky. An inexact feasible interior point method for linear optimization with high adaptability to quantum computers. arXiv preprint arXiv:2307.14445, 2023 b

    2023 arXiv

  17. [25]

    Mohammadisiahroudi, R

    M. Mohammadisiahroudi, R. Fakhimi, and T. Terlaky. Efficient use of quantum linear system algorithms in inexact infeasible IPMs for linear optimization. Journal of Optimization Theory and Applications, pages 1--38, 2024 a

    2024

  18. [26]

    Mohammadisiahroudi, Z

    M. Mohammadisiahroudi, Z. Wu, B. Augustino, A. Carr, and T. Terlaky. Improvements to quantum interior point method for linear optimization. ACM Transactions on Quantum Computing, 2024 b

    2024

  19. [27]

    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

  20. [28]

    Nannicini

    G. Nannicini. Fast quantum subroutines for the simplex method. Operations Research, 2022

    2022

  21. [29]

    Nesterov and A

    Y. Nesterov and A. Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming. SIAM, 1994

    1994

  22. [30]

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

    1997

  23. [31]

    P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124--134. IEEE, 1994

    1994

  24. [32]

    P. M. Vaidya. Speeding-up linear programming using fast matrix multiplication. In 30th Annual Symposium on Foundations of Computer Science, pages 332--337. IEEE Computer Society, 1989

    1989

  25. [33]

    van Apeldoorn, A

    J. van Apeldoorn, A. Cornelissen, A. Gily \'e n, 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

  26. [34]

    van den Brand

    J. van den Brand. A deterministic linear program solver in current matrix multiplication time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 259--278. SIAM, 2020

    2020

  27. [35]

    van den Brand, Y

    J. van den Brand, Y. T. Lee, A. Sidford, and Z. Song. Solving tall dense linear programs in nearly linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 775--788, 2020

    2020

  28. [36]

    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 0 (2), 2023. ISSN 1099-4300. doi:10.3390/e25020330. URL https://www.mdpi.com/1099-4300/25/2/330

    2023 doi

Pith tools

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