Pith. sign in

REVIEW 3 major objections 5 minor 84 references

Quantum Algorithms for Projection-Free Sparse Convex Optimization

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

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

Pith's one-line read The paper claims that quantum search and quantum singular-value estimation can cut the bottleneck of Frank-Wolfe optimization from linear to square-root dimension dependence.

desk verdict Vector-domain quantum Frank-Wolfe is solid; Theorem 4's power-method step has a load-bearing gap, so the matrix claims need major revision before acceptance. read the letter →

arxiv 2507.08543 v1 pith:KDKC72EC submitted 2025-07-11 quant-ph cs.LG

Jianhao He , John C.S. Lui This is my paper · ORCID
classification quant-phcs.LG MSC 68Q1290C2581P68
keywords quantumalgorithmsFrank-Wolfeconvexoptimizationsparseconstraintsnuclearnormsingularvalueestimationpowermethodprojection-free
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper sets out to show that the projection-free Frank-Wolfe method can be made substantially faster on high-dimensional sparse and low-rank constrained problems by replacing its two classical bottlenecks—scanning gradient coordinates and computing top singular vectors—with quantum search and quantum singular-value primitives. In the vector domain, it claims that for $\ell^1$-ball, simplex, and latent group norm constraints, an $\varepsilon$-optimal solution can be found in $T = 4C_f/\varepsilon - 2$ rounds using $O(\sqrt{d}\log(C_f/(p\varepsilon)))$ function-value oracle calls per round, compared with $O(d)$ for the classical Frank-Wolfe method; with a bounded-error Jordan gradient estimate, the per-round calls drop to $O(1)$. In the matrix domain, it claims that for nuclear-norm constraints, the update direction can be computed in $\tilde{O}(rd/\varepsilon^2)$ or $\tilde{O}(\sqrt{r}d/\varepsilon^3)$ time per round under quantum access to the gradient matrix, improving on classical power and Lanczos methods by a factor of at least $\sqrt{d}$ in dimension. If these claims hold, projection-free optimization inherits a dimension-dependent quantum speedup for a large class of machine-learning and operations-research problems, with the caveat that the matrix results count update computation only and assume gradients are precomputed and stored in a quantum data structure.

What carries the argument

The machinery is a small set of quantum oracles wired into the Frank-Wolfe loop. A two-query quantum circuit converts the function-value oracle into a gradient-component oracle $|i\rangle|x\rangle|0\rangle \mapsto |i\rangle|x\rangle|g_i(x)\rangle$, and an approximate quantum maximum-finding circuit extracts the coordinate of largest estimated gradient in $O(\sqrt{d}\log(1/\delta))$ applications even when estimates carry bounded error. For matrices, the first algorithm (QTSVE) prepares the gradient matrix as a quantum superposition, applies quantum singular value estimation to label singular values, uses quantum maximum finding to isolate the top singular subspace, and reads out the top left and right singular vectors with $\ell^2$ tomography; the second (QPM) replaces this with repeated quantum matrix-vector multiplication, a quantum power method, followed by tomography. The convergence argument in both cases absorbs the subroutine error into the Frank-Wolfe step-size schedule, so the classical iteration count $O(C_f/\varepsilon)$ is unchanged.

What would settle it

Run the quantum Frank-Wolfe matrix algorithm on a smooth nuclear-norm-constrained problem with a simulator that charges the full cost of building the Assumption 4 gradient data structure from scratch at every iteration; if the measured per-round time scales as $d^2$ or worse instead of $\tilde{O}(rd/\varepsilon^2)$, the end-to-end speedup claim is refuted. Alternatively, proving a quantum lower bound of $\Omega(d)$ for preparing the row-norm superposition of an adversarially changing Frank-Wolfe gradient sequence would falsify the assumption under which Theorem 3 holds.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorem 1 and its extensions, is that every Frank-Wolfe step over an atomic constraint set reduces to an approximate extremal search over gradient components, and that quantum amplitude amplification finds the best atom with $O(\sqrt{N})$ oracle queries rather than $O(N)$. For $D = \{x : \|x\|_1 \le 1\}$ or $D = \Delta_d$, the paper proves a quantum Frank-Wolfe algorithm with $T = 4C_f/\varepsilon - 2$ rounds, where each round uses $O(\sqrt{d}\log(C_f/(p\varepsilon)))$ calls to a function-value oracle and succeeds with probability $1-p$; the key to convergence is that the maximum-finding subroutine is robust to gradient-estimation error, so a slightly suboptimal atom still preserves the classical Frank-Wolfe recurrence. For $D = \{X : \|X\|_{\mathrm{tr}} \le 1\}$, the paper claims a quantum top singular vector extraction update with per-round time $\tilde{O}(r\sigma_1^3(M)d/((\sigma_1(M)-\sigma_2(M))\varepsilon^2))$ and a quantum power method update with per-round time $\tilde{O}(\sqrt{r}\sigma_1^4(M)d/((1-\sigma_1(M))\gamma_{\min}'^3\varepsilon^3))$, both beating classical power and Lanczos methods in dimension $d$ under the quantum matrix access assumption of Assumption 4.

Load-bearing premise

The matrix speedups assume the gradient matrix is already stored in a quantum memory that answers row-sum queries instantly and can be refreshed for free as the optimization proceeds; if constructing or maintaining that memory costs more than the saved update time, the claimed dimension speedup is not end-to-end.

Editorial extensions

If this is right

  • For $\ell^1$-ball and simplex constraints, every Frank-Wolfe iteration becomes implementable with $O(\sqrt{d})$ function-value queries, so an $\varepsilon$-optimal solution costs $O((C_f/\varepsilon)\sqrt{d}\log(C_f/(p\varepsilon)))$ queries in total.
  • With a bounded-error Jordan gradient estimator, each vector iteration needs only a constant number of function-value calls, at the price of more qubits and $O(d\log d)$ gates.
  • For nuclear-norm constraints with quantum matrix access, the per-round update direction can be computed in $\tilde{O}(rd/\varepsilon^2)$ via quantum top singular vector extraction or $\tilde{O}(\sqrt{r}d/\varepsilon^3)$ via the quantum power method, improving on the classical power and Lanczos methods by a factor of at least $\sqrt{d}$ in dimension.
  • The latent group norm extension gives an $O(\sqrt{|G||g|_{\max}})$ query cost per round, a $\sqrt{|G|}$-fold saving over the classical scan over all group coordinates.
  • The iteration count of the classical Frank-Wolfe algorithm, $O(C_f/\varepsilon)$, is preserved in all variants, so the speedup is concentrated in the linear subproblem that is the usual bottleneck.

Reading between the lines

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

  • If the Assumption 4 data structure can be updated incrementally between Frank-Wolfe iterations, the matrix results would be end-to-end; the paper does not provide such an update scheme, so a natural next step is to design one or prove a lower bound on maintaining row-norm superpositions under low-rank updates.
  • The same error-tolerant maximum-finding primitive could accelerate away-step Frank-Wolfe and pairwise conditional gradient methods, whose linear oracles are also atomic-set searches over gradient-related scores.
  • In stochastic or online Frank-Wolfe settings, replacing exact gradient oracles with quantum gradient estimators could yield analogous $\sqrt{d}$ reductions in per-step query complexity; the paper lists online and stochastic extension as future work.
  • The parallelization remark points to a practical route: using $O(d)$ quantum processing units removes the tomography $d$-factor, suggesting that small-dimensional experiments could test the update-direction speedup before large fault-tolerant memories exist.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper proposes quantum Frank-Wolfe algorithms for projection-free convex optimization over vector and matrix domains. For the vector domain, the algorithms use a finite-difference gradient oracle combined with quantum maximum finding to locate the coordinate of largest gradient magnitude, claiming O(√d log(...)) function-value oracle calls per iteration for ℓ1-ball and simplex constraints, and O(1) calls per iteration when a bounded-error Jordan gradient subroutine is used. For the matrix domain with nuclear-norm constraints, the paper proposes two update-direction subroutines: one based on quantum singular value estimation and tomography (QTSVE), and one based on a quantum power method (QPM). The claimed update-step complexities are O~(rσ1^3(M)d/((σ1(M)−σ2(M))ε^2)) and O~(√rσ1^4(M)d/((1−σ1(M))γ'^3_min ε^3)), respectively, compared with classical power-method and Lanczos baselines.

Significance. The vector-domain results are a genuine and largely coherent contribution: the finite-difference error is balanced against the Frank-Wolfe curvature, and the maximum-finding error is propagated through the standard Frank-Wolfe analysis in a clean way. The QTSVE matrix result is plausible under the stated quantum-access assumption, though it inherits the usual caveats of quantum data structures and tomography. The QPM result, however, rests on an unsupported power-method convergence statement, and this is load-bearing for Theorem 4 and for the abstract's O~(√rd/ε^3) claim. The paper is also careful to state in Remark 2 that the matrix-domain speedups cover only the update-direction computation, excluding gradient evaluation and data loading; that caveat is important and should be reflected in the abstract. Overall, the work is interesting and technically substantial, but the matrix QPM part needs a corrected analysis before the main claims can be accepted.

major comments (3)
  1. [Appendix B.11, Eq. (89); Theorem 4] The assertion 'we settle down k = 2C0 σ1(M) ln d / ε' to obtain |z_u^T M z_v / (||z_u|| ||z_v||) − σ1(M)| ≤ ε/2 is not derived and is not a valid power-method convergence bound in general. Classical power-method convergence depends on the spectral gap σ1(M) − σ2(M) and on the initial overlap of the start vector with the top singular subspace; for a start vector nearly orthogonal to that subspace, the required number of iterations can scale as Θ((1/(σ1−σ2)) log(1/overlap)), which can exceed C0/ε for any fixed C0. The quantity γ'_min appears in the time complexity but is not used to control Eq. (89). Unless a correct gap- and overlap-aware analysis is provided, Algorithm 4 may not return an ε-close top singular vector after k steps, so Theorem 4 and the abstract's O~(√rd/ε^3) update-step claim are not established.
  2. [Appendix B.10, Lemma 9] The proof of Lemma 9 treats the iterates z_l as unnormalized vectors satisfying ||z_l − M z_{l−1}|| ≤ ε and derives a final vector error by induction, but Lemma 8 creates normalized quantum states |M z⟩. The accumulated fidelity error for normalized iterates, the failure probability over k repetitions, and the precise role of γ'_min in controlling the final normalized error are not quantified. Since the theorem's time complexity depends on γ'^3_min, the proof needs a complete argument relating γ'_min, the per-step approximation error, and the final infidelity of |(M^T M)^k b⟩.
  3. [Assumption 4 and Remark 2] The matrix-domain speedups require, at every Frank-Wolfe iteration t, a quantum data structure for the gradient matrix M_t that supports |i⟩|0⟩ → |i⟩|M_{i,·}⟩ and |0⟩ → Σ_i ||M_{i,·}|| |i⟩ in time O~(1). The paper does not describe how such a structure is constructed or updated as the iterate X_t changes. The text explicitly states in Remark 2 that the analysis covers only update-direction computation and excludes gradient evaluation and data loading, so this is a scope limitation rather than a hidden error; nevertheless, the abstract's unqualified 'time complexity' phrasing should carry this caveat, and Table 2 should make explicit which terms are included in each entry.
minor comments (5)
  1. [Theorem 4 statement] The theorem statement omits the assumptions σmax(M) ≤ 1 and σ1(M) < 1 that appear in Lemma 9 and in the proof of Theorem 4; these should be stated explicitly, since the QPM analysis depends on them.
  2. [Table 1] The 'Query complexity' column mixes per-iteration and total complexities: the classical entries O(d) appear to be per iteration, while the quantum entries O(√d log(Cf/pε)) are also per iteration, but the abstract quotes O(√d/ε) as the total complexity. Please clarify which convention is used in each row.
  3. [Appendix B.2, Lemma 4 proof] The final paragraph of the proof conflates maximum-finding and minimum-finding language and contains a garbled sentence about the relation between g_i(x) and |∇f_j(x)|; the argument should be rewritten to cleanly separate the maximum and minimum cases and the ±2ε guarantee.
  4. [Table 2] The caption has a typo: 'σ1(M ) and is the largest and the second largest singular value' should read 'σ1(M) and σ2(M) are the largest and the second largest singular values.'
  5. [Appendix B.11] The word 'Simalar' should be 'Similar'.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the central derivations compose external quantum primitives rather than re-importing the paper's own conclusions.

full rationale

The vector-domain results (Theorems 1, 2, 5, 6) derive the Frank-Wolfe update from a function-value oracle via finite-difference gradient oracles (Lemma 3), quantum minimum/maximum finding (Lemma 4), and, for Theorem 5, the bounded-error Jordan gradient estimator. The only self-citation is [36] for that estimator, but the relevant lemma (Lemma 10) is reproved in full in Appendix B.4, so the citation is not load-bearing in a circular way. The matrix-domain results are built on the external QSVE and quantum matrix-vector multiplication results of [6, 44, 15] and on standard ℓ2 tomography; Assumption 4 is an access-model premise, not a quantity fitted from the paper's own claims. The one passage that deserves scrutiny is Equation (89) in Appendix B.11, which asserts the power-method convergence bound |z_u^T M z_v / (||z_u|| ||z_v||) - sigma_1(M)| <= eps/2 for k = 2 C0 sigma_1(M) ln d / eps without a derivation and without spectral-gap or start-overlap dependence. This is a correctness gap in the proof of Theorem 4, not a circularity: it is an unsupported mathematical assertion rather than an input that is re-labeled as a prediction. Accordingly, no step in the derivation reduces by construction to its own assumption, and the circularity score is low.

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

The paper introduces no new physical entities. Its central results rest on standard convex-analysis assumptions, on a quantum oracle model, and on several imported quantum subroutines. The most fragile inputs are Assumption 4 (quantum access to every gradient matrix with O~(1) state preparation) and the gamma'_min lower bound in the quantum power method, neither of which is justified with high-probability guarantees or an update mechanism.

free parameters (5)
  • finite-difference step sigma_t = Cf/(sqrt(d) L (t+2))
    Chosen in Theorem 1 to balance gradient approximation error against the convergence budget; not fitted to data.
  • Jordan gradient radius r_t = rho Cf / (16 pi d^2 (d/rho + 1) L (t+2))
    Chosen in Theorem 5 so the O(1)-query Jordan gradient error fits the Frank-Wolfe convergence argument.
  • tomography precision delta_t = Cf/(2 (t+2) sigma1(M_t))
    Set in Theorem 3 to keep the top singular vector error within the curvature budget.
  • power iteration count k_t = 2 C0 sigma1(M_t) ln(d/epsilon)
    Set in Theorem 4 so the power method error is at most epsilon/2; C0 is treated as a constant even though classical power method convergence depends on the spectral gap.
  • quantum multiplication precision delta_t = epsilon gamma'_min / (16 sigma1(M))
    Set in Theorem 4 to control accumulated error from repeated quantum matrix-vector multiplication.
assumptions (8)
  • domain assumption f is convex and L-smooth
    Assumption 1; used for the finite-difference gradient error bound and the curvature bound.
  • domain assumption D is compact and convex with bounded diameter
    Assumption 2; ensures the curvature Cf is finite.
  • domain assumption An exact unitary function value oracle Uf exists
    Assumption 3; needed for the quantum gradient circuit and the Jordan gradient estimator.
  • domain assumption Quantum access to each gradient matrix in O~(1) time at every iteration
    Assumption 4 plus Remark 2; the matrix complexity excludes gradient evaluation and data loading costs.
  • standard math Correctness of cited quantum subroutines (QSVE, Durr-Hoyer max finding, quantum matrix-vector multiplication, bounded-error Jordan gradient)
    Lemmas 5, 6, 8, and 10 are imported from [6, 42, 47, 15, 36] and treated as black boxes.
  • ad hoc to paper Spectral gap condition sigma1(M) > sigma2(M) and QSVE precision epsilon_t <= (sigma1 - sigma2)/2
    Theorem 3 requires this to ensure quantum max-finding isolates the top singular vector; the complexity diverges as the gap shrinks.
  • ad hoc to paper Deterministic lower bound gamma'_min on ||(M^T M)^i b|| for all i in [k]
    Lemma 9 and Theorem 4 assume the random initial vector b is never nearly orthogonal to the top singular subspace; no high-probability bound is provided.
  • ad hoc to paper sigma_max(M) <= 1 and sigma1(M) < 1 for the quantum power method
    Lemma 9 and Theorem 4 use (1 - sigma1(M)) in the denominator, which blows up as sigma1 approaches 1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Algorithms for Projection-Free Sparse Convex Optimization." pith.science (2026). https://pith.science/paper/KDKC72EC

@misc{pith2026250708543,
  author       = {Pith},
  title        = {Pith review of: Quantum Algorithms for Projection-Free Sparse Convex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KDKC72EC}},
  note         = {Machine review of arXiv:2507.08543}
}
abstract

This paper considers the projection-free sparse convex optimization problem for the vector domain and the matrix domain, which covers a large number of important applications in machine learning and data science. For the vector domain $\mathcal{D} \subset \mathbb{R}^d$, we propose two quantum algorithms for sparse constraints that finds a $\varepsilon$-optimal solution with the query complexity of $O(\sqrt{d}/\varepsilon)$ and $O(1/\varepsilon)$ by using the function value oracle, reducing a factor of $O(\sqrt{d})$ and $O(d)$ over the best classical algorithm, respectively, where $d$ is the dimension. For the matrix domain $\mathcal{D} \subset \mathbb{R}^{d\times d}$, we propose two quantum algorithms for nuclear norm constraints that improve the time complexity to $\tilde{O}(rd/\varepsilon^2)$ and $\tilde{O}(\sqrt{r}d/\varepsilon^3)$ for computing the update step, reducing at least a factor of $O(\sqrt{d})$ over the best classical algorithm, where $r$ is the rank of the gradient matrix. Our algorithms show quantum advantages in projection-free sparse convex optimization problems as they outperform the optimal classical methods in dependence on the dimension $d$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

84 extracted references · 68 canonical work pages

  1. [1]

    Linear convergence of a frank-wolfe type algorithm over trace-norm balls

    Zeyuan Allen-Zhu, Elad Hazan, Wei Hu, and Yuanzhi Li. Linear convergence of a frank-wolfe type algorithm over trace-norm balls. Advances in neural information processing systems , 30, 2017

    2017

  2. [2]

    Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations

    A Ambainis. Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations. In Symp. Theoretical Aspects of Computer Science (STACS 2012), volume 14, pages 636–47, 2012

    2012

  3. [3]

    Quantum algorithms for matching and network flows

    Andris Ambainis and Robert ˇSpalek. Quantum algorithms for matching and network flows. In Annual Symposium on Theoretical Aspects of Computer Science , pages 172–183, Berlin, 2006. Springer

    2006

  4. [4]

    Quantum speedups for linear programming via interior point meth- ods

    Simon Apers and Sander Gribling. Quantum speedups for linear programming via interior point meth- ods. arXiv preprint arXiv:2311.03215 , 2023

    arXiv 2023

  5. [5]

    Hybrid conditional gradient-smoothing algo- rithms with applications to sparse and low rank regularization

    Andreas Argyriou, Marco Signoretto, and Johan Suykens. Hybrid conditional gradient-smoothing algo- rithms with applications to sparse and low rank regularization. Regularization, Optimization, Kernels, and Support Vector Machines , pages 53–82, 2014

    2014

  6. [6]

    Quantum algorithms for svd-based data representation and analysis

    Armando Bellante, Alessandro Luongo, and Stefano Zanero. Quantum algorithms for svd-based data representation and analysis. Quantum Machine Intelligence , 4(2):20, 2022

    work page 2022

  7. [7]

    A theoretical and empirical comparison of gradient approximations in derivative-free optimization

    Albert S Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg. A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Foundations of Com- putational Mathematics , 22(2):507–560, 2022

    work page 2022

  8. [8]

    Frank–wolfe and friends: a journey into projection-free first-order optimization methods

    Immanuel M Bomze, Francesco Rinaldi, and Damiano Zeffiro. Frank–wolfe and friends: a journey into projection-free first-order optimization methods. 4OR, 19:313–345, 2021

    work page 2021

Show all 84 references
  1. [9]

    Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning

    Fernando GSL Brand˜ ao, 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, Languages, and Programming , pages 27–1. Sch...

    2019

  2. [10]

    Quantum speed-ups for solving semidefinite programs

    Fernando GSL Brand˜ ao and Krysta M Svore. Quantum speed-ups for solving semidefinite programs. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science , pages 415–426, Piscataway, NJ, 2017. IEEE

    2017

  3. [11]

    Quantum amplitude amplification and estimation

    Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53–74, 2002

    2002

  4. [12]

    A tight upper bound on the rate of convergence of frank-wolfe algorithm

    Michael D Canon and Clifton D Cullum. A tight upper bound on the rate of convergence of frank-wolfe algorithm. SIAM Journal on Control , 6(4):509–516, 1968

    1968

  5. [13]

    Quantum bandits

    Balthazar Casal´ e, Giuseppe Di Molfetta, Hachem Kadri, and Liva Ralaivola. Quantum bandits. Quan- tum Machine Intelligence , 2(1):1–7, 2020

    2020

  6. [14]

    Quantum algorithms and lower bounds for convex optimization

    Shouvanik Chakrabarti, Andrew M Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. Quantum, 4:221, 2020

    2020

  7. [15]

    The power of block-encoded matrix powers: Improved regression techniques via faster hamiltonian simulation

    Shantanav Chakraborty, Andr´ as Gily´ en, and Stacey Jeffery. The power of block-encoded matrix powers: Improved regression techniques via faster hamiltonian simulation. In 46th International Colloquium on Automata, Languages, and Programming, pages 33–1. Schloss Dagstuhl–Leib...

    2019

  8. [16]

    Projection-free online optimization with stochastic gradient: From convexity to submodularity

    Lin Chen, Christopher Harshaw, Hamed Hassani, and Amin Karbasi. Projection-free online optimization with stochastic gradient: From convexity to submodularity. In International Conference on Machine Learning, pages 814–823. PMLR, 2018. 10

    2018

  9. [17]

    Quantum algorithms and lower bounds for linear regression with norm constraints

    Yanlin Chen and Ronald de Wolf. Quantum algorithms and lower bounds for linear regression with norm constraints. In 50th International Colloquium on Automata, Languages, and Programming , pages 38–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2023

    2023

  10. [18]

    A quantum speed-up for approximating the top eigen- vectors of a matrix

    Yanlin Chen, Andr´ as Gily´ en, and Ronald de Wolf. A quantum speed-up for approximating the top eigen- vectors of a matrix. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 994–1036. SIAM, 2025

    2025

  11. [19]

    Quantum langevin dynamics for optimization

    Zherui Chen, Yuchen Lu, Hao Wang, Yizhou Liu, and Tongyang Li. Quantum langevin dynamics for optimization. Communications in Mathematical Physics , 406(3):52, 2025

    2025

  12. [20]

    Quantum algorithm for systems of lin- ear equations with exponentially improved dependence on precision

    Andrew M Childs, Robin Kothari, and Rolando D Somma. Quantum algorithm for systems of lin- ear equations with exponentially improved dependence on precision. SIAM Journal on Computing , 46(6):1920–1950, 2017

    1920

  13. [21]

    Lifted coordinate descent for learning with trace- norm regularization

    Miroslav Dudik, Zaid Harchaoui, and J´ erˆ ome Malick. Lifted coordinate descent for learning with trace- norm regularization. In Artificial intelligence and statistics , pages 327–336. PMLR, 2012

    2012

  14. [22]

    Conditional gradient algorithms with open loop step size rules

    Joseph C Dunn and S Harshbarger. Conditional gradient algorithms with open loop step size rules. Journal of Mathematical Analysis and Applications , 62(2):432–444, 1978

    1978

  15. [23]

    Quantum query complexity of some graph problems

    Christoph D¨ urr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing , 35(6):1310–1328, 2006

    2006

  16. [24]

    A quantum algorithm for finding the minimum

    Christoph Durr and Peter Hoyer. A quantum algorithm for finding the minimum. arXiv preprint quant-ph/9607014, 1996

    1996 arXiv

  17. [25]

    An algorithm for quadratic programming

    Marguerite Frank et al. An algorithm for quadratic programming. Naval research logistics quarterly , 3(1-2):95–110, 1956

    1956

  18. [26]

    Faster projection-free convex optimization over the spectrahedron

    Dan Garber. Faster projection-free convex optimization over the spectrahedron. Advances in Neural Information Processing Systems, 29, 2016

    2016

  19. [27]

    A linearly convergent variant of the conditional gradient algorithm under strong convexity, with applications to online and stochastic optimization

    Dan Garber and Elad Hazan. A linearly convergent variant of the conditional gradient algorithm under strong convexity, with applications to online and stochastic optimization. SIAM Journal on Optimization, 26(3):1493–1528, 2016

    2016

  20. [28]

    Optimizing quantum optimization algo- rithms via faster quantum gradient computation

    Andr´ as Gily´ en, Srinivasan Arunachalam, and Nathan Wiebe. Optimizing quantum optimization algo- rithms via faster quantum gradient computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1425–1444, Philadelphia, PA, 2019. SIAM

    2019

  21. [29]

    A fast quantum mechanical algorithm for database search

    Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty- eighth annual ACM symposium on Theory of computing , pages 212–219, New York, NY, 1996. ACM

    1996

  22. [30]

    Conditional gradient algorithms for norm- regularized smooth convex optimization

    Zaid Harchaoui, Anatoli Juditsky, and Arkadi Nemirovski. Conditional gradient algorithms for norm- regularized smooth convex optimization. Mathematical Programming, 152(1):75–112, 2015

    2015

  23. [31]

    Quantum algorithm for linear systems of equa- tions

    Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equa- tions. Physical review letters , 103(15):150502, 2009

    2009

  24. [32]

    Stochastic conditional gradi- ent++:(non) convex minimization and continuous submodular maximization

    Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Zebang Shen. Stochastic conditional gradi- ent++:(non) convex minimization and continuous submodular maximization. SIAM Journal on Opti- mization, 30(4):3315–3344, 2020

    2020

  25. [33]

    Projection-free online learning

    Elad Hazan and Satyen Kale. Projection-free online learning. arXiv preprint arXiv:1206.4657 , 2012

    2012 arXiv

  26. [34]

    Near-optimal algorithms for online matrix predic- tion

    Elad Hazan, Satyen Kale, and Shai Shalev-Shwartz. Near-optimal algorithms for online matrix predic- tion. In Conference on Learning Theory , pages 38–1. JMLR Workshop and Conference Proceedings, 2012. 11

    2012

  27. [35]

    Variance-reduced and projection-free stochastic optimization

    Elad Hazan and Haipeng Luo. Variance-reduced and projection-free stochastic optimization. In Inter- national Conference on Machine Learning , pages 1263–1271. PMLR, 2016

    2016

  28. [36]

    Jianhao He, Chengchang Liu, Xutong Liu, Lvzhou Li, and John C.S. Lui. Quantum algorithm for online exp-concave optimization. In Proceedings of the 41st International Conference on Machine Learning , volume 235 of Proceedings of Machine Learning Research, pages 17946–17971. PML...

    2024

  29. [37]

    Quantum algorithm for online convex opti- mization

    Jianhao He, Feidiao Yang, Jialin Zhang, and Lvzhou Li. Quantum algorithm for online convex opti- mization. Quantum Science and Technology, 7(2):025022, 2022

    2022

  30. [38]

    Quantum search with prior knowledge

    Xiaoyu He, Jialin Zhang, and Xiaoming Sun. Quantum search with prior knowledge. arXiv preprint arXiv:2009.08721, 2020

    2009 arXiv

  31. [39]

    Revisiting frank-wolfe: Projection-free sparse convex optimization

    Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In International Conference on Machine Learning , pages 427–435. PMLR, 2013

    2013

  32. [40]

    Structured variable selection with sparsity- inducing norms

    Rodolphe Jenatton, Jean-Yves Audibert, and Francis Bach. Structured variable selection with sparsity- inducing norms. The Journal of Machine Learning Research , 12:2777–2824, 2011

    2011

  33. [41]

    Fast quantum algorithm for numerical gradient estimation

    Stephen P Jordan. Fast quantum algorithm for numerical gradient estimation. Physical review letters , 95(5):050501, 2005

    2005

  34. [42]

    Quantum expectation-maximization for gaussian mixture models

    Iordanis Kerenidis, Alessandro Luongo, and Anupam Prakash. Quantum expectation-maximization for gaussian mixture models. In International Conference on Machine Learning , pages 5187–5197. PMLR, 2020

    2020

  35. [43]

    Quantum recommendation systems

    Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) . Schloss Dagstuhl-Leibniz-Zentrum fuer Infor- matik, 2017

    2017

  36. [44]

    Quantum gradient descent for linear systems and least squares

    Iordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear systems and least squares. Physical Review A , 101(2):022316, 2020

    2020

  37. [45]

    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):1–32, 2020

    2020

  38. [47]

    Quantum algorithms for portfolio optimiza- tion

    Iordanis Kerenidis, Anupam Prakash, and D´ aniel Szil´ agyi. Quantum algorithms for portfolio optimiza- tion. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, pages 147–155, 2019

    2019

  39. [48]

    Quantum algorithms for second-order cone programming and support vector machines

    Iordanis Kerenidis, Anupam Prakash, and D´ aniel Szil´ agyi. Quantum algorithms for second-order cone programming and support vector machines. arXiv preprint arXiv:1908.06720 , 2019

    1908 arXiv

  40. [49]

    A quantum interior-point method for second- order cone programming

    Iordanis Kerenidis, Anupam Prakash, and D´ aniel Szil´ agyi. A quantum interior-point method for second- order cone programming. [Research Report] IRIF. 2019. ffhal-02138307 , 2019

    2019

  41. [50]

    Estimating the largest eigenvalue by the power and lanczos algorithms with a random start

    Jacek Kuczy´ nski and Henryk Wo´ zniakowski. Estimating the largest eigenvalue by the power and lanczos algorithms with a random start. SIAM journal on matrix analysis and applications , 13(4):1094–1122, 1992

    1992

  42. [51]

    The complexity of large-scale convex programming under a linear optimization oracle

    Guanghui Lan. The complexity of large-scale convex programming under a linear optimization oracle. arXiv preprint arXiv:1309.5550 , 2013

    2013 arXiv

  43. [52]

    Conditional gradient sliding for convex optimization

    Guanghui Lan and Yi Zhou. Conditional gradient sliding for convex optimization. SIAM Journal on Optimization, 26(2):1379–1409, 2016. 12

    2016

  44. [53]

    Constrained minimization methods

    Evgeny S Levitin and Boris T Polyak. Constrained minimization methods. USSR Computational mathematics and mathematical physics , 6(5):1–50, 1966

    1966

  45. [54]

    Projection free online learning over smooth sets

    Kfir Levy and Andreas Krause. Projection free online learning over smooth sets. In The 22nd interna- tional conference on artificial intelligence and statistics , pages 1458–1466. PMLR, 2019

    2019

  46. [55]

    Sublinear quantum algorithms for training linear and kernel-based classifiers

    Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu. Sublinear quantum algorithms for training linear and kernel-based classifiers. In International Conference on Machine Learning , pages 3815–3824, Palo Alto, CA, 2019. AAAI

    2019

  47. [56]

    Quantum speedups of optimizing approximately convex functions with applications to logarithmic regret stochastic convex bandits

    Tongyang Li and Ruizhe Zhang. Quantum speedups of optimizing approximately convex functions with applications to logarithmic regret stochastic convex bandits. Advances in Neural Information Processing Systems, 35:3152–3164, 2022

    2022

  48. [57]

    A quantum online portfolio optimization algorithm

    Debbie Lim and Patrick Rebentrost. A quantum online portfolio optimization algorithm. arXiv preprint arXiv:2208.14749, 2022

    2022 arXiv

  49. [58]

    Quantum algorithms for supervised and unsu- pervised machine learning

    Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum algorithms for supervised and unsu- pervised machine learning. arXiv preprint arXiv:1307.0411 , 2013

    2013 arXiv

  50. [59]

    Quantum principal component analysis

    Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10(9):631–633, 2014

    2014

  51. [60]

    Critically damped quantum search

    Ari Mizel. Critically damped quantum search. Physical review letters , 102(15):150501, 2009

    2009

  52. [61]

    PhD thesis, INRIA Grenoble, 2014

    Federico Pierucci, Zaid Harchaoui, and J´ erˆ ome Malick.A smoothing approach for composite conditional gradient with nonsmooth loss . PhD thesis, INRIA Grenoble, 2014

    2014

  53. [62]

    The frank-wolfe algorithm: a short introduction

    Sebastian Pokutta. The frank-wolfe algorithm: a short introduction. Jahresbericht der Deutschen Mathematiker-Vereinigung, pages 1–33, 2023

    2023

  54. [63]

    Quantum support vector machine for big data classification

    Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical review letters , 113(13):130503, 2014

    2014

  55. [64]

    Quantum gradient descent and newton’s method for constrained polynomial optimization.New Journal of Physics, 21(7):073023, 2019

    Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione, and Seth Lloyd. Quantum gradient descent and newton’s method for constrained polynomial optimization.New Journal of Physics, 21(7):073023, 2019

    2019

  56. [65]

    Quantum search with prior knowledge

    Przemys law Sadowski. Quantum search with prior knowledge. arXiv preprint arXiv:1506.04030 , 2015

    2015 arXiv

  57. [66]

    Quantum speedups for stochastic optimization

    Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization. Advances in Neural Information Processing Systems, 36:35300–35330, 2023

    2023

  58. [67]

    Improvements in quantum SDP-solving with applications

    Joran van Apeldoorn and Andr´ as Gily´ en. Improvements in quantum SDP-solving with applications. In 46th International Colloquium on Automata, Languages, and Programming , page 99, Wadern, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik

    2019

  59. [68]

    Quantum algorithms for zero-sum games

    Joran van Apeldoorn and Andr´ as Gily´ en. Quantum algorithms for zero-sum games. arXiv preprint arXiv:1904.03180, 2019

    1904 arXiv

  60. [69]

    Quantum SDP-solvers: Better upper and lower bounds

    Joran van Apeldoorn, Andr´ as Gily´ en, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 403–414, Piscataway, NJ, 2017. IEEE

    2017

  61. [70]

    Convex optimization using quantum oracles

    Joran van Apeldoorn, Andr´ as Gily´ en, Sander Gribling, and Ronald de Wolf. Convex optimization using quantum oracles. Quantum, 4:220, 2020

    2020

  62. [71]

    Quantum multi-armed bandits and stochastic linear bandits enjoy logarithmic regrets

    Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang, and Xiaoming Sun. Quantum multi-armed bandits and stochastic linear bandits enjoy logarithmic regrets. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 37, pages 10087–10094, 2023. 13

    2023

  63. [72]

    Quantum exploration algorithms for multi-armed bandits

    Daochen Wang, Xuchen You, Tongyang Li, and Andrew M Childs. Quantum exploration algorithms for multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 35, pages 10102–10110, 2021

    2021

  64. [73]

    Convergence theory in nonlinear programming

    Philip Wolfe. Convergence theory in nonlinear programming. Integer and nonlinear programming, pages 1–36, 1970

    1970

  65. [74]

    Quantum linear system algorithm for dense matrices

    Leonard Wossnig, Zhikuan Zhao, and Anupam Prakash. Quantum linear system algorithm for dense matrices. Physical review letters , 120(5):050502, 2018

    2018

  66. [75]

    Efficient projection-free online meth- ods with stochastic recursive gradient

    Jiahao Xie, Zebang Shen, Chao Zhang, Boyu Wang, and Hui Qian. Efficient projection-free online meth- ods with stochastic recursive gradient. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 6446–6453, 2020

    2020

  67. [76]

    Fixed-point quantum search with an optimal number of queries

    Theodore J Yoder, Guang Hao Low, and Isaac L Chuang. Fixed-point quantum search with an optimal number of queries. Physical review letters , 113(21):210501, 2014

    2014

  68. [77]

    Conditional gradient methods via stochastic path- integrated differential estimator

    Alp Yurtsever, Suvrit Sra, and Volkan Cevher. Conditional gradient methods via stochastic path- integrated differential estimator. In International Conference on Machine Learning , pages 7282–7291. PMLR, 2019

    2019

  69. [78]

    Quantum lower bounds for finding stationary points of nonconvex functions

    Chenyi Zhang and Tongyang Li. Quantum lower bounds for finding stationary points of nonconvex functions. In International Conference on Machine Learning , pages 41268–41299. PMLR, 2023

    2023

  70. [79]

    One sample stochas- tic frank-wolfe

    Mingrui Zhang, Zebang Shen, Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. One sample stochas- tic frank-wolfe. In International Conference on Artificial Intelligence and Statistics , pages 4012–4023. PMLR, 2020

    2020

  71. [80]

    Accelerated training for matrix-norm regulariza- tion: A boosting approach

    Xinhua Zhang, Dale Schuurmans, and Yao-liang Yu. Accelerated training for matrix-norm regulariza- tion: A boosting approach. Advances in Neural Information Processing Systems , 25, 2012

    2012

  72. [81]

    Quantum algorithms and lower bounds for finite-sum optimization

    Yexin Zhang, Chenyi Zhang, Cong Fang, Liwei Wang, and Tongyang Li. Quantum algorithms and lower bounds for finite-sum optimization. In Proceedings of the 41st International Conference on Machine Learning, pages 60244–60270. PMLR, 2024. 14 Appendix A Extension and Discussion A....

    2024

  73. [82]

    Prepare the state Pd i |i⟩ |x⟩ |gi(x)⟩ |0⟩

  74. [83]

    Set the third register to |1⟩ conditioned on the value of the second register smaller than gj(x)

  75. [84]

    Apply the quantum exponential Grover search algorithm for the third register being 1

  76. [85]

    By Theorem 1 of [24], the algorithm finds the minimum gi(x) with probability 1 /2, O( √ d) applications of Ug, U † g and O( √ d) elementary gates

    Measure the first register in computation basis, if the measurement result is smaller than gj(x), set j to be the measurement result. By Theorem 1 of [24], the algorithm finds the minimum gi(x) with probability 1 /2, O( √ d) applications of Ug, U † g and O( √ d) elementary gat...

    2019

Pith tools

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