Amplitude estimation, in its original form, is formulated as phase estimation upon the Grover iterate. Subsequent improvements to the algorithm have eliminated the need for phase estimation and introduced low-depth variants that trade speedups for lower circuit depth. We make the key observation that amplitude estimation is equivalent to estimating the energy gap of an effective Hamiltonian, whereby discrete-time evolution is generated by amplitude amplification. This enables us to develop an amplitude estimation algorithm for both Heisenberg-limited and low-depth circuit regimes, inspired by statistical phase estimation techniques developed for early fault-tolerant ground-state energy estimation. In the Heisenberg-limited regime, our approach achieves performance comparable to state-of-the-art methods while using simplified classical post-processing. In the low-depth regime, it obtains optimal query--depth tradeoffs up to polylogarithmic factors, with provable guarantees and improved empirical performance over prior approaches. The resulting protocol is ancilla-free and requires only standard Grover reflections. Due to its flexibility, generality, and robustness, we expect our approach to be a key enabler for a broad range of early fault-tolerant applications.
Amplitude estimation, in its original form, is formulated as phase estimation upon the Grover iterate. Subsequent improvements to the algorithm have eliminated the need for phase estimation and introduced low-depth variants that trade speedups for lower circuit depth. We make the key observation that amplitude estimation is equivalent to estimating the energy gap of an effective Hamiltonian, whereby discrete-time evolution is generated by amplitude amplification. This enables us to develop an amplitude estimation algorithm for both Heisenberg-limited and low-depth circuit regimes, inspired by statistical phase estimation techniques developed for early fault-tolerant ground-state energy estimation. In the Heisenberg-limited regime, our approach achieves performance comparable to state-of-the-art methods while using simplified classical post-processing. In the low-depth regime, it obtains optimal query--depth tradeoffs up to polylogarithmic factors, with provable guarantees and improved empirical performance over prior approaches. The resulting protocol is ancilla-free and requires only standard Grover reflections. Due to its flexibility, generality, and robustness, we expect our approach to be a key enabler for a broad range of early fault-tolerant applications.
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 M2N∈O(ε−2) uniformly over λ∈[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 λ→0 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.
We develop a phase-estimation method with a distinct feature: its maximal run time (which determines the circuit depth) is δ/ , where is the target precision, and the preconstant δ can be arbitrarily close to 0 as the initial state approaches the target eigenstate.The total cost of the algorithm satisfies the Heisenberg-limited scaling O( -1 ).As a result, our algorithm may significantly reduce the circuit depth for performing phase-estimation tasks on early fault-tolerant quantum computers.The key technique is a simple subroutine called quantum complex exponential least squares (QCELS).Our algorithm can be readily applied to reduce the circuit depth for estimating the ground-state energy of a quantum Hamiltonian, when the overlap between the initial state and the ground state is large.If this initial overlap is small, we can combine our method with the Fourier-filtering method developed in [Lin and Tong, PRX Quantum 3, 010318, 2022], and the resulting algorithm provably reduces the circuit depth in the presence of a large relative overlap compared to .The relative-overlap condition is similar to a spectral-gap assumption but it is aware of the information in the initial state and is therefore applicable to certain Hamiltonians with small spectral gaps.We observe that the circuit depth can be reduced by around 2 orders of magnitude in numerical experiments under various settings.
We design and analyze two new low depth algorithms for amplitude estimation (AE) achieving an optimal tradeoff between the quantum speedup and circuit depth. For β∈(0,1] , our algorithms require N=O~(1ϵ1+β) oracle calls and require the oracle to be called sequentially D=O(1ϵ1−β) times to perform amplitude estimation within additive error ϵ . These algorithms interpolate between the classical algorithm (β=1) and the standard quantum algorithm ( β=0 ) and achieve a tradeoff ND=O(1/ϵ2) . These algorithms bring quantum speedups for Monte Carlo methods closer to realization, as they can provide speedups with shallower circuits.The first algorithm (Power law AE) uses power law schedules in the framework introduced by Suzuki et al \cite{S20}. The algorithm works for β∈(0,1] and has provable correctness guarantees when the log-likelihood function satisfies regularity conditions required for the Bernstein Von-Mises theorem. The second algorithm (QoPrime AE) uses the Chinese remainder theorem for combining lower depth estimates to achieve higher accuracy. The algorithm works for discrete β=q/k where k≥2 is the number of distinct coprime moduli used by the algorithm and 1≤q≤k−1 , and has a fully rigorous correctness proof. We analyze both algorithms in the presence of depolarizing noise and provide numerical comparisons with the state of the art amplitude estimation algorithms.
Non-adaptive quantum amplitude estimation (QAE) fixes its Grover depths in advance, so every circuit can run in parallel, but it has so far needed more queries than the best adaptive methods. We show that most of this gap comes from two conventional choices: subspace-based post-processing and power-of-two depth ladders. 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≈1.45. The result is a fully parallel, deterministic-schedule estimator with total query complexity 2.8-3.1/ε at 95% confidence for target errors from 3.5×10−3 to 10−6. This matches the average-case complexity of chebAE, the best benchmarked adaptive method, within statistical uncertainty (with the lower point estimate at every scale tested), beats its maximum-observed complexity by 1.6×, and needs a maximum sequential depth of only 0.21/ε against chebAE's 2.9/ε. Relative to csAE, the best non-adaptive benchmark, the constants improve by 30-35% at 95% and 1.5-1.7× at 99% confidence. The optimal ratio has a simple origin. Doubling is the fastest depth growth at which the data can still tell neighboring candidate values apart, so power-of-two ladders sit at the edge of confusion and must buy reliability with extra shots; a slightly denser ladder checks every scale redundantly. An error-probability analysis reproduces the measured failure rates and locates the optimum. The likelihood formulation extends directly to noise-aware estimation, and uniformly scaling the capped ladder covers the depth-limited regime, realizing the optimal trade-off MNtot≈(0.4-0.6)/ε2 within ∼1.1× of the schedule's Cramér-Rao limit.
Quantum amplitude estimation is one of the core subroutines in quantum algorithms. This paper gives a parallelized amplitude estimation (PAE) algorithm that simultaneously achieves near-Heisenberg scaling in the total number of queries and sub-linear scaling in the circuit depth, with respect to the estimation precision. The algorithm is composed of a global GHZ state followed by separated low-depth Grover circuits optimized by quantum signal processing techniques; the number of qubits in the GHZ state and the depth of each circuit is tunable as a trade-off way, which particularly enables even near-Heisenberg-limited and logarithmic-depth algorithm for amplitude estimation. We prove that this trade-off scaling is nearly optimal with use of the parallel quantum adversary method, against folklore on the impossibility of efficient parallelization in amplitude estimation. The proposed algorithm has a form of distributed quantum computing, which may be suitable for device implementation.
Under suitable assumptions, the quantum-phase-estimation (QPE) algorithm is able to achieve Heisenberg-limited precision scaling in estimating the ground-state energy.However, QPE requires a large number of ancilla qubits and a large circuit depth, as well as the ability to perform inverse quantum Fourier transform, making it expensive to implement on an early fault-tolerant quantum computer.We propose an alternative method to estimate the ground-state energy of a Hamiltonian with Heisenberglimited precision scaling, which employs a simple quantum circuit with one ancilla qubit, and a classical postprocessing procedure.Besides the ground-state energy, our algorithm also produces an approximate cumulative distribution function of the spectral measure, which can be used to compute other spectral properties of the Hamiltonian.