Nearly Optimal Amplitude Estimation at any Depth

• URL: http://arxiv.org/abs/2608.24434v1
• Date: Tue, 25 Aug 2026 11:46:21 GMT
• Title: Nearly Optimal Amplitude Estimation at any Depth
• Abstract summary: We develop a class of amplitude estimation algorithms with tunable circuit depth $M$ and circuit repetitions $N$, requiring neither ancilla qubits nor controlled Grover operations.<n>For additive error $$ in the Grover angle, they attain the nearly optimal query-depth tradeoff $M2NinwidetildeO(-2)$ uniformly over $in[0,/2]$, spanning the full range from classical sampling at $M=1$ to the Heisenberg limit at $M=(-1)$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop a class of amplitude estimation algorithms with tunable circuit depth $M$ and circuit repetitions $N$, requiring neither ancilla qubits nor controlled Grover operations. For additive error $ε$ in the Grover angle, they attain the nearly optimal query-depth tradeoff $M^2N\in\widetilde{O}(ε^{-2})$ uniformly over $λ\in[0,π/2]$, spanning the full range from classical sampling at $M=1$ to the Heisenberg limit at $M=Θ(ε^{-1})$. While prior depth-tunable work establishes comparable angle-accuracy guarantees only away from the boundaries $λ\to0$ or $π/2$ or at discrete depth tradeoffs, our guarantee extends to both boundaries, so the quantum speedup persists there rather than degrading to classical sampling. Numerical experiments confirm the predicted uniform angle accuracy and show low overhead in practice, making them strong candidates for practical amplitude estimation in the early fault-tolerant regime, with applications such as overlap certification, trial-state verification, and Monte Carlo methods.

Related papers

• Quantum amplitude estimation beyond power-of-two schedules [0.0]
  Non-adaptive quantum amplitude estimation (QAE) fixes its Grover depths in advance, so every circuit can run in parallel.<n>We show that most of this gap comes from two conventional choices: subspace-based post-processing and power-of-two depth ladders.<n>We replace the first by the exact maximum-likelihood estimate, one matrix multiplication per batch of estimates, and the second by a geometric ladder with ratio $r approx 1.45$.
  arXiv  Detail & Related papers  (2026-09-02T15:20:50Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• Transferred QAOA Parameters Remember the Penalty Scale: A $λ$-Resonance Law for Constrained Quantum Optimization [0.0]
  We identify a new, independent axis that governs transfer whenever constraints are encoded as penalties.<n>We prove that at arbitrary fixed QAOA angles $(,)$ of depth $p$, the probability $F()$ on the feasible subspace is a finite real trigonometric mass.<n>The theorem is independent of how the angles were obtained and applies to any integer-penalty QUBO.
  arXiv  Detail & Related papers  (2026-07-10T19:23:41Z)
• Optimal algorithmic complexity of inference in quantum kernel methods [0.815557531820863]
  Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning.<n>Standard approach estimates each term independently via sampling, yielding a query complexity of $O(NlVertrVert2/varepsilon2)$.<n>We propose a query-optimal combination, encoding the full inference sum as the expectation value of a single observable.<n>Our results provide both a query-optimal algorithm and a practically optimal choice of strategy depending on hardware capabilities.
  arXiv  Detail & Related papers  (2026-04-16T16:45:02Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Quantum Phaselift [0.0]
  We introduce a lifting-based framework that estimates the rank-one matrix $Z = f fdagger$ rather than estimating $f$ directly.<n>We prove that a $O(1)$ bandwidth suffices for generic signals, leading to substantial savings in controlled operations.<n>We numerically demonstrate that high-quality recovery is possible for the 2D Fermi-Hubbard and 2D transverse-field Ising model signals of size exceeding 100 time points.
  arXiv  Detail & Related papers  (2026-02-09T19:09:57Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• A gradient estimator via L1-randomization for online zero-order optimization with two point feedback [93.57603470949266]
  We present a novel gradient estimator based on two function evaluation and randomization. We consider two types of assumptions on the noise of the zero-order oracle: canceling noise and adversarial noise. We provide an anytime and completely data-driven algorithm, which is adaptive to all parameters of the problem.
  arXiv  Detail & Related papers  (2022-05-27T11:23:57Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• Low depth algorithms for quantum amplitude estimation [6.148105657815341]
  We design and analyze two new low depth algorithms for amplitude estimation (AE) These algorithms bring quantum speedups for Monte Carlo methods closer to realization.
  arXiv  Detail & Related papers  (2020-12-06T18:39:20Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.