Quantum algorithms for Second-Order Cone Programming and Support Vector Machines

Anupam Prakash; D\'aniel Szil\'agyi; Iordanis Kerenidis

REVIEW 3 major objections 5 minor 2 cited by

Quantum algorithms for Second-Order Cone Programming and Support Vector Machines

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

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

Pith's one-line read 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…

desk verdict 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 δ. read the letter →

arxiv 1908.06720 v4 pith:XT5T3LYY submitted 2019-08-19 quant-ph cs.DSstat.ML

Iordanis Kerenidis , Anupam Prakash , Dániel Szilágyi This is my paper · ORCID

classification quant-phcs.DSstat.ML MSC 81P6890C25 PACS 03.67.Lx

keywords quantuminterior-pointmethodsecond-orderconeprogrammingsupportvectormachineslinearalgebrablockencodingsEuclideanJordanalgebrasconvexoptimizationspeedup

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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 δ.

What 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.

Where 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.

The 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.

Bottom 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.

Referee Report

3 major / 5 minor

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.

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 (3)

[Section 3, Algorithm 1 and Section 4.6, Theorem 6] 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 4.6 and Section 5.2] 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 5.2] 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.

minor comments (5)

[Section 4.2, Theorem 4] 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 4.2, Theorem 4] 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 5.2] 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.
[Abstract and Section 1.1] 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.
[Figure 1] 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.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the SOCP quantum IPM theorem is proven from an original approximate-Newton analysis, and the empirical exponent fit is a measurement of parameter scaling, not an input to the proof.

full rationale

The main derivation is self-contained. Theorem 4's per-iteration correctness is proved in Sections 4.3 to 4.5: rescaling by Tx, bounding approximate increments, strict feasibility, central-path neighborhood, and duality-gap reduction. The SOCP-specific inexact-Newton analysis is original, with only standard Jordan-algebra lemmas from Monteiro-Tsuchiya [28] and the SDP-IPM template from Kerenidis-Prakash [26]. Theorem 5 is then a direct composition of the iteration count, the quantum linear system solver [11,18], and vector-state tomography [26], with kappa, zeta, and delta as explicitly defined instance parameters. The numerical section (Section 5.2) fits the measured quantity n^{1.5} kappa zeta / delta^2 to a power law; this is an empirical estimate of parameter scaling used to illustrate, not to prove, the speedup, and the paper explicitly disclaims a worst-case asymptotic speedup. The self-citations [24,25,26] supply QRAM block encodings and tomography subroutines that are published and parameter-free with assumptions not including the target SOCP conclusion; the convergence and complexity claims do not reduce to those citations or to the fitted exponents. No equation is equivalent to its own input by construction.

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

The central theorem is built on three reused building blocks: classical SOCP interior-point theory (Jordan algebra lemmas from [1,28]), the QRAM/block-encoding framework and quantum linear algebra from prior work (including the authors' own [24,25,26] and [11,18]), and the strict feasibility assumption. The only hand-chosen constants are eta, chi, xi, plus C=1 in the experiments. No new physical entity is introduced. The empirical speedup claim additionally assumes that a uniform-noise simulation faithfully represents quantum tomography.

free parameters (2)

Central path constants (eta, chi, xi) = 0.01, 0.01, 0.001
Chosen by hand in Theorem 4 to make the per-iteration feasibility and convergence inequalities hold; not derived from first principles.
SVM hyperparameter C = 1
Set to 1 in all experiments; not part of the algorithm's core complexity, but affects the instance distribution and the fitted scaling exponent.

assumptions (5)

standard math Classical IPM convergence for SOCP and Jordan algebra properties from [1,28]
The paper relies on the Jordan algebra spectral decomposition, quadratic representation, and central path neighborhood lemmas (e.g., Lemma 2 from [28]) without reproving them.
domain assumption Quantum linear algebra theorems from [11,18,24,25] hold as stated
The algorithm's per-iteration cost directly uses the QRAM block-encoding construction, quantum matrix inversion, and state tomography with the claimed polylogarithmic and linear-in-n scaling.
domain assumption The SOCP is strictly feasible; general SOCPs are handled via homogeneous self-dual embedding [42]
Strong duality and central path existence require strict feasibility; the embedding is invoked but not detailed.
ad hoc to paper The condition number kappa and boundary distance parameter delta are bounded so that zeta*kappa/delta^2 stays manageable; empirically kappa=O(1/epsilon)
The running time formula depends on instance-dependent kappa, zeta, delta. The claimed polynomial speedup in practice assumes these do not grow too fast; the paper gives zeta<=sqrt(n) and empirical evidence for kappa, but no worst-case bound.
domain assumption Availability of QRAM and a data structure that can be updated in O(log^2 n) per entry
The algorithm requires storing the Newton matrix in QRAM and preparing block encodings at each iteration; this is a hardware architecture assumption.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quantum algorithms for Second-Order Cone Programming and Support Vector Machines." pith.science (2026). https://pith.science/paper/XT5T3LYY

@misc{pith2026190806720,
  author       = {Pith},
  title        = {Pith review of: Quantum algorithms for Second-Order Cone Programming and Support Vector Machines},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XT5T3LYY}},
  note         = {Machine review of arXiv:1908.06720}
}

abstract

We present a quantum interior-point method (IPM) for second-order cone programming (SOCP) that runs in time $\widetilde{O} \left( n\sqrt{r} \frac{\zeta \kappa}{\delta^2} \log \left(1/\epsilon\right) \right)$ where $r$ is the rank and $n$ the dimension of the SOCP, $\delta$ bounds the distance of intermediate solutions from the cone boundary, $\zeta$ is a parameter upper bounded by $\sqrt{n}$, and $\kappa$ is an upper bound on the condition number of matrices arising in the classical IPM for SOCP. The algorithm takes as its input a suitable quantum description of an arbitrary SOCP and outputs a classical description of a $\delta$-approximate $\epsilon$-optimal solution of the given problem. Furthermore, we perform numerical simulations to determine the values of the aforementioned parameters when solving the SOCP up to a fixed precision $\epsilon$. We present experimental evidence that in this case our quantum algorithm exhibits a polynomial speedup over the best classical algorithms for solving general SOCPs that run in time $O(n^{\omega+0.5})$ (here, $\omega$ is the matrix multiplication exponent, with a value of roughly $2.37$ in theory, and up to $3$ in practice). For the case of random SVM (support vector machine) instances of size $O(n)$, the quantum algorithm scales as $O(n^k)$, where the exponent $k$ is estimated to be $2.59$ using a least-squares power law. On the same family random instances, the estimated scaling exponent for an external SOCP solver is $3.31$ while that for a state-of-the-art SVM solver is $3.11$.

Figures

Figures reproduced from arXiv: 1908.06720 by the authors.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

A distillation-teleportation protocol for fault-tolerant QRAM
quant-ph 2025-05 accept novelty 8.0 of 10

An adaptive distillation-teleportation protocol implements a fault-tolerant QRAM query with poly(n) quantum resources and 1/poly(n) device fidelity, at the cost of an exponential classical dataset update each round.
Quantum Algorithms for Projection-Free Sparse Convex Optimization
quant-ph 2025-07 conditional novelty 5.0 of 10

Quantum Frank-Wolfe algorithms reduce dimension dependence in sparse convex optimization, from O(d) to O(sqrt d) function queries for vectors and from O(d^2) to O(d) per update step for matrices under certain assumptions.

Reference graph

Works this paper leans on

45 extracted references · 17 canonical work pages · cited by 2 Pith papers

[28]

Renato D. C. Monteiro and Takashi Tsuchiya. Polynomial convergence of primal- dual algorithms for the second-order cone program based on the MZ-family of di- rections. Math. Program., 88(1, Ser. A):61–83, 2000. ISSN 0025-5610. DOI: 10.1007/PL00011378

work page doi:10.1007/pl00011378
[26]

A quantum interior point method for LPs and SDPs

Iordanis Kerenidis and Anupam Prakash. A quantum interior point method for LPs and SDPs. ACM Transactions on Quantum Computing, 1(1), October 2020. ISSN 2643-6809. DOI: 10.1145/3406306

doi:10.1145/3406306 2020
[33]

Quantum support vector ma- chine for big data classiﬁcation.Physical Review Letters, 113(13), September 2014

Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector ma- chine for big data classiﬁcation.Physical Review Letters, 113(13), September 2014. DOI: 10.1103/physrevlett.113.130503

doi:10.1103/physrevlett.113.130503 2014
[3]

Quantum Sparse Support Vector Machines

Tomasz Arodz and Seyran Saeedi. Quantum sparse support vector machines, 2019. URL https://arxiv.org/abs/1902.01879

work page Pith review arXiv 2019
[1]

Alizadeh and D

F. Alizadeh and D. Goldfarb. Second-order cone programming.Math. Program., 95 (1, Ser. B):3–51, 2003. ISSN 0025-5610. DOI: 10.1007/s10107-002-0339-5. ISMP 2000, Part 3 (Atlanta, GA)

work page doi:10.1007/s10107-002-0339-5 2003
[2]

A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time.Quantum, 4:342, October 2020

Jonathan Allcock and Chang-Yu Hsieh. A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time.Quantum, 4:342, October 2020. ISSN 2521- 327X. DOI: 10.22331/q-2020-10-15-342

work page doi:10.22331/q-2020-10-15-342 2020
[4]

The multiplicative weights update method: a meta-algorithm and applications.Theory Comput., 8:121–164, 2012

Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications.Theory Comput., 8:121–164, 2012. DOI: 10.4086/toc.2012.v008a006

doi:10.4086/toc.2012.v008a006 2012
[5]

Lectures on modern convex optimization

Aharon Ben-Tal and Arkadi Nemirovski. Lectures on modern convex optimization. MPS/SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS), Philadelphia, PA, 2001. ISBN 0-89871-491-5. DOI: 10.1137/1.9780898718829. Analysis, algorithms, and engineering applications

doi:10.1137/1.9780898718829 2001

Show all 45 references

[6]

Cambridge University Press, Cambridge, 2004

Stephen Boyd and Lieven Vandenberghe.Convex optimization. Cambridge University Press, Cambridge, 2004. ISBN 0-521-83378-7. DOI: 10.1017/CBO9780511804441

2004 doi
[7]

Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP solvers: large speed-ups, optimality, and applications to quantum learning. In 46th International Colloquium on Automata, Accepted in Quantum 2021-04-05, click ti...

2021 doi
[8]

Fernando G. S L. Brandão, Richard Kueng, and Daniel Stilck França. Faster quantum and classical sdp approximations for quadratic binary optimization, 2020. URLhttps: //arxiv.org/abs/1909.04613

2020 arXiv
[9]

Brandão and Krysta M

Fernando G.S.L. Brandão and Krysta M. Svore. Quantum speed-ups for solving semideﬁnite programs. In58th Annual IEEE Symposium on Foundations of Com- puter Science—FOCS 2017, pages 415–426. IEEE Computer Soc., Los Alamitos, CA,

2017
[10]

Convex optimization: Algorithms and complexity

Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends® in Machine Learning, 8(3-4):231–357, 2015. DOI: 10.1561/2200000050

2015 doi
[11]

The power of block-encoded matrix powers: improved regression techniques via faster Hamil- tonian simulation

Shantanav Chakraborty, András Gilyén, and Stacey Jeﬀery. The power of block-encoded matrix powers: improved regression techniques via faster Hamil- tonian simulation. In 46th International Colloquium on Automata, Languages, and Programming, volume 132 of LIPIcs. Leibniz Int. P...

2019 doi
[12]

LIBSVM:Alibraryforsupportvectormachines

Chih-ChungChangandChih-JenLin. LIBSVM:Alibraryforsupportvectormachines. ACM Transactions on Intelligent Systems and Technology, 2(3):1–27, April 2011. DOI: 10.1145/1961189.1961199

2011
[13]

Cohen, Yin Tat Lee, and Zhao Song

Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. In STOC’19—Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 938–942. ACM, New York,
[14]

Iterative linear algebra for constrained optimization

Hilary Dollar. Iterative linear algebra for constrained optimization. PhD thesis, University of Oxford, 2005. URLhttps://www.numerical.rl.ac.uk/people/hsd/ thesismain.pdf

2005
[15]

ECOS: An SOCP solver for embedded systems

Alexander Domahidi, Eric Chu, and Stephen Boyd. ECOS: An SOCP solver for embedded systems. In 2013 European Control Conference (ECC). IEEE, July 2013. DOI: 10.23919/ecc.2013.6669541

2013
[16]

LIBLINEAR: A library for large linear classiﬁcation.Journal of machine learning research, 9(Aug):1871–1874, 2008

Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. LIBLINEAR: A library for large linear classiﬁcation.Journal of machine learning research, 9(Aug):1871–1874, 2008. URLhttps://www.jmlr.org/papers/volume9/ fan08a/fan08a

2008
[17]

Optimizing quantum optimization algorithms via faster quantum gradient computation

András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe. Optimizing quantum optimization algorithms via faster quantum gradient computation. InProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1425–
[18]

Quantum singu- lar value transformation and beyond: exponential improvements for quantum ma- trix arithmetics

András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singu- lar value transformation and beyond: exponential improvements for quantum ma- trix arithmetics. In STOC’19—Proceedings of the 51st Annual ACM SIGACT Sym- posium on Theory of Computing, pages 193–204. ACM, ...

2019
[19]

Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension, 2018

András Gilyén, Seth Lloyd, and Ewin Tang. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension, 2018. URLhttps://arxiv. org/abs/1811.04909

2018 arXiv
[20]

Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Com- Accepted in Quantum 2021-04-05, click title to verify. Published under CC-BY 4.0. 22 puting (Philadelphia, PA, 1996), pages 21...

2021
[21]

Harrow, Avinatan Hassidim, and Seth Lloyd

Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for lin- ear systems of equations. Physical Review Letters, 103(15), October 2009. DOI: 10.1103/physrevlett.103.150502

2009 doi
[22]

Training linear SVMs in linear time

Thorsten Joachims. Training linear SVMs in linear time. InProceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’06, page 217–226, New York, NY, USA, 2006. Association for Computing Ma- chinery. ISBN 1595933395. DOI: 10.1145/11...

2006
[23]

Karmarkar

N. Karmarkar. A new polynomial-time algorithm for linear programming. InProceed- ings of the sixteenth annual ACM symposium on Theory of computing - STOC'84, pages 302–311. ACM Press, 1984. DOI: 10.1145/800057.808695

1984
[24]

Quantum recommendation systems

Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) , volume 67 of Leibniz International Proceed- ings in Informatics (LIPIcs), pages 49:1–49:21, Dag...

2017 doi
[25]

Quantum gradient descent for linear sys- tems and least squares

Iordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear sys- tems and least squares. Phys. Rev. A, 101:022316, Feb 2020. DOI: 10.1103/Phys- RevA.101.022316

2020 doi
[27]

Solving empirical risk minimization in the current matrix multiplication time

Yin Tat Lee, Zhao Song, and Qiuyi Zhang. Solving empirical risk minimization in the current matrix multiplication time. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 ofPro- ceedings of Machine Learning R...
[29]

Yu. E. Nesterov and M. J. Todd. Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res., 22(1):1–42, 1997. ISSN 0364-765X. DOI: 10.1287/moor.22.1.1

1997 doi
[30]

Yu. E. Nesterov and M. J. Todd. Primal-dual interior-point methods for self- scaled cones. SIAM J. Optim. , 8(2):324–364, 1998. ISSN 1052-6234. DOI: 10.1137/S1052623495290209

1998 doi
[31]

URL http://proceedings.mlr.press/v99/lee19a.html

PMLR. URL http://proceedings.mlr.press/v99/lee19a.html
[32]

Nielsen and Isaac L

Michael A. Nielsen and Isaac L. Chuang.Quantum Computation and Quantum Infor- mation. Cambridge University Press, 2009. DOI: 10.1017/cbo9780511976667

2009 doi
[34]

Iterative methods for sparse linear systems

Yousef Saad. Iterative methods for sparse linear systems. Society for Industrial and Applied Mathematics, Philadelphia, PA, second edition, 2003. ISBN 0-89871-534-2. DOI: 10.1137/1.9780898718003. Accepted in Quantum 2021-04-05, click title to verify. Published under CC-BY 4.0. 23

2003 doi
[35]

Applied linear statistical models, volume 4

John Neter, Michael H Kutner, Christopher J Nachtsheim, and William Wasserman. Applied linear statistical models, volume 4. Irwin Chicago, 1996

1996
[36]

Gaussian elimination is not optimal.Numerische Mathematik, 13(4): 354–356, August 1969

Volker Strassen. Gaussian elimination is not optimal.Numerische Mathematik, 13(4): 354–356, August 1969. DOI: 10.1007/bf02165411

1969 doi
[37]

Suykens and J

J.A.K. Suykens and J. Vandewalle. Least squares support vector machine classiﬁers. Neural Processing Letters, 9(3):293–300, 1999. DOI: 10.1023/a:1018628609742

1999 doi
[38]

Suykens, J

J.A.K. Suykens, J. De Brabanter, L. Lukas, and J. Vandewalle. Weighted least squares support vector machines: robustness and sparse approximation.Neurocomputing, 48 (1-4):85–105, October 2002. DOI: 10.1016/s0925-2312(01)00644-0

2002 doi
[39]

Peter W. Shor. Algorithms for quantum computation: discrete logarithms and fac- toring. In 35th Annual Symposium on Foundations of Computer Science (Santa Fe, NM, 1994), pages 124–134. IEEE Comput. Soc. Press, Los Alamitos, CA, 1994. DOI: 10.1109/SFCS.1994.365700

1994
[40]

Improvements in quantum SDP- solving with applications

Joran van Apeldoorn and András Gilyén. Improvements in quantum SDP- solving with applications. In 46th International Colloquium on Automata, Lan- guages, and Programming, volume 132 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 99, 15. Schloss Dagstuhl. Leibniz-Zent. In...

2019 doi
[41]

Quan- tum SDP-solvers: Better upper and lower bounds

Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quan- tum SDP-solvers: Better upper and lower bounds. In2017 IEEE 58th Annual Sym- posium on Foundations of Computer Science (FOCS). IEEE, October 2017. DOI: 10.1109/focs.2017.44

2017 doi
[42]

Todd, and Shinji Mizuno

Yinyu Ye, Michael J. Todd, and Shinji Mizuno. AnO(√nL)-iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res., 19(1):53–67, 1994. ISSN 0364-765X. DOI: 10.1287/moor.19.1.53. Accepted in Quantum 2021-04-05, click title to verify. Published under CC-BY 4.0. 24

1994 doi
[43]

Quantum SVM via SOCP experiment logs

Daniel Szilagyi, Iordanis Kerenidis, and Anupam Prakash. Quantum SVM via SOCP experiment logs. Mar 2021. DOI: 10.6084/m9.ﬁgshare.11778189.v1

2021 doi
[1444]

DOI: 10.1137/1.9781611975482.87

SIAM, Philadelphia, PA, 2019. DOI: 10.1137/1.9781611975482.87

2019 doi
[2017]

DOI: 10.1109/focs.2017.45

2017 doi

Pith tools

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

[1] [28]

Renato D. C. Monteiro and Takashi Tsuchiya. Polynomial convergence of primal- dual algorithms for the second-order cone program based on the MZ-family of di- rections. Math. Program., 88(1, Ser. A):61–83, 2000. ISSN 0025-5610. DOI: 10.1007/PL00011378

work page doi:10.1007/pl00011378

[2] [26]

A quantum interior point method for LPs and SDPs

Iordanis Kerenidis and Anupam Prakash. A quantum interior point method for LPs and SDPs. ACM Transactions on Quantum Computing, 1(1), October 2020. ISSN 2643-6809. DOI: 10.1145/3406306

doi:10.1145/3406306 2020

[3] [33]

Quantum support vector ma- chine for big data classiﬁcation.Physical Review Letters, 113(13), September 2014

Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector ma- chine for big data classiﬁcation.Physical Review Letters, 113(13), September 2014. DOI: 10.1103/physrevlett.113.130503

doi:10.1103/physrevlett.113.130503 2014

[4] [3]

Quantum Sparse Support Vector Machines

Tomasz Arodz and Seyran Saeedi. Quantum sparse support vector machines, 2019. URL https://arxiv.org/abs/1902.01879

work page Pith review arXiv 2019

[5] [1]

Alizadeh and D

F. Alizadeh and D. Goldfarb. Second-order cone programming.Math. Program., 95 (1, Ser. B):3–51, 2003. ISSN 0025-5610. DOI: 10.1007/s10107-002-0339-5. ISMP 2000, Part 3 (Atlanta, GA)

work page doi:10.1007/s10107-002-0339-5 2003

[6] [2]

A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time.Quantum, 4:342, October 2020

Jonathan Allcock and Chang-Yu Hsieh. A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time.Quantum, 4:342, October 2020. ISSN 2521- 327X. DOI: 10.22331/q-2020-10-15-342

work page doi:10.22331/q-2020-10-15-342 2020

[7] [4]

The multiplicative weights update method: a meta-algorithm and applications.Theory Comput., 8:121–164, 2012

Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications.Theory Comput., 8:121–164, 2012. DOI: 10.4086/toc.2012.v008a006

doi:10.4086/toc.2012.v008a006 2012

[8] [5]

Lectures on modern convex optimization

Aharon Ben-Tal and Arkadi Nemirovski. Lectures on modern convex optimization. MPS/SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS), Philadelphia, PA, 2001. ISBN 0-89871-491-5. DOI: 10.1137/1.9780898718829. Analysis, algorithms, and engineering applications

doi:10.1137/1.9780898718829 2001