{"id":"6cf715d0-f23a-4a0f-a1d1-676ca51f80ff","arxiv_id":"2412.15977","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A dual-only quantum interior point method for linear optimization with inexact Newton directions and O(√n) iteration complexity, using QLSA and tomography.","lead":"This paper designs a quantum algorithm for linear programming by pairing a dual logarithmic barrier method with a quantum linear system solver, tolerating noisy intermediate steps. The authors claim O(√n) iterations and a quantum speedup for tall problems, but the proof contains gaps.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.2's proof uses the false componentwise lower bound (s^-1 Δs)^2 >= 0.25e, so the proximity invariant δ(s,μ)<=0.5 and the O(sqrt(n)) iteration bound in Theorem 3.3 are not established as written.","rationale":"The reader's weakest assumption identifies exactly the failure I consider most load-bearing: Lemma 3.2 is the only mechanism that keeps the proximity measure ≤0.5 across iterations, and the O(sqrt(n)) complexity is derived from it. I checked the proof line by line. The proof uses the norm bound δ≤0.5 to infer componentwise (s^-1Δs)^2≥0.25e, but the norm bound gives the opposite direction. A concrete admissible choice (n=1, a=0.05, b=0.005) makes h^T(e-h)<0, directly falsifying the proof's intermediate claim. While this specific example does not necessarily violate the lemma's final inequality (the constants are loose), it exposes that the published proof does not establish the lemma; the derivation of δ(s+,μ+)^2≤(1+ρ^2)(δ^4+0.06)+ρ^2 n passes through an unjustified inequality. Since Theorem 3.3 and hence the headline iteration and query complexity depend on this lemma, the central claim is not proven as written. I do not see a different flaw that is more fundamental; the separate issue that 'sublinear in dimension' is not actually o(n) under n≥m^2 is also present, but it is downstream of the convergence proof and is a comparison/interpolation error rather than the root of the proof failure. Thus I agree with the reader's REJECT and recommend no change to the verdict.","tokens_in":21442,"tokens_out":21901,"duration_ms":181647,"concrete_test":"Re-derive Lemma 3.2 without the false componentwise bound (s^-1Δs)^2>=0.25e. As a witness, use n=1, a=s^-1Δs=0.05, b=s^-1E=0.005, μ=1, s=1, θ=1/4, which satisfies all stated hypotheses and gives h=a^2+(a-1)b=-0.00225, hence h(e-h)<0; compute δ(s+,μ+)^2 directly for this instance. If the exact value exceeds the lemma's RHS in any such admissible search (n<=10, |a_i|<=0.5, ||b||_2<=0.1||a||_2), the O(sqrt(n)) iteration bound in Theorem 3.3 is false; if it never does, the theorem still needs a corrected proof because the published one is invalid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 3.2 is the linchpin of Theorem 3.3: it is used to prove the invariant δ(s,μ)<=0.5 after every iteration, from which the claimed O(sqrt(n) log(nμ0/ζ)) iteration bound follows. Its proof is invalid. Writing a=s^-1Δs and b=s^-1E^C_Δs, the available bounds are |a_i|<=0.5 and ||b||_2<=0.1δ(s,μ)<=0.05; these give a_i^2<=0.25, not a_i^2>=0.25. The lower bound displayed in Eq. (2) therefore does not follow. More directly, the claimed intermediate conclusion h^T(e-h)>=0 is false: with n=1, a=0.05, b=0.005 (which satisfies ||b||=0.1δ), h=a^2+(a-1)b=-0.00225<0, so h(e-h)<0. Consequently the step δ(s+,μ+)^2 <= (1+ρ^2)||h||^2+ρ^2 n, which relies on h^T(e-h)>=0, is not justified, and the final bound δ(s+,μ+)^2 <= (1+ρ^2)(δ^4+0.06)+ρ^2 n is not established as written. A corrected argument might exist, but the paper supplies none; without Lemma 3.2, Theorem 3.3's complexity claim is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21798,"tokens_out":18558,"duration_ms":153453,"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":[{"comment":"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.","section":"Lemma 3.2, Eq. (2)"},{"comment":"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.","section":"Section 3.2, Proposition 3.4"},{"comment":"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.","section":"Theorem 3.7 and Section 3.3"},{"comment":"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.","section":"Abstract and Section 3.2"}],"minor_comments":[{"comment":"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.","section":"Theorem 3.3, proof"},{"comment":"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).","section":"Lemma 3.2"},{"comment":"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.","section":"Table 1 and surrounding text"},{"comment":"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.","section":"Section 2.4"}],"recommendation":"major_revision","confidential_remarks":"The main blocker is Lemma 3.2: the proof contains a false inequality with the wrong direction, and the paper's iteration-complexity theorem depends on it. I am not able to show that the final complexity claims are false, and a corrected analysis may exist, so I recommend major revision rather than reject. The editor should also be aware that key quantum complexity bounds are taken from the authors' own unpublished or to-appear results; the paper would be stronger if those statements were proved in an appendix or clearly isolated as assumptions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the dual-only framework is a real contribution, and the paper is honest about its debt to prior work, but the proof of Lemma 3.2 has a false inequality that takes down the O(sqrt(n)) iteration bound as written. The rest of the analysis deserves proper referee attention, because the errors look repairable.\n\nThe genuinely new piece is the inexact-feasible dual logarithmic barrier method with QSVT/QTA subroutines and the error propagation analysis in Theorems 3.1–3.3. Unlike Bellavia et al., the method keeps primal feasibility without preprocessing or modifying the Newton system, and the dual-only iterative refinement in Section 3.3 is a sensible way to kill the precision dependence. The authors also make a real attempt to state explicit accuracy bounds for the quantum subroutines, which is more than many QIPM papers do.\n\nThe load-bearing problem is Lemma 3.2. The proof uses the componentwise lower bound (s^{-1}Delta s)^2 >= 0.25e. That is false: from |a_i| <= 0.5 you only get a_i^2 <= 0.25, not >=. The stress-test counterexample is valid (n=1, a=0.05, b=0.005 gives h = a^2+(a-1)b < 0), so the intermediate claim h^T(e-h) >= 0 is not established. Since Lemma 3.2 is the step that keeps delta(s,mu) <= 0.5 in Theorem 3.3, the claimed O(sqrt(n) log(n mu0/zeta)) iteration bound is unsupported as written. A corrected argument may exist, but it is not in the paper.\n\nThere are smaller issues. The derivation of the QLSA accuracy condition in Proposition 3.4 has a denominator missing a square root; the displayed expression is dimensionally inconsistent, though the final bound may still be right. The abstract's 'sublinear dependence on dimension' is misleading: under n >= m^2, m sqrt(n) kappa0 is O(n kappa0), not o(n). Finally, several complexity bounds are imported from same-group works in-press or in thesis form, which makes independent verification harder; that is not a fatal flaw by itself, but the paper should be explicit about what is and isn't established externally.\n\nWho is this for: researchers working on quantum interior point methods. The dual-only approach is worth exploring further, and the error analysis machinery is reusable. I would send this to a serious referee, but with the expectation of major revision and a repaired Lemma 3.2. My guess is the approach can be fixed, and if it is, the paper will be useful.","headline":"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.","tokens_in":22359,"tokens_out":4062,"would_cite":false,"duration_ms":29921,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C05","90C51","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"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))$…","keywords":["quantum interior point method","dual logarithmic barrier","linear optimization","quantum linear system algorithm","quantum tomography","iterative refinement","inexact Newton method","sublinear quantum complexity"],"falsifier":"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.","tokens_in":21219,"feed_emoji":"⚛️","tokens_out":13332,"duration_ms":101050,"temperature":0.7,"pith_summary":"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.","feed_headline":"Inexact quantum barrier method targets O(√n) LP iterations","feed_subtitle":"Claims quantum linear-system solvers and iterative refinement give sublinear query counts for tall LPs","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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}$."],"supporting_citations":[{"why":"Supplies the classical dual logarithmic barrier method, the proximity measure, and Lemmas 2.1-2.4 that the inexact analysis extends.","marker":"Roos et al. [1997]"},{"why":"Provides the quantum singular value transformation used as the QLSA to solve the normal equation system.","marker":"Gilyén et al. [2019]"},{"why":"Provides the quantum tomography algorithm used to read out classical Newton directions from quantum states.","marker":"van Apeldoorn et al. [2023]"},{"why":"The classical inexact dual logarithmic barrier method for semidefinite programs whose residual handling and convergence framework are adapted to LO.","marker":"Bellavia et al. [2019]"},{"why":"The closest quantum IPM for tall LOs; serves as the paper's sublinear-query comparison target and the benchmark for the relaxed tallness condition.","marker":"Apers and Gribling [2023]"},{"why":"Supplies block-encoding primitives used to represent the normal equation matrix in the quantum operator input model.","marker":"Chakraborty et al. [2018]"},{"why":"Establishes the QRAM data structure and efficient block encoding on which the quantum subroutine's polylogarithmic overhead rests.","marker":"Kerenidis and Prakash [2016]"},{"why":"Shows how to solve the normal equation system via QSVT with iterative refinement, giving the query complexity used in Theorem 3.7.","marker":"Mohammadisiahroudi [2024]"},{"why":"Motivates the iterative refinement scheme and the feasibility-preserving treatment of inexact directions in quantum IPMs.","marker":"Mohammadisiahroudi et al. [2023b]"}],"fun_headline_variants":["Quantum barrier method quashes LP iteration count to O(√n)","Inexact quantum barrier converges quadratically, cuts queries","Sublinear quantum complexity for tall linear programs","Quantum DLBM: √n iterations with inexact directions","Quadratic convergence in quantum barrier method for LP"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quantum barrier method quashes LP iteration count to O(√n)","Inexact quantum barrier converges quadratically, cuts queries","Sublinear quantum complexity for tall linear programs","Quantum DLBM: √n iterations with inexact directions","Quadratic convergence in quantum barrier method for LP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000609,"raw_usage":{"total_tokens":2882,"prompt_tokens":1035,"completion_tokens":1847,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":651,"completion_tokens_details":{"reasoning_tokens":1768}},"tokens_in":651,"tokens_out":1847,"duration_ms":13248,"temperature":1.0,"reasoning_tokens":1768,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T10:55:50.499752+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}