- 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, -sparse -optimal solution using queries at constant confidence. This improves upon Chen and de Wolf’s 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
- 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.
- 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.
- 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
- The search budget in Theorem 5.3 contains a factor of , 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.
- 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.
- 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.
- 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
- The search budget in Theorem 5.3 contains a factor of . 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?
- 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 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 for the number of features and for the target loss error. At fixed confidence and , the auxiliary gate upper bounds are as follows, with logarithmic and word-length factors suppressed.
| Working-memory implementation | Chen–de Wolf | AQFW |
|---|---|---|
| Native working QRAM | ||
| Reversible circuits |
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 , our input-query upper bound improves on the classical coordinate-query baseline of Hazan and Koren (2012), applied to the empirical problem, by a factor of order . 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 . Here is the number of features, is the target loss error, and is the number of examples. At fixed confidence, under for suitable universal constants , Table 5 in Appendix H of the revised manuscript gives the following entry-query bounds.
| Model | Lower bound | Upper bound |
|---|---|---|
| Classical randomized | ||
| Quantum |
The sample-size condition suffices for the lower-bound construction. The upper bounds also hold for smaller . The classical bounds match, and the quantum bounds remain separated. Optimal quantum complexity throughout this low-dimensional regime remains open.
When dominates the suppressed logarithmic factors, the quantum upper bound is below the classical lower bound. Ignoring those factors, this includes the range . 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 quantum entry-query complexity for logistic, exponential, log-cosh, and pseudo-Huber loss (scale ), with explicit feasible -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 . 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 to , without additional logarithmic factors.
-
Tighter constants in the convergence analysis. We sharpen the potential-decrease estimates and set , with step size for search threshold .
-
Sharper FindAtom guarantees. For current atom weights , let be the directional rate of loss decrease toward atom . Accepted atoms satisfy in the accurate process. The new interface gives separate lower bounds on the probability of returning any atom and of returning each atom with . Write for the Grover iteration cap and for the probability that the preparation and test circuit marks an atom. In the contraction proof, the overall return bound controls loss decrease when . When , 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 that is valid with high probability and below . 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 be the number of signed coordinate atoms, the current positive weight vector, and the update step size. For an atom , 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 , and the KL calculation contributes . Their product satisfies This inequality connects the probability of returning an atom to expected KL progress.
Uniform starting weights need not satisfy the same bound. For , take , for , and . Then 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 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.
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
Response. We have reduced the coefficient in the prescribed search budget from 245 to 8192=213 through revised parameter choices and a sharper convergence analysis, without adding logarithmic factors. For d features, dyadic target error ϵ, and failure probability δ, the revised budget is T=⌈ϵ8192L[logϵδ8+10241log(2d)]⌉,L=1+log2(16/ϵ). Here L 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
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 d features and target loss error ϵ, threshold-dependent estimation precision and Grover caps give a cost of O(d/ϵ+ϵ−1) queries per attempt at fixed confidence. Distribution reuse and the loss/KL potential analysis bound all attempts, including empty returns, by O(1/ϵ). 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.