acceptodds
Under review as a conference paper at ICLR 2027

Quantum Lasso: Closing the Gap in High Dimensions via Adaptive Frank–Wolfe

Abstract

We study Lasso, a linear regression problem that minimizes the mean squared loss subject to the coefficient vector having -norm at most one. We use quantum queries to data entries on index superpositions. chen2023 (CdW) use approximate quantum minimum finding with additive error for Frank–Wolfe direction selection. Each update costs queries, leaving a gap to the high-dimensional lower bound. We propose a new algorithm, Adaptive Quantum Frank–Wolfe (AQFW), which returns an explicit feasible -sparse -optimal vector with constant confidence using queries. For and , this improves CdW's bound by and matches their lower bound up to logarithms. AQFW replaces -precision minimum finding with randomized threshold searches that test estimated loss-decrease slopes along signed coordinate directions (atoms). Smaller thresholds require more precise, costlier estimates, so we reduce Grover iteration caps, where each attempt costs queries, cheaper than CdW's . Accepted step sizes are proportional to the threshold, ensuring sufficient loss decrease under accurate checks. A simplex lift represents by a distribution over atoms. Mixing with the uniform distribution reuses information and warm-starts searches while keeping every atom accessible. We propose a multiplicative potential that combines the objective suboptimality gap with an exponentiated Kullback–Leibler (KL) divergence from a fixed optimal atom distribution to the current one. Our analysis shows that searches suffice to reach -accuracy, matching the baseline's searches up to logarithms. Finite-precision state preparation preserves the bound.

Primary area:
optimization
Keywords:
Quantum Algorithm, Lasso, Complexity

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_XzhYOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the quantum query complexity of Lasso regression under coherent access to individual data entries. The authors propose Adaptive Quantum Frank–Wolfe (AQFW), which outputs an explicit, feasible, O(1/ϵ)O(1/\epsilon)-sparse ϵ\epsilon-optimal solution using O~(d,ϵ−3/2+ϵ−2)\widetilde O(\sqrt{d},\epsilon^{-3/2}+\epsilon^{-2}) queries at constant confidence. This improves upon Chen and de Wolf’s O~(d,ϵ−2)\widetilde O(\sqrt{d},\epsilon^{-2}) upper bound and matches their lower bound up to logarithmic factors in the high-dimensional regime with sufficiently many samples. The algorithm replaces approximate minimum finding with randomized threshold searches whose estimation precision and Grover iteration budgets vary with the threshold. It also mixes the current iterate’s atom distribution with a uniform distribution to reuse information across searches. The convergence analysis employs a multiplicative potential combining objective suboptimality and KL divergence, accounting for unsuccessful searches. The paper additionally analyzes finite-precision state preparation, adaptive estimation failures, and sparse-output postprocessing.

Critical strengths
  1. The paper improves the accuracy dependence of quantum Lasso query complexity and matches the existing lower bound up to logarithmic factors in the specified high-dimensional regime. This resolves a concrete gap left by Chen and de Wolf’s work.
  2. Randomized threshold searches, threshold-dependent Grover budgets, and reuse of the current distribution work together to reduce search costs. The multiplicative potential combining objective suboptimality and KL divergence provides a technically interesting way to establish convergence despite unsuccessful searches.
  3. The paper addresses finite-precision state preparation, coherent estimation errors, adaptive failure probabilities, and sparse-output verification. The algorithm returns an explicitly stored, feasible sparse vector, making the output guarantee concrete and comparable with prior Lasso algorithms.
Critical weaknesses
  1. The search budget in Theorem 5.3 contains a factor of 2452^{45}, and Algorithm 1 directly uses this budget. Although this does not invalidate the asymptotic improvement, the prescribed parameters provide little practical guidance. A tighter analysis or numerical illustration would help establish whether substantially smaller budgets suffice.
  2. The algorithm builds on standard amplitude estimation, randomized amplitude amplification, and approximate Frank–Wolfe ideas. The main technical contribution appears to be their coordinated design and the multiplicative KL potential. A more explicit comparison with lazy and randomized Frank–Wolfe methods would clarify which ingredients are essential to the improved accuracy dependence.
  3. Input loading and oracle construction are excluded, while the efficient auxiliary implementation assumes coherent access to working memory. Without native working QRAM, the stated nonquery gate bound incurs additional overhead. Consequently, the practical computational implications remain unclear.
  4. The matching lower bound applies only in the specified high-dimensional, sufficiently large-sample regime. Optimality in lower dimensions remains unresolved, and extensions beyond squared loss are not established.
Questions for authors
  1. The search budget in Theorem 5.3 contains a factor of 2452^{45}. Which conservative estimates contribute most to this constant? Could a tighter analysis or a verifiable early stopping rule substantially reduce the required number of searches?
  2. Is reusing the current distribution essential to the improved accuracy dependence? If searches always started from the uniform distribution, would the current analysis still apply? If not, which step would fail, and could the same query complexity be achieved through a different analysis?
9 comments

Part 1 of 3

Thank you for your careful reading and constructive comments. We appreciate your suggestions on the search budget, related methods, computational costs, and scope of the results. We respond to each point below.

All manuscript references are to the revised version.

1. Weakness 1, large constant

The search budget in Theorem 5.3 contains a factor of 2452^{45}, and Algorithm 1 directly uses this budget. Although this does not invalidate the asymptotic improvement, the prescribed parameters provide little practical guidance. A tighter analysis or numerical illustration would help establish whether substantially smaller budgets suffice.

Response. We have reduced the coefficient in the prescribed search budget from 2452^{45} to 8192=2138192=2^{13} through revised parameter choices and a sharper convergence analysis, without adding logarithmic factors. For dd features, dyadic target error ϵ\epsilon, and failure probability δ\delta, the revised budget is T=⌈8192Lϵ[log⁡8ϵδ+11024log⁡(2d)]⌉,L=1+log⁡2(16/ϵ).T=\left\lceil\frac{8192L}{\epsilon} \left[\log\frac{8}{\epsilon\delta}+\frac{1}{1024}\log(2d)\right]\right\rceil, \qquad L=1+\log_2(16/\epsilon). Here LL is the number of threshold values. Algorithm 1 uses this budget directly and counts all FindAtom calls, including empty returns. This remains a conservative worst-case guarantee. The revised step size, acceptance threshold, Grover cap, and potential analysis are explained in our response to Question 1. Theorem 5.3 states the resulting search budget.

2. Weakness 2

The algorithm builds on standard amplitude estimation, randomized amplitude amplification, and approximate Frank–Wolfe ideas. The main technical contribution appears to be their coordinated design and the multiplicative KL potential. A more explicit comparison with lazy and randomized Frank–Wolfe methods would clarify which ingredients are essential to the improved accuracy dependence.

Response. The methods differ in their search guarantees. Lazy FW reuses cached directions and uses a weak separation test that either supplies a suitable direction or bounds the remaining improvement. Sampled-subset FW optimizes over a randomly selected subset of atoms. AQFW permits an empty return even when qualifying directions remain. Such a return provides no bound on the remaining improvement.

Allowing empty returns reduces the work per search, but a bound on accepted updates alone cannot control the number of unsuccessful attempts. For dd features and target loss error ϵ\epsilon, threshold-dependent estimation precision and Grover caps give a cost of O~(d/ϵ+ϵ−1)\widetilde O(\sqrt{d/\epsilon}+\epsilon^{-1}) queries per attempt at fixed confidence. Distribution reuse and the loss/KL potential analysis bound all attempts, including empty returns, by O~(1/ϵ)\widetilde O(1/\epsilon). These two bounds give the improved query complexity.

Section 2 of the revised manuscript gives this comparison under Weaker linear-minimization oracles. Section 4.1 explains the estimation precision, search caps, and distribution reuse.

Part 2 of 3

3. Weakness 3

Input loading and oracle construction are excluded, while the efficient auxiliary implementation assumes coherent access to working memory. Without native working QRAM, the stated nonquery gate bound incurs additional overhead. Consequently, the practical computational implications remain unclear.

Response. Our input-query bound is unchanged when native working QRAM is replaced by reversible circuits for working-memory reads. Efficient working QRAM gives the sharper auxiliary gate bound. Appendix E reports both implementations, which continue to use the supplied coherent input oracles.

Write dd for the number of features and ϵ\epsilon for the target loss error. At fixed confidence and d≳1/ϵd\gtrsim1/\epsilon, the auxiliary gate upper bounds are as follows, with logarithmic and word-length factors suppressed.

Working-memory implementationChen–de WolfAQFW
Native working QRAMO~(d,ϵ−2)\widetilde O(\sqrt d\\,\epsilon^{-2})O~(d,ϵ−3/2)\widetilde O(\sqrt d\\,\epsilon^{-3/2})
Reversible circuitsO~(d,ϵ−3)\widetilde O(\sqrt d\\,\epsilon^{-3})O~(d,ϵ−5/2)\widetilde O(\sqrt d\\,\epsilon^{-5/2})

The comparison uses Appendix E and Theorems 2.13 and 3.7 of Chen and de Wolf's full version. It compares upper bounds for these implementations. Optimal gate complexity and a practical runtime advantage are not established.

For d≫1/ϵd\gg1/\epsilon, our input-query upper bound improves on the O~(dϵ−2)\widetilde O(d\epsilon^{-2}) classical coordinate-query baseline of Hazan and Koren (2012), applied to the empirical problem, by a factor of order d/ϵ\sqrt{d/\epsilon}. Chen and de Wolf already established a quantum query advantage. AQFW improves its accuracy dependence.

For a fixed dataset, the one-time cost of loading the data and constructing the input oracles is excluded. Each subsequent oracle call or inverse counts as one input query. A practical crossover depends on their physical implementation, the working-memory hardware, and the overhead of the chosen quantum error-correcting code.

4. Weakness 4

The matching lower bound applies only in the specified high-dimensional, sufficiently large-sample regime. Optimality in lower dimensions remains unresolved, and extensions beyond squared loss are not established.

Response. Our original matching result concerns the high-dimensional regime of Corollary 4.2. Appendix H now gives a separate analysis for small dϵd\epsilon. Here dd is the number of features, ϵ\epsilon is the target loss error, and NN is the number of examples. At fixed confidence, under d≥4,0<dϵ≤c,N≥C(d/ϵ)log⁡(2d),d\ge4,\qquad 0 < d\epsilon\le c,\qquad N\ge C(d/\epsilon)\log(2d), for suitable universal constants c,C>0c,C > 0, Table 5 in Appendix H of the revised manuscript gives the following entry-query bounds.

ModelLower boundUpper bound
Classical randomizedΩ(d2/ϵ)\Omega(d^2/\epsilon)O(d2/ϵ)O(d^2/\epsilon)
QuantumΩ(d3/2/ϵ)\Omega(d^{3/2}/\sqrt\epsilon)O~(min⁡d2/ϵ,ϵ−2)\widetilde O(\min\\{d^2/\epsilon,\epsilon^{-2}\\})

The sample-size condition suffices for the lower-bound construction. The upper bounds also hold for smaller NN. The classical bounds match, and the quantum bounds remain separated. Optimal quantum complexity throughout this low-dimensional regime remains open.

When d2ϵd^2\epsilon dominates the suppressed logarithmic factors, the quantum upper bound is below the classical lower bound. Ignoring those factors, this includes the range ϵ−1/2≪d≪ϵ−1\epsilon^{-1/2}\ll d\ll\epsilon^{-1}. Thus quantum query advantage also occurs below the dimension threshold of the main matching result.

We also extend AQFW to differentiable convex objectives over finite convex hulls under the normalization, curvature, and coherent sampling assumptions of Corollary I.1. That corollary gives the general query upper bound. Corollary I.2 and Theorem I.3 give matching entry-query bounds for bounded quartic loss in the stated regime. Section 7 introduces this extension, and Appendix I gives the proofs.

Beyond quartic loss, our framework achieves Θ~(dϵ−3/2)\widetilde{\Theta}(\sqrt{d}\epsilon^{-3/2}) quantum entry-query complexity for logistic, exponential, log-cosh, and pseudo-Huber loss (scale 22), with explicit feasible O(1/ϵ)O(1/\epsilon)-sparse classical outputs. These bounds are optimal up to logarithmic factors under the same access assumptions and high-dimensional, large-sample conditions.

These extensions motivate investigating AQFW for maximal-loss minimization with convex Lipschitz losses, as studied by Wang, Zhang, and Li (ICLR 2024), through regularized dual formulations over simplex weights. Establishing efficient coherent sampling oracles and translating the resulting dual guarantees into query and accuracy guarantees for the original problem remain directions for future work.

Part 3 of 3

5. Question 1: Which conservative estimates drive the large constant, and can a tighter analysis or stopping rule reduce the searches?

The search budget in Theorem 5.3 contains a factor of 2452^{45}. Which conservative estimates contribute most to this constant? Could a tighter analysis or a verifiable early stopping rule substantially reduce the required number of searches?

Response. Two changes reduce the search-budget coefficient from 2452^{45} to 2132^{13}, without additional logarithmic factors.

  1. Tighter constants in the convergence analysis. We sharpen the potential-decrease estimates and set ρ=1/1024\rho=1/1024, with step size γ=r/8\gamma=r/8 for search threshold rr.

  2. Sharper FindAtom guarantees. For current atom weights qq, let va(q)v_a(q) be the directional rate of loss decrease toward atom aa. Accepted atoms satisfy va(q)≥7r/8v_a(q)\ge7r/8 in the accurate process. The new interface gives separate lower bounds on the probability of returning any atom and of returning each atom with va(q)≥rv_a(q)\ge r. Write RR for the Grover iteration cap and pp for the probability that the preparation and test circuit marks an atom. In the contraction proof, the overall return bound controls loss decrease when R2p≥1R^2p\ge1. When R2p<1R^2p < 1, the bound for each qualifying atom and distribution reuse control the KL contribution. We adjust the cap to satisfy these guarantees at the reduced search cost.

An early-stop test would need an upper bound on the Frank–Wolfe gap g(q)=max⁡ava(q)g(q)=\max_a v_a(q) that is valid with high probability and below ϵ/2\epsilon/2. An empty FindAtom return does not provide this bound. Computing it also requires input queries. The revised theorem uses a fixed search budget and does not claim that an additional stopping test improves the total query bound.

Definition 4.3 and Theorem 5.3 state the revised interface and search budget. Appendices B.2 and C give the proofs.

6. Question 2: Is distribution reuse essential, and what happens with uniform starts?

Is reusing the current distribution essential to the improved accuracy dependence? If searches always started from the uniform distribution, would the current analysis still apply? If not, which step would fail, and could the same query complexity be achieved through a different analysis?

Response. Distribution reuse is needed by our current contraction proof. Let n=2dn=2d be the number of signed coordinate atoms, qq the current positive weight vector, and γ\gamma the update step size. For an atom aa, define \bar\ell_a=\min\left\\{\log\left(1+\frac{\gamma}{(1-\gamma)q_a}\right),1\right\\}. The return-probability bound contributes the starting weight σa\sigma_a, and the KL calculation contributes ℓˉa\bar\ell_a. Their product satisfies σaℓˉa≥c2,σa=qa+1/n2,c=min⁡γ,1/n.\sigma_a\bar\ell_a\ge\frac c2, \qquad \sigma_a=\frac{q_a+1/n}{2}, \qquad c=\min\\{\gamma,1/n\\}. This inequality connects the probability of returning an atom to expected KL progress.

Uniform starting weights ua=1/nu_a=1/n need not satisfy the same bound. For n≥8n\ge8, take qa=1/2q_a=1/2, qb=1/[2(n−1)]q_b=1/[2(n-1)] for b≠ab\ne a, and γ=1/n\gamma=1/n. Then uaℓˉa≤1nlog⁡(1+2n−1)≤2n(n−1)=O(n−2),c2=12n.u_a\bar\ell_a \le\frac1n\log\left(1+\frac2{n-1}\right) \le\frac{2}{n(n-1)} =O(n^{-2}), \qquad \frac c2=\frac1{2n}. Thus a uniform start can lose a factor proportional to dimension in this intermediate bound. With the same Grover cap, our proof no longer gives O~(1/ϵ)\widetilde O(1/\epsilon) search attempts at fixed confidence. The example shows the failure of this proof step. Whether other uniform-start algorithms or analyses attain the same query complexity remains open. Appendix B.2 gives the example and its role in the contraction proof.

Reviewer_gW1nOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

In this work, the authors propose "Adaptive Quantum Frank-Wolfe" for solving Lasso regression problems.

Their key contribution is an adaptive version of the search direction selection from Chen and de Wolf (ICALP, 2023) to save a 1/ϵ\sqrt{1/\epsilon} factor in the overall running time expression. They accomplish this by devising an implementation of the search direction selection step that can handle coarse tolerances to avoid paying O(ϵ−1)O(\epsilon^{-1}) using quantum minimum finding in each iteration. I find the paper does not meet the bar for ICLR; the novelty is limited, and the algorithm is uninteresting from both theoretical and practical perspectives.

Critical strengths

The paper appears technically correct, and the main result gives a running time for quantum Frank-Wolfe applied to Lasso that matches known lower bounds in some parameter regimes. I think that the technical components of the paper were carefully written.

Critical weaknesses

My primary concern is significance, and I do not believe the main result meets the bar for ICLR.

Most of the ingredients for the algorithm are already found in the literature, it basically boils down to Chen & de Wolf with a capped implementation of the quantum minimum finding steps (the authors call this procedure FindAtom) that can handle coarser accuracy and adapting the potential to maintain the O(ϵ−1)O(\epsilon^{-1}) iteration complexity.

The speedup over the previous best quantum algorithm Chen & de Wolf is ϵ−1/2\epsilon^{-1/2}. However, both algorithms are sublinear, and therefore are interesting when inverse precision scales at most polylogarithmically in dimension. For this parameter regime, both this work and Chen&de Wolf scale as O~(d)\widetilde{O} (\sqrt{d}).

Further, the overall speedup over classical FW algorithms is sub-quadratic (and also cannot be improved in a meaningful way). Thus, unlike classical Frank-Wolfe algorithms, the quantum variant is unlikely to be of any practical interest [1]. I understand that this is a theoretical work, but I think that this is an important distinction to make.

I also found the expository component of the paper to be poorly written in some places:

  • The literature review provided is uneven; one of the subheads is titled "Broader quantum optimization" and yet a very narrow picture is given, with very limited information about the cited works provided. For instance the authors cite Bouland et al (2023) and Gao et al (2023) but omit "Quantum algorithms for zero-sum games" by van Apeldoorn and Gilyén (2019), which these two works build off.
  • In many places, results or mathematical ideas are formalized with little to no explanation. The preliminaries goes from defining the query model and "atoms" to "The lifted problem" (without telling us why this is needed).

The later sections are slightly more well written, but if the reader is not an expert in quantum algorithms or convex optimization, they will likely find it much harder to follow.

Overall, I do not believe this work provides a meaningful advance in quantum algorithms or machine learning. It gives a modest improvement in precision over a specific quantum algorithm for a specific problem. I concede that the authors have indeed addressed an open question of Chen & de Wolf through their results here, there is simply no meaningfully new techniques for quantum algorithms or consequences for ML to merit acceptance at a top tier ML venue like ICLR.

[1] "Focus beyond quadratic speedups for error-corrected quantum advantage" Babbush et al, (2021) PRX Quantum

Questions for authors

Do you see any way to leverage their techniques beyond the FW method for Lasso?

2 comments

Part 1 of 2

Thank you for the detailed review and for recognizing the care in the technical analysis. We appreciate the opportunity to clarify the contribution, accuracy improvement, practical scope, presentation, and possible extensions.

All manuscript references are to the revised version.

1. Novelty and significance

Most of the ingredients for the algorithm are already found in the literature, it basically boils down to Chen & de Wolf with a capped implementation of the quantum minimum finding steps (the authors call this procedure FindAtom) that can handle coarser accuracy and adapting the potential to maintain the O(ϵ−1)O(\epsilon^{-1}) iteration complexity.

Overall, I do not believe this work provides a meaningful advance in quantum algorithms or machine learning. It gives a modest improvement in precision over a specific quantum algorithm for a specific problem. I concede that the authors have indeed addressed an open question of Chen & de Wolf through their results here, there is simply no meaningfully new techniques for quantum algorithms or consequences for ML to merit acceptance at a top tier ML venue like ICLR.

Response. Our contribution is twofold: achieving optimal quantum query complexity for Lasso up to logarithmic factors in the stated high-dimensional, large-sample regime, and establishing AQFW as an optimization framework applicable beyond Lasso under explicit assumptions (see our response to Question 1 and Appendix I).

We agree that the underlying quantum primitives are standard. However, capping a search does not by itself control total query cost: empty returns can occur while useful directions remain and provide no optimality certificate. AQFW's distribution reuse and loss/KL analysis bound all attempts, by O~(1/ϵ)\widetilde{O}(1/\epsilon).

Accuracy dependence is a standard measure of optimization complexity. At fixed confidence in the high-dimensional regime, AQFW improves the leading accuracy dependence from ϵ−2\epsilon^{-2} to ϵ−3/2\epsilon^{-3/2}. Under the conditions of Corollary 4.2, this matches a lower bound for every quantum algorithm with the same access and output requirements, determining the worst-case quantum query complexity of Lasso up to logarithms. Corollary I.1 also extends AQFW to differentiable convex objectives over finite convex hulls under its stated assumptions, and the bounded quartic-loss example gives matching entry-query bounds beyond squared loss.

2. Accuracy dependence

The speedup over the previous best quantum algorithm Chen & de Wolf is ϵ−1/2\epsilon^{-1/2}. However, both algorithms are sublinear, and therefore are interesting when inverse precision scales at most polylogarithmically in dimension. For this parameter regime, both this work and Chen&de Wolf scale as O~(d)\widetilde{O}(\sqrt{d}).

Response. We agree that both bounds are O~(d)\widetilde{O}(\sqrt{d}) when inverse accuracy is only polylogarithmic in dd. Our improvement concerns the dependence on ϵ\epsilon instead of dd in the claimed regime, especially when d=O(2poly(1/ϵ))d=O(2^{\mathrm{poly}(1/\epsilon)}). The query bounds can also be sublinear when inverse accuracy grows polynomially with dimension. For example, take ϵ=d−1/6\epsilon=d^{-1/6} along the dyadic sequence d=26kd=2^{6k}, ϵ=2−k\epsilon=2^{-k}. At constant confidence, the Chen–de Wolf upper bound becomes O~(d5/6)\widetilde{O}(d^{5/6}), and AQFW's becomes O~(d3/4+d1/3)=O~(d3/4)\widetilde{O}(d^{3/4}+d^{1/3})=\widetilde{O}(d^{3/4}). Both are sublinear in dd, and their displayed upper bounds differ by a factor of d1/12d^{1/12}, up to logarithms. This comparison counts input queries to the supplied coherent oracles.

3. Practical relevance

Further, the overall speedup over classical FW algorithms is sub-quadratic (and also cannot be improved in a meaningful way). Thus, unlike classical Frank-Wolfe algorithms, the quantum variant is unlikely to be of any practical interest [1].

Response. We distinguish limits on the achievable speedup from the significance of attaining those limits. Under the conditions of Corollary 4.2, AQFW improves the leading query bound from O~(d,ϵ−2)\widetilde{O}(\sqrt{d}\\,\epsilon^{-2}) to O~(d,ϵ−3/2)\widetilde{O}(\sqrt{d}\\,\epsilon^{-3/2}), matching the quantum lower bound up to logarithms. A lower bound limiting further asymptotic query improvements in this regime does not make closing the remaining precision gap theoretically insignificant.

Practical performance is a separate question. Babbush et al. identify serious obstacles to small polynomial speedups on early fault-tolerant devices, under explicit assumptions about error correction, primitive costs, and classical parallelism. Our paper does not claim a demonstrated practical advantage. However, Babbush et al. doesn't claim it's impossible to get practical advantage for quadratic speedup.

Part 2 of 2

4. Related work and presentation

I also found the expository component of the paper to be poorly written in some places:

  • The literature review provided is uneven; one of the subheads is titled “Broader quantum optimization” and yet a very narrow picture is given, with very limited information about the cited works provided. For instance the authors cite Bouland et al (2023) and Gao et al (2023) but omit “Quantum algorithms for zero-sum games” by van Apeldoorn and Gilyén (2019), which these two works build off.

  • In many places, results or mathematical ideas are formalized with little to no explanation. The preliminaries goes from defining the query model and “atoms” to “The lifted problem” (without telling us why this is needed).

The later sections are slightly more well written, but if the reader is not an expert in quantum algorithms or convex optimization, they will likely find it much harder to follow.

Response. We added van Apeldoorn and Gilyén (2019). Section 2 and Appendix G, including Tables 2–4, now distinguish prior work by oracle access, assumptions, and output guarantees.

Section 3 now motivates the simplex lift. Its probability weights can be coherently prepared as a quantum superposition over signed coordinate atoms, enabling amplitude estimation of directional derivatives and loss values.

5. Question 1. Generalization

Do you see any way to leverage their techniques beyond the FW method for Lasso?

Response. We extend the AQFW algorithm, including its capped threshold searches, distribution reuse, and convergence analysis, to differentiable convex objectives over finite convex hulls. Given vectors v1,…,vd\mathbf v_1,\ldots,\mathbf v_d and an objective FF, write min⁡q∈Δdf(q),f(q)=F(x(q)),x(q)=∑a=1dqava.\min_{q\in\Delta_d} f(q),\qquad f(q)=F(x(q)),\qquad x(q)=\sum_{a=1}^d q_a\mathbf v_a. Here dd counts the given vectors, and Δd\Delta_d consists of nonnegative weights that sum to one. These probability weights support coherent state preparation, distribution reuse, and the same loss/KL analysis.

For a fixed, classically specified qq, the oracles coherently prepare bounded scalar samples whose means approximate [∇f(q)]a[\nabla f(q)]_a and f(q)−f(u)f(q)-f(u), where u=(1/d,…,1/d)u=(1/d,\ldots,1/d). The finite-precision bias is bounded as specified in Corollary I.1. The gradient index aa may be in superposition. Each forward, inverse, or controlled sampler call counts as one query. Estimating a mean to the required accuracy takes repeated calls, whose cost is included in the bound.

Under Corollary I.1's normalization, curvature, accuracy, and oracle assumptions, AQFW returns an explicit feasible convex combination of O(1/ϵ)O(1/\epsilon) given vectors that is ϵ\epsilon-optimal with probability at least 1−δ1-\delta. Here ϵ\epsilon is the target loss error and δ\delta is the failure probability. Its query bound on every branch is O~!(d,ϵ−3/2log⁡(1/δ)+ϵ−2log⁡2(1/δ)).\widetilde O\\!\left( \sqrt d\\,\epsilon^{-3/2}\log(1/\delta) +\epsilon^{-2}\log^2(1/\delta)\right). This includes mean estimation, construction of sparse candidates, and selection of the candidate with the smallest estimated loss. Only dimension and accuracy logarithms are suppressed.

Consider the bounded quartic loss f(q)=124N∑i=1N((Zq)i−yi)4,q∈Δd,f(q)=\frac{1}{24N}\sum_{i=1}^{N}\bigl((Zq)_i-y_i\bigr)^4,\qquad q\in\Delta_d, where Z∈[−1,1]N×dZ\in[-1,1]^{N\times d}, y∈[−1,1]Ny\in[-1,1]^N, and NN is the number of examples. Products of independent residual samples implement the required samplers with a constant number of data-entry queries per invocation. Corollary I.2 therefore gives an entry-query upper bound, and Theorem I.3 proves a matching lower bound in the stated high-dimensional, large-sample regime. Optimality for other objectives requires separate lower bounds. Section 7 describes the extension, and Appendix I gives the assumptions, constructions, and proofs.

Beyond quartic loss, our framework achieves Θ~(dϵ−3/2)\widetilde{\Theta}(\sqrt{d}\epsilon^{-3/2}) quantum entry-query complexity for logistic, exponential, log-cosh, and pseudo-Huber loss (scale 22), with explicit feasible O(1/ϵ)O(1/\epsilon)-sparse classical outputs. These bounds are optimal up to logarithmic factors under the same access assumptions and high-dimensional, large-sample conditions.

These extensions motivate investigating AQFW for maximal-loss minimization with convex Lipschitz losses, as studied by Wang, Zhang, and Li (ICLR 2024), through regularized dual formulations over simplex weights. Establishing efficient coherent sampling oracles and translating the resulting dual guarantees into query and accuracy guarantees for the original problem remain directions for future work.

Reviewer_dX2iOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes Adaptive Quantum Frank–Wolfe for Lasso in the coherent entry-query model, achieving query complexity O~(d ε−3/2+ε−2)\widetilde O(\sqrt d\,\varepsilon^{-3/2}+\varepsilon^{-2}). This improves the precision dependence of prior algorithms and matches an existing quantum lower bound under specified dimension and sample-size conditions. The algorithm outputs an explicit sparse classical solution.

Critical strengths
  1. The paper closes a concrete complexity gap in quantum Lasso optimization.
  2. Adaptive threshold search and the potential-function analysis provide a nontrivial way to balance estimation costs against optimization progress.
  3. The explicit classical output and treatment of finite precision strengthen the result.
Critical weaknesses
  1. The main text could better explain why straightforward adaptive-precision Frank–Wolfe methods cannot achieve the same bound, and which new ingredients overcome this obstacle.
  2. The conditions required for optimality deserve a clearer presentation, particularly the regimes where the additive ε−2\varepsilon^{-2} term dominates.
  3. The distinction between query complexity and overall computational costs, including oracle implementation and working-memory assumptions, should be more visible.
Questions for authors
  1. Where does a direct adaptive-precision approach fail, making the proposed search interface and potential function necessary?
  2. Could the authors summarize the precise regimes of optimality and the auxiliary resource costs with and without efficient working QRAM?
  3. Which parts of the analysis extend beyond squared loss and the simplex representation?

I lean toward acceptance. The theoretical improvement is meaningful, and the analysis appears substantive. My reservations concern the explanation of technical novelty and the scope of the complexity claims, rather than an identified correctness issue. The absence of experiments is not itself a weakness.

4 comments

Part 1 of 2

Thank you for your careful review and positive assessment of the theoretical contribution. Your comments helped us clarify the adaptive-precision comparison, the scope of optimality, computational costs, and extensions beyond squared loss.

All manuscript references are to the revised version.

1. Weakness 1 and Question 1. Adaptive precision and the new ingredients

The main text could better explain why straightforward adaptive-precision Frank–Wolfe methods cannot achieve the same bound, and which new ingredients overcome this obstacle.

Where does a direct adaptive-precision approach fail, making the proposed search interface and potential function necessary?

Response. For Lasso with dd features and target additive loss error ϵ\epsilon, a standard adaptive-precision implementation of inexact FW reduces the direction error as the step size decreases. At update tt, it uses γt=2/(t+2)\gamma_t=2/(t+2) and additive error tolerance ζt=Θ((t+2)−1)\zeta_t=\Theta((t+2)^{-1}). Running T=Θ(1/ϵ)T=\Theta(1/\epsilon) updates suffices. Fresh quantum approximate minimum finding costs O~(d/ζt)\widetilde O(\sqrt d/\zeta_t) per update in the same query model. At fixed overall confidence, the total is O~!(d∑t=0T−1ζt−1)=O~(d,T2)=O~(d,ϵ−2).\widetilde O\\!\left(\sqrt d\sum_{t=0}^{T-1}\zeta_t^{-1}\right) =\widetilde O(\sqrt d\\,T^2) =\widetilde O(\sqrt d\\,\epsilon^{-2}). This is the bound for that standard implementation, not a lower bound for all adaptive-precision FW methods.

AQFW uses smaller Grover caps at smaller thresholds, reducing the cost of each attempt to O~(d/ϵ+ϵ−1)\widetilde O(\sqrt{d/\epsilon}+\epsilon^{-1}) queries while allowing empty returns. Distribution reuse and FindAtom's guarantees on the overall return probability and each qualifying atom's return probability give expected loss/KL contraction and bound the total number of attempts by O~(1/ϵ)\widetilde O(1/\epsilon). Combining these bounds gives O~(d,ϵ−3/2+ϵ−2)\widetilde O(\sqrt d\\,\epsilon^{-3/2}+\epsilon^{-2}) total queries at fixed confidence (Section 4.1 and Definition 4.3).

2. Weaknesses 2–3 and Question 2. Optimality regimes and computational costs

The conditions required for optimality deserve a clearer presentation, particularly the regimes where the additive ε−2\varepsilon^{-2} term dominates.

The distinction between query complexity and overall computational costs, including oracle implementation and working-memory assumptions, should be more visible.

Could the authors summarize the precise regimes of optimality and the auxiliary resource costs with and without efficient working QRAM?

Response.

  1. Optimality and the additive term. Here dd is the number of features, ϵ\epsilon the target additive loss error, NN the number of examples, and δ\delta the failure probability. At fixed confidence, the ratio of the two displayed terms in AQFW's query bound is dϵ\sqrt{d\epsilon}. Thus the additive term dominates when dϵ≪1d\epsilon\ll1, ignoring the suppressed logarithmic factors. The upper bound holds for every N≥1N\ge1. For dyadic ϵ=2−k\epsilon=2^{-k}, k≥3k\ge3, and fixed 0<δ<1/200 < \delta < 1/20, Corollary 4.2 gives quantum query complexity Θ~(d,ϵ−3/2)\widetilde\Theta(\sqrt d\\,\epsilon^{-3/2}) when c1/d<ϵ<c2c_1/d < \epsilon < c_2 and N≥2048ϵ−2log⁡(2d/δ)N\ge2048\epsilon^{-2}\log(2d/\delta), where c1,c2>0c_1,c_2 > 0 are universal constants. For non-dyadic targets in (0,1/8](0,1/8], Appendix F.3 rounds down to a neighboring power of two, changing the upper bound by only a constant factor.

  2. Working memory implementations. The table gives bounds at fixed failure probability. Both implementations use the supplied coherent input oracles. Write w=bin+O(log⁡(Nd/ϵ))w=b_{\mathrm{in}}+O(\log(Nd/\epsilon)), where binb_{\mathrm{in}} is the number of bits per input entry.

Query complexityAuxiliary gate upper bound
With efficient working QRAMO~(d,ϵ−3/2+ϵ−2)\widetilde O(\sqrt d\\,\epsilon^{-3/2}+\epsilon^{-2})O~(d,ϵ−3/2+ϵ−2)poly⁡(w)\widetilde O(\sqrt d\\,\epsilon^{-3/2}+\epsilon^{-2})\operatorname{poly}(w)
Without native working QRAMO~(d,ϵ−3/2+ϵ−2)\widetilde O(\sqrt d\\,\epsilon^{-3/2}+\epsilon^{-2})O~(d,ϵ−5/2+ϵ−3)poly⁡(w)\widetilde O(\sqrt d\\,\epsilon^{-5/2}+\epsilon^{-3})\operatorname{poly}(w)

Proposition E.1 gives the implementation with efficient working QRAM, and Corollary E.2 implements working memory reads by reversible circuits. These are auxiliary gate upper bounds for the specified AQFW implementations.

In the model with efficient working QRAM at fixed confidence, classical working memory uses O~(ϵ−1)\widetilde O(\epsilon^{-1}) words and quantum workspace uses O~(1)\widetilde O(1) words. These counts exclude input storage, input-oracle hardware, and QRAM hardware. Classical work is O~(ϵ−1)poly⁡(w)\widetilde O(\epsilon^{-1})\operatorname{poly}(w) for maintenance and processing, and O~(QX,y)poly⁡(w)\widetilde O(Q_{X,y})\operatorname{poly}(w) including generating and issuing quantum circuit instructions, where QX,yQ_{X,y} is the input-query bound in the table.

Part 2 of 2

3. Question 3. Generalization to other losses and feasible sets

Which parts of the analysis extend beyond squared loss and the simplex representation?

Response. The simplex representation gives probability weights that can be coherently prepared as a quantum superposition over vector indices. Together with suitable sampling oracles, this allows amplitude estimation to accelerate gradient and loss estimation. We retain this representation when extending AQFW to differentiable convex objectives over finite convex hulls under the assumptions of Corollary I.1. The original feasible set need not be a simplex: AQFW performs its searches and updates on the corresponding simplex weights.

Under Corollary I.1's assumptions, the loss/KL analysis uses convexity and vertex-direction curvature rather than the exact quadratic form. the KL identities depend only on weight updates. The same FindAtom interface yields expected contraction. Curvature also bounds the expected loss increase from averaging ss independent atom samples by O(1/s)O(1/s), extending the sparse-output guarantee. Corollary I.1 states the query and success guarantees for an explicit feasible ϵ\epsilon-optimal combination of O(1/ϵ)O(1/\epsilon) vectors.

For each new loss, we must verify the objective assumptions and implement bounded coherent samplers with the required bias and query cost. optimality requires a separate lower bound.

Appendix I does so for the normalized quartic loss $ f(q)=\frac{1}{24N}\sum_{i=1}^{N}\bigl((Zq)_i-y_i\bigr)^4, \qquad q\in\Delta_d, $ where Z∈[−1,1]N×dZ\in[-1,1]^{N\times d}, y∈[−1,1]Ny\in[-1,1]^N, NN counts examples, and Δd\Delta_d is the probability simplex. Products of independent residual samples give samplers costing O(1)O(1) entry queries per call. Corollary I.2 gives the upper bound, including mean estimation. Theorem I.3 proves a matching lower bound in the stated high-dimensional, large-sample regime.

Beyond quartic loss, our framework achieves Θ~(dϵ−3/2)\widetilde{\Theta}(\sqrt{d}\epsilon^{-3/2}) quantum entry-query complexity for logistic, exponential, log-cosh, and pseudo-Huber loss (scale 22), with explicit feasible O(1/ϵ)O(1/\epsilon)-sparse classical outputs. These bounds are optimal up to logarithmic factors under the same access assumptions and high-dimensional, large-sample conditions.

These extensions motivate investigating AQFW for maximal-loss minimization with convex Lipschitz losses, as studied by Wang, Zhang, and Li (ICLR 2024), through regularized dual formulations over simplex weights. Establishing efficient coherent sampling oracles and translating the resulting dual guarantees into query and accuracy guarantees for the original problem remain directions for future work.

Thank you for the response. I will maintain my current positive score.

Thank you for your feedback again. We would be very happy to address any further questions or concerns you may have before the end of the rebuttal period.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Overall Response and Summary of Revisions

Dear AC and reviewers,

We thank all three reviewers for their careful reading and constructive feedback. Their comments have helped us sharpen the analysis, improve the presentation, and clarify the scope of our results. We summarize the main revisions below:

  1. Sharper convergence analysis. We reduced the leading coefficient in the prescribed search budget from 2452^{45} to 81928192, without introducing additional logarithmic factors.

  2. Clarified optimality and low-dimensional behavior. We made the dimension and sample-size conditions for matching bounds explicit and added a separate analysis of the low-dimensional regime, including the remaining quantum complexity gap.

  3. Generalization to other objectives and losses. We extended AQFW to differentiable convex objectives over finite convex hulls under explicit oracle assumptions. Beyond quartic loss, we also established matching query bounds for logistic, exponential, log-cosh, and pseudo-Huber loss (scale 22) in the stated regime.

  4. Improved presentation. We revised the presentation based on the reviewers’ feedback, improving the algorithmic explanations, comparisons with prior work, and discussion of computational assumptions and resource costs.

Detailed responses to each reviewer are provided in the corresponding discussion threads.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.