{"id":"668e2bfb-fad2-42d0-baeb-823e63b4db96","arxiv_id":"2412.11307","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A preconditioned inexact infeasible quantum interior point method improves the condition number of the normal equations from O(1/μ^2) to O(1/μ), yielding better QLSA query complexity.","lead":"This paper designs a preconditioned quantum interior point method for linear optimization and proves that its linear systems have condition number growing only linearly with the inverse duality gap, instead of quadratically. The authors derive complexity bounds showing better scaling with problem size and accuracy than prior quantum interior point methods.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's complexity relies on unproven accuracy propagation from the preconditioned system (RP-RAS) to the MNES residual; equation (7) is derived for MNES, not for the system Algorithm 2 actually solves.","rationale":"The reader correctly identified the missing accuracy analysis. My reading confirms: Section 2.3 derives equation (7) specifically for solving (MNES) with QLSA/QTA, using the residual of (MNES) and Lemma 2.1. Algorithm 2 replaces (MNES) by (RP-RAS), a preconditioned and normalized system, yet line 6 still calls for epsilon_QLSA and epsilon_QTA from equation (7). The proof of Theorem 1 does not bridge the two systems. This is not a consensus disagreement; it is an internal gap in the argument for the main theorem. The condition number analysis (Lemmas 3.3-3.7, 3.18) is independent and may be sound, but it only bounds the cost of solving RP-RAS, not the accuracy needed for convergence. I agree with the reader's conditional verdict: the paper's main contribution is plausible but currently incomplete. A concrete test would be to write out the missing propagation bound; if it introduces an additional factor such as κ(M_B) or 1/σ_min(P_c^{-1}), the claimed total complexity would likely worsen. No data or code exists to check empirically, so this analytical derivation is the appropriate test.","tokens_in":979,"tokens_out":1202,"duration_ms":66339,"concrete_test":"Re-derive the error propagation for Algorithm 2. Specifically, express the MNES residual r = M_MNES M_B^{-1} Δy - v_MNES in terms of the RP-RAS residual rho = ΞΔy - xi, using the definitions of Ξ, xi, P_c, and the identities in Section 3.1. Determine the smallest constant C such that ||r||_2 ≤ C(||rho||_2 + ε_QTA-related terms) under the normalization in (RP-RAS). If C depends on κ(M_B), 1/σ_min(P_c^{-1}), ||(P_c^{-1}K)_11||, or other quantities not bounded in Section 3.2, then equation (7) does not supply a valid precision for Algorithm 2 and the complexity bound in Theorem 1 must be recomputed. If the derivation can be completed with C = O(1) or another bound consistent with the claimed complexity, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central complexity claim in Theorem 1 depends on the QLSA/QTA accuracy set by equation (7). However, equation (7) bounds the residual of the modified normal equations (MNES), r = M_MNES z - v_MNES, by propagating a normalized-state error through M_MNES M_B^{-1}. Algorithm 2 does not solve (MNES); it builds and solves the preconditioned reduced system (RP-RAS), ΞΔy = ξ, and then reconstructs the Newton direction via Δy = M_B z. For Lemma 2.1 to apply, one needs a bound on ||r||_2 from a bound on ||ΞΔy - ξ||_2 (or from the QTA accuracy ε_QTA). The paper never derives this propagation. The proof of Theorem 1 simply reuses equation (7), and the closing paragraph of Section 3.4 says only 'Similar analysis shows...' that the accuracy is linear in the reciprocal of the condition number of a 'different linear system'. This is not a derivation. The statement of Theorem 1 even refers to a residual rhat^k without defining it. Since the convergence of the IPM and the final 1/epsilon^6 query count both hinge on the MNES residual bound, the missing accuracy analysis is load-bearing. The condition number improvements in Section 3.2 are structurally plausible, but they do not by themselves establish the error propagation needed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":20576,"tokens_out":10305,"duration_ms":91432,"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":[{"comment":"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.","section":"Section 3.4, proof of Theorem 1"},{"comment":"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.","section":"Theorem 1, statement of residual"},{"comment":"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.","section":"Theorem 1, displayed total complexity"}],"minor_comments":[{"comment":"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.","section":"Section 3.2, after Lemma 3.6"},{"comment":"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'.","section":"Equation (8)"},{"comment":"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.","section":"Proof of Lemma 3.7 / Theorem 1"},{"comment":"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.","section":"Lemma 3.17"},{"comment":"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.","section":"Section 1 and Section 3.4"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a natural continuation of [19], and the main idea is plausible. The key technical obstacle is the missing transfer of the accuracy analysis from (MNES) to (RP-RAS); without that transfer, Theorem 1 is not proved. The condition-number lemmas themselves are a solid contribution. If the authors add a rigorous error-propagation lemma for the RP-RAS solver and correct the dimension-count issue, the paper would be a strong candidate for acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper does something genuinely useful: it adapts Chai-Toh's preconditioner to the inexact infeasible QIPM setting and proves the condition number of the Newton system drops from O(1/mu^2) to O(1/mu). The condition number lemmas (3.2-3.7) are structurally plausible, and the improvement is a real step for the quantum optimization subfield. Second, the main complexity theorem (Theorem 1) has a load-bearing gap: it reuses equation (7) from [19], which was derived for solving the modified normal equations (MNES) directly, but Algorithm 2 solves the preconditioned reduced system (RP-RAS). The paper never derives the accuracy requirement that maps an error in RP-RAS to the bound ||r||_2 <= eta sqrt(mu/n) on the MNES residual. The text says only \"Similar analysis shows...\", and Theorem 1 refers to a residual rhat^k without defining it. This is not a trivial omission: the 1/epsilon^6 query count and the whole complexity claim depend on that propagation.\n\nThe condition number analysis itself is the paper's real contribution. Lemmas 3.3-3.7 give bounds on G, Y, and Z that are careful and, as far as I can tell, correct. The partition rule in Definition 2 is natural. The paper is honest about the missing derivation, which is to its credit, but it leaves the central theorem unproven.\n\nA few minor points: the algorithm requires building H, Z, and the preconditioner at each iteration, and the paper hand-waves the cost of those constructions as dominated by QLSA/QTA. That is probably fine but worth checking. The block-encoding accuracy parameters are also ignored, which is common in this literature.\n\nWho is this for? Researchers working on quantum interior point methods. The condition number improvement is a useful building block even if Theorem 1 falls. As it stands, the paper should go to serious peer review, because the gap is likely fixable and the contribution is meaningful. I would not cite the main complexity bound as stated, but I would cite the condition number lemmas if they hold. My recommendation: major revision, asking the authors to supply the missing error propagation analysis.","headline":"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.","tokens_in":21083,"tokens_out":2602,"would_cite":false,"duration_ms":22188,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C05","90C51","68Q12"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["quantum interior point methods","linear optimization","preconditioning","quantum linear system algorithms","inexact infeasible interior point methods","condition number","optimal partition","block-encoding"],"falsifier":"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.","tokens_in":20036,"feed_emoji":"⚛","tokens_out":14211,"duration_ms":109528,"temperature":0.7,"pith_summary":"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)$.","feed_headline":"Quantum IPM condition number drops from O(1/μ²) to O(1/μ)","feed_subtitle":"Preconditioning cuts Newton-system blow-up near optimality, improving accuracy dependence from ε⁻⁹ to ε⁻⁶.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the II-QIPM framework, the MNES reformulation, and the residual-to-step bound (Lemma 2.1) that this work inherits and improves.","marker":"[19]"},{"why":"Supplies the preconditioning construction for the augmented system that is adapted into (RAS), (P-RAS), and finally (RP-RAS).","marker":"[5]"},{"why":"Provides the QLSA whose condition-number dependence and block-encoding costs determine the query complexity in Theorem 1.","marker":"[6]"},{"why":"Provides the quantum state tomography algorithm whose precision enters the accuracy condition (7) and hence the total query count.","marker":"[27]"},{"why":"Supplies the block-encoding primitives used to build the coefficient matrix of (RP-RAS) with polylogarithmic overhead.","marker":"[11]"},{"why":"Gives the inexact infeasible IPM convergence framework whose residual criterion the quantum solver must meet.","marker":"[1]"},{"why":"Justifies Assumptions 2 and 3 through canonical-form and self-dual embedding reductions.","marker":"[18]"}],"fun_headline_variants":["Quantum IPM conditioning drops to O(1/μ) with preconditioning","Preconditioned QIPM: linear condition number, ε^-6 accuracy","II-QIPM preconditioning: condition number O(1/μ) and ε^-6","Quantum LP solver preconditioning: μ^-2 to μ^-1 conditioning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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).","fun_headline_variants_meta":{"raw":{"variants":["Quantum IPM conditioning drops to O(1/μ) with preconditioning","Preconditioned QIPM: linear condition number, ε^-6 accuracy","II-QIPM preconditioning: condition number O(1/μ) and ε^-6","Quantum LP solver preconditioning: μ^-2 to μ^-1 conditioning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000769,"raw_usage":{"total_tokens":3439,"prompt_tokens":1006,"completion_tokens":2433,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":622,"completion_tokens_details":{"reasoning_tokens":2347}},"tokens_in":622,"tokens_out":2433,"duration_ms":18559,"temperature":1.0,"reasoning_tokens":2347,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T15:05:27.773342+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Efficient Use of Quantum Linear System Algorithms in Interior Point Methods for Linear Optimization","cited_arxiv_id":"2205.01220","evidence_quote":"Defines the II-QIPM framework, the MNES reformulation, and the residual-to-step bound (Lemma 2.1) that this work inherits and improves."},{"cited_title":"Chai and K.-C","cited_arxiv_id":null,"evidence_quote":"Supplies the preconditioning construction for the augmented system that is adapted into (RAS), (P-RAS), and finally (RP-RAS)."},{"cited_title":"van Apeldoorn, A","cited_arxiv_id":null,"evidence_quote":"Provides the quantum state tomography algorithm whose precision enters the accuracy condition (7) and hence the total query count."},{"cited_title":"Al-Jeiroudi and J","cited_arxiv_id":null,"evidence_quote":"Gives the inexact infeasible IPM convergence framework whose residual criterion the quantum solver must meet."},{"cited_title":"Mohammadisiahroudi, F","cited_arxiv_id":null,"evidence_quote":"Justifies Assumptions 2 and 3 through canonical-form and self-dual embedding reductions."}],"review_version":1}