{"id":"67d6e50e-eede-4a79-a699-d19c4c69e942","arxiv_id":"1908.06720","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A quantum interior-point method for second-order cone programs, applied to soft-margin SVM training, runs in O~(n√r ζκ/δ² log(1/ε)) and is shown in simulation to scale as O(n^2.59) on random SVM instances.","lead":"This paper designs a quantum interior-point method for second-order cone programming, a broad class of optimization problems that includes support vector machine training. It reports a theoretical running time and simulations suggesting a polynomial speedup over classical solvers for random SVM instances.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed polynomial speedup rests on unproven scaling of κ and δ; experiments only cover n≤512 and ε=0.1, so the speedup claim remains conditional.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing gap: the runtime theorem is parameterized by instance-dependent quantities κ, ζ, and δ, and the claimed polynomial speedup over classical SOCP/SVM solvers depends on these quantities remaining modest as n grows. The paper is honest about this dependence, and the experimental evidence is a reasonable first step: it uses a reproducible experiment log, a classical IPM with simulated tomography noise, and fits exponents with confidence intervals. That evidence supports a conditional speedup for moderate n and precision, but it does not establish a worst-case or even a robust instance-family speedup. I agree with the conditional verdict: the theoretical algorithm is plausible and the per-iteration analysis is detailed, but the end-to-end speedup claim should not be upgraded to unconditional. A larger-scale refit or an adversarial instance family is the natural check that would either stabilize the exponent or reveal that the speedup is an artifact of small n. I do not see a separate internal inconsistency strong enough to overturn the conditional verdict.","tokens_in":21360,"tokens_out":26852,"duration_ms":264357,"concrete_test":"Run the same simulation protocol for SVM(n,2n,p) at n = 2^10, 2^12, and 2^14 with p ∈ {0.1, 0.5, 0.9}, recording the exact κ, ζ, and δ from the simulated IPM. Refit the power-law exponent of n^{1.5}κζ/δ²; if the refitted exponent reaches 3.0 or higher, the polynomial speedup over ECOS's measured exponent of 3.314 disappears.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.6 and Theorem 5 define the runtime as O~(√r log(µ0/ε) · nκζ/δ² log(κζ/δ)), with δ = min_i (ξ/4) min{λmin(x_i), λmin(s_i)}. Section 5.2 converts this into a speedup by fitting n^{1.5}κζ/δ² to a power law on SVM(n,2n,p) instances, obtaining a fitted exponent of 2.591 for the quantum side versus 3.314 for ECOS. The load-bearing assumption is that κ, ζ, and δ scale benignly with n on this instance family. The paper provides no worst-case bound: Section 4.6 explicitly notes that κ and δ are difficult to bound, and Section 1.1 concedes that κ is empirically O(1/ε). The speedup comparison is therefore a finite-sample fit over n = 4 to 512 at a single precision ε = 0.1, on a simulated noise model. Nothing in the analysis rules out families of SVMs—for example, instances with a small margin or with many support vectors near the margin—where κ/δ² grows with n fast enough to erase the reported exponent gap. Since the central advertised advantage is an end-to-end polynomial speedup, this unverified parameter scaling is the point where the claim is least secure.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes a quantum interior-point method (IPM) for second-order cone programming (SOCP). The algorithm assumes a QRAM/block-encoding input model, solves each Newton linear system with quantum linear algebra, and recovers classical updates by vector-state tomography. The authors state a per-iteration invariance theorem for an approximate IPM in the Euclidean Jordan algebra framework and derive the worst-case complexity O~(sqrt(r) log(mu0/epsilon) * n kappa zeta / delta^2 * log(kappa zeta / delta)), where kappa, zeta, and delta are instance-dependent quantities. They then reduce the soft-margin l1-SVM training problem to SOCP, simulate the algorithm on random SVM instances with n up to 512 and epsilon=0.1, and report a fitted exponent 2.591 for the quantum cost expression versus 3.314 for ECOS and 3.112 for LIBSVM. The paper claims the first quantum IPM for SOCP and the first quantum algorithm for standard soft-margin SVM, with experimental evidence of polynomial speedup.","tokens_in":21625,"tokens_out":9762,"duration_ms":100925,"significance":"If the main theorem is correct, the contribution is significant: it extends quantum interior-point methods from LP/SDP to SOCP, provides a complete algorithm under QRAM assumptions, and identifies SVM as a concrete end-to-end application with possible polynomial speedup. Strengths include the detailed per-iteration analysis using Jordan-algebraic tools, the use of block-encoding data structures with stated update costs, and the public release of experiment logs. The main advertised speedup, however, is empirical and depends on the unproven benign scaling of kappa and delta; the paper is appropriately cautious in places, but the abstract's phrasing goes somewhat beyond the evidence.","major_comments":[{"comment":"Algorithm 1 as written updates only x and s in step (d), not y, even though step (c) obtains an approximate Delta y by tomography. The per-iteration correctness theorem and the infeasibility bound in Theorem 6 are for (x+Delta x, y+Delta y, s+Delta s), and the proof of Theorem 6 explicitly uses y_T = y_{T-1} + Delta y_T. If y is not updated, the dual residual A^T y + s - c does not satisfy the claimed bound, and the right-hand side of the Newton system in later iterations is stale. The authors should either update y in Algorithm 1 or explain rigorously why y can remain fixed.","section":"Section 3, Algorithm 1 and Section 4.6, Theorem 6"},{"comment":"The complexity formula in Theorem 5 depends on kappa and delta, which are instance-dependent and are not bounded in the paper. The reported polynomial speedup is based on fitting the quantity n^{1.5} kappa zeta / delta^2 to a power law over n in {4,...,512} at a single precision epsilon=0.1, with no argument that kappa zeta / delta^2 grows slowly on the SVM family. Section 4.6 explicitly states that kappa and delta are difficult to bound. Therefore the end-to-end speedup claim is conditional; the authors should either provide bounds for the random SVM family or explicitly restrict the conclusion to evidence under an assumed scaling of these parameters.","section":"Section 4.6 and Section 5.2"},{"comment":"The comparison mixes a fitted symbolic cost expression (n^{1.5} kappa zeta / delta^2) for the quantum algorithm with wall-clock timings for ECOS and LIBSVM. The claimed 'speedup of 10^4 for n=10^6' is obtained by ignoring constant factors, but the constants in quantum tomography and block-encoding procedures are not negligible and the fit also pools over the noise parameter p. The quantitative speedup at finite n is therefore not justified by the exponent fit; please report constants or state the conclusion only in terms of asymptotic exponents under the assumed parameter scaling.","section":"Section 5.2"}],"minor_comments":[{"comment":"The formal statement of Theorem 4 sets sigma = 1 - chi/sqrt(n), while Lemma 5 and the rest of the paper use sigma = 1 - alpha/sqrt(r); this should be sqrt(r), or the iteration count in Theorem 5 must be reconciled.","section":"Section 4.2, Theorem 4"},{"comment":"Part 2 of Theorem 4 writes 'mu = sigma mu', overloading the symbol mu for both the old and new duality gap; please rename the updated gap, for example mu_new.","section":"Section 4.2, Theorem 4"},{"comment":"The description of the simulated noise as 'uniform, from an interval selected so that ... simulates the outputs of tomography' is not a faithful model of the l2 guarantee in Theorem 3; specify how the interval is chosen and justify why this matches the tomography error bound.","section":"Section 5.2"},{"comment":"The phrase 'delta-approximate epsilon-optimal solution' overloads delta as both the tomographic precision and the infeasibility parameter; the two roles should be defined explicitly.","section":"Abstract and Section 1.1"},{"comment":"The caption should state the quantity plotted on the y-axis; as written, the reader must infer from the text that it is n^{1.5} kappa zeta / delta^2.","section":"Figure 1"}],"recommendation":"major_revision","confidential_remarks":"The per-iteration proof is the heart of the paper, so I recommend that the editor ensure the supplementary material is part of the review if it contains the full proof. The y-update inconsistency in Algorithm 1 must be resolved before acceptance, and the speedup claims should be reworded to match the conditional evidence."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is the first quantum interior-point method for second-order cone programs and the first quantum algorithm aimed at the standard soft-margin (l1) SVM. The genuinely new piece is the approximate IPM analysis in Euclidean Jordan algebras, extending the LP/SDP treatment of Kerenidis and Prakash. The paper is honest that the advertised polynomial speedup rests on unproven scaling of κ and δ.\n\nWhat it does well: the per-iteration theorem is stated with explicit constants (η=χ=0.01, ξ=0.001), and the proof structure—rescaling, strict feasibility, central-path neighborhood, gap reduction—is standard but adapted carefully to SOCP. The SVM reduction to SOCP is clean. The numerical study is real work: roughly 16,000 random instances, n up to 512, ε=0.1, with logs deposited. On that family the fitted exponent 2.59 beats ECOS 3.31 and LIBSVM 3.11. The paper does not oversell; it repeatedly says the speedup is experimental and not a worst-case bound.\n\nWhere I would push back: the full proof of Theorem 4 is only in the supplementary material, and the main text imports Lemma 2 from Monteiro and Tsuchiya [28]. That is acceptable practice, but it means the central claim is not verifiable from the main text alone. Second, the simulation adds uniform per-coordinate noise calibrated to the tomography precision. It is a reasonable proxy but not the actual tomography distribution, so the empirical constants should be read as indicative. Third, and most importantly, the runtime formula has nκζ/δ², where δ is the minimum over iterations of the smallest eigenvalues of x and s. There is no bound on κ or δ in terms of n; Section 1.1 says κ is empirically O(1/ε), and the experiments cover a single precision. Nothing rules out SVM families—small margin, many support vectors near the margin—where κ/δ² grows fast enough to erase the observed exponent gap. The paper says this itself, but it is the load-bearing weakness.\n\nThe citation pattern is fine: it builds explicitly on [26], [28], and QRAM data structures, and the novelty claims against [33] and [3] are accurate. I do not see an obvious flaw in the per-iteration argument as sketched.\n\nBottom line: this deserves a serious referee. The theory is plausible, the writing is clear, and the limitations are laid out rather than hidden. The referee should demand the supplementary proof and keep the discussion conditional. I would bring it to reading group and would cite it if I worked on quantum optimization.","headline":"First quantum interior-point method for SOCP and the standard soft-margin SVM; the analysis is credible, the speedup is conditional on unproven scaling of κ and δ.","tokens_in":22166,"tokens_out":2515,"would_cite":true,"duration_ms":26492,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","90C25"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"This paper presents a quantum interior-point method for second-order cone programs that returns a classical $\\delta$-approximate $\\epsilon$-optimal solution from a quantum description of the problem, with running time…","keywords":["quantum interior-point method","second-order cone programming","support vector machines","quantum linear algebra","block encodings","Euclidean Jordan algebras","convex optimization","quantum speedup"],"falsifier":"Run the noisy-IPM simulation on a family of SOCPs engineered to push iterates close to the cone boundary (small $\\delta$) with ill-conditioned Newton matrices, and measure $n^{1.5}\\kappa\\zeta/\\delta^2$; if the least-squares exponent reaches or exceeds the classical exponent of about $3.31$, the claimed polynomial speedup is refuted for that family.","tokens_in":21136,"feed_emoji":"⚛️","tokens_out":10251,"duration_ms":97379,"temperature":0.7,"pith_summary":"This paper aims to establish that second-order cone programs (SOCPs) admit a quantum interior-point method that accepts a quantum description of the problem and returns a classical description of a solution that is both close to feasible and close to optimal. The claimed running time is $\\widetilde{O}(\\sqrt{r}\\log(\\mu_0/\\epsilon)\\cdot n\\kappa\\zeta/\\delta^2)$, where $r$ is the number of cone constraints, $\\kappa$ bounds the condition numbers of the Newton systems, $\\zeta$ is a block-encoding parameter, and $\\delta$ measures how far the iterates stay from the cone boundary. If the instance-dependent parameters stay moderate, this would be the first quantum interior-point method for SOCPs and the first quantum algorithm for the standard soft-margin $\\ell^1$-SVM training problem. Numerical simulations on random SVM instances estimate the quantum scaling exponent at about $2.59$, versus about $3.31$ for a general SOCP solver and $3.11$ for a specialized classical SVM solver, suggesting a polynomial speedup for low- to medium-precision training.","feed_headline":"Quantum cone solver outruns classical SVM solvers in tests","feed_subtitle":"It targets the standard soft-margin SVM, where benchmarked classical solvers scale close to cubic time.","key_machinery":"The load-bearing mechanism is the Euclidean Jordan algebra of Lorentz cones, which lets the proof treat vectors as matrices: each cone vector has two eigenvalues $\\lambda_1=x_0+\\|\\tilde{x}\\|$ and $\\lambda_2=x_0-\\|\\tilde{x}\\|$, a quadratic representation $Q_x$, and a square-root map $T_x=Q_x^{1/2}$. The central path analysis rescales $x$ and $s$ by $T_x$ so they share a Jordan frame, reducing the approximate Newton-step correction to bounds on $\\|\\Delta x'\\|_F$ and $\\|\\Delta s'\\|_F$. Quantum speed enters through block encodings of the Newton matrix built from QRAM data structures, the quantum linear-system solver, and dimension-linear tomography; the precision $\\delta$ of tomography is chosen as $\\delta_i=\\xi\\min\\{\\lambda_{\\min}(x_i),\\lambda_{\\min}(s_i)\\}/4$ to keep the approximate IPM convergent.","core_discovery":"The paper's central claim is that a long-step interior-point method for SOCP can tolerate inexact solutions of its Newton linear system, as long as each inexact increment is accurate to within a fraction of the current iterate's distance to the cone boundary. Using quantum linear algebra over block encodings, each Newton system can then be solved in time sublinear in the dimension, and vector-state tomography converts the quantum solution into a classical increment. The authors prove per-iteration correctness: with constants $\\eta=\\chi=0.01$ and $\\xi=0.001$, the updated primal and dual iterates remain strictly feasible, stay in the $\\eta$-neighborhood of the central path, and reduce the duality gap by a factor $1-\\alpha/\\sqrt{r}$. Iterating this for $O(\\sqrt{r}\\log(\\mu_0/\\epsilon))$ steps yields Theorem 5's complexity and Theorem 6's controlled linear infeasibility. Applying the method to the soft-margin SVM reduces training to an SOCP of size $O(n+m)$ with $O(m)$ cone constraints, and the simulations estimate the full cost $n^{1.5}\\kappa\\zeta/\\delta^2$ as scaling like $n^{2.591}$ on random instances.","pith_inferences":["If $\\kappa$ grows as $O(1/\\epsilon)$ on realistic instances, the effective dependence on $\\epsilon$ becomes polynomial, so the quantum advantage is plausibly confined to low- and medium-precision regimes; high-precision SOCP may not show a speedup.","The same approximate-IPM framework could be retargeted at homogeneous self-dual embeddings to remove the need for a known strictly feasible starting point, extending the algorithm to arbitrary SOCPs without initialization heuristics.","A direct test of the paper's premise would be to generate adversarial random instances that force iterates close to the cone boundary (small $\\delta$) and measure whether $n\\kappa\\zeta/\\delta^2$ grows faster than the classical exponent of about $3.31$.","Benchmarking the noisy-IPM simulation against classical first-order SVM solvers on real datasets would test whether the random Gaussian instances used here reflect the conditioning of text or image data."],"forward_implications":["The standard soft-margin $\\ell^1$-SVM becomes a candidate end-to-end application where a quantum optimization algorithm improves on classical SOCP solvers, assuming the measured parameter scaling persists.","For low or moderate precision, roughly $\\epsilon=0.1$, which already gives near-optimal classifiers, the quantum algorithm's empirical exponent $2.59$ beats the measured $3.31$ of the benchmarked general SOCP solver and $3.11$ of the specialized SVM solver.","The same Newton-system solver can be replaced by a classical iterative solver, yielding an $O(n^2\\sqrt{r}\\kappa\\log(n/\\epsilon))$ classical method as a byproduct of the analysis.","The $\\ell^2$ least-squares SVM also fits the framework with $O(1)$ cone constraints, matching the complexity of the existing quantum LS-SVM algorithm while additionally supporting the sparse $\\ell^1$ variant.","The per-iteration correctness theorem gives the first approximate-IPM convergence analysis for SOCP under $\\ell^2$-norm Newton errors, a result that stands whether or not a quantum computer is used."],"supporting_citations":[{"why":"Provides the classical SOCP interior-point analysis and the Jordan-algebraic lemmas that the per-iteration proof reuses.","marker":"[28]"},{"why":"Supplies the approximate quantum interior-point method template and the vector-state tomography theorem used to recover classical increments.","marker":"[26]"},{"why":"Gives the block-encoded quantum linear-system solver used to solve each Newton system.","marker":"[11]"},{"why":"Provides the quantum singular-value transformation machinery that implements the quantum linear algebra with the stated error dependence.","marker":"[18]"},{"why":"Defines the QRAM data structures and block-encoding construction used for the input model.","marker":"[24, 25]"},{"why":"Supplies the background theory of second-order cone programming and the properties of quadratic representations used throughout.","marker":"[1]"},{"why":"The external SOCP solver whose measured running-time exponent is the classical baseline in the experiments.","marker":"[15]"},{"why":"The specialized linear-kernel SVM solver used as the state-of-the-art classical comparison for training time.","marker":"[12]"}],"fun_headline_variants":["Quantum SOCP solver shows polynomial speedup over classical","Quantum interior-point method beats classical SVM scaling","Quantum algorithm for SOCP scales better than classical solvers","Quantum speedup for second-order cone programming and SVM","Faster SOCP solving with quantum interior-point method"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claimed speedup depends on the combined instance parameter $\\kappa\\zeta/\\delta^2$ staying modest as $n$ grows; the paper supports this only with empirical power-law fits, not a worst-case bound, so there may exist SOCP instances where the quantum algorithm loses its advantage.","fun_headline_variants_meta":{"raw":{"variants":["Quantum SOCP solver shows polynomial speedup over classical","Quantum interior-point method beats classical SVM scaling","Quantum algorithm for SOCP scales better than classical solvers","Quantum speedup for second-order cone programming and SVM","Faster SOCP solving with quantum interior-point method"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000856,"raw_usage":{"total_tokens":3809,"prompt_tokens":1125,"completion_tokens":2684,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":741,"completion_tokens_details":{"reasoning_tokens":2609}},"tokens_in":741,"tokens_out":2684,"duration_ms":21135,"temperature":1.0,"reasoning_tokens":2609,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:36:54.987575+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the noisy-IPM simulation on a family of SOCPs engineered to push iterates close to the cone boundary (small $\\delta$) with ill-conditioned Newton matrices, and measure $n^{1.5}\\kappa\\zeta/\\delta^2$; if the least-squares exponent reaches or exceeds the classical exponent of about $3.31$, the claimed polynomial speedup is refuted for that family.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the classical SOCP interior-point analysis and the Jordan-algebraic lemmas that the per-iteration proof reuses."},{"cited_title":"Alizadeh and D","cited_arxiv_id":null,"evidence_quote":"Supplies the background theory of second-order cone programming and the properties of quadratic representations used throughout."}],"review_version":1}