In this paper, we introduce an efficient algorithm for the quantum amplitude estimation task which is tailored for near-term quantum computers. The quantum amplitude estimation is an important problem which has various applications in fields such as quantum chemistry, machine learning, and finance. Because the well-known algorithm for the quantum amplitude estimation using the phase estimation does not work in near-term quantum computers, alternative approaches have been proposed in recent literature. Some of them provide a proof of the upper bound which almost achieves the Heisenberg scaling. However, the constant factor is large and thus the bound is loose. Our contribution in this paper is to provide the algorithm such that the upper bound of query complexity almost achieves the Heisenberg scaling and the constant factor is small.
In this paper, we introduce an efficient algorithm for the quantum amplitude estimation task which is tailored for near-term quantum computers. The quantum amplitude estimation is an important problem which has various applications in fields such as quantum chemistry, machine learning, and finance. Because the well-known algorithm for the quantum amplitude estimation using the phase estimation does not work in near-term quantum computers, alternative approaches have been proposed in recent literature. Some of them provide a proof of the upper bound which almost achieves the Heisenberg scaling. However, the constant factor is large and thus the bound is loose. Our contribution in this paper is to provide the algorithm such that the upper bound of query complexity almost achieves the Heisenberg scaling and the constant factor is small.
In this work, we provide the first QFT-free algorithm for Quantum Amplitude Estimation (QAE) that is asymptotically optimal while maintaining the leading numerical performance. QAE algorithms appear as a subroutine in many applications for quantum computers. The optimal query complexity achievable by a quantum algorithm for QAE is log queries, providing a speedup of a factor of 1/ε over any other classical algorithm for the same problem. The original algorithm for QAE utilizes the quantum Fourier transform (QFT) which is expected to be a challenge for near-term quantum hardware. To solve this problem, there has been interest in designing a QAE algorithm that avoids using QFT. Recently, the iterative QAE algorithm (IQAE) [1] was introduced with a near-optimal query complexity and small constant factors. In this work, we combine ideas from the preceding line of work to introduce a QFT-free QAE algorithm that maintains the asymptotically optimal query complexity while retaining small constant factors. We supplement our analysis with numerical experiments comparing our performance with IQAE where we find that our modifications retain the high performance, and in some cases even improve the numerical results.
The Quantum Amplitude Estimation (QAE) algorithm is a major quantum algorithm designed to achieve a quadratic speed-up. Until fault-tolerant quantum computing is achieved, being competitive over classical Monte Carlo (MC) remains elusive. Alternative methods have been developed so as to require fewer resources while maintaining an advantageous theoretical scaling. We compared the standard QAE algorithm with two Noisy Intermediate-Scale Quantum (NISQ)-friendly versions of QAE on a numerical integration task, with the Monte Carlo technique of Metropolis–Hastings as a classical benchmark. The algorithms were evaluated in terms of the estimation error as a function of the number of samples, computational time, and length of the quantum circuits required by the solutions, respectively. The effectiveness of the two QAE alternatives was tested on an 11-qubit trapped-ion quantum computer in order to verify which solution can first provide a speed-up in the integral estimation problems. We concluded that an alternative approach is preferable with respect to employing the phase estimation routine. Indeed, the Maximum Likelihood estimation guaranteed the best trade-off between the length of the quantum circuits and the precision in the integral estimation, as well as greater resistance to noise.
In this work, we study the phase estimation problem. We show an alternative, simpler and self-contained proof of query lower bounds. Technically, compared to the previous proofs [NW99, Bes05], our proof is considerably elementary. Specifically, our proof consists of basic linear algebra without using the knowledge of Boolean function analysis and adversary methods. Qualitatively, our bound is tight in the low success probability regime and offers a more fine-grained trade-off. In particular, we prove that for any ε>0,p≥0, every algorithm requires at least Ω(p/ε) queries to obtain an ε-approximation for the phase with probability at least p. However, the existing bounds hold only when p>1/2. Quantitatively, our bound is tight since it matches the well-known phase estimation algorithm of Cleve, Ekert, Macchiavello, and Mosca [CEMM98] which requires O(1/ε) queries to obtain an ε-approximation with a constant probability. Following the derivation of the lower bound in our framework, we give a new and intuitive interpretation of the phase estimation algorithm of [CEMM98], which might be of independent interest.
Given a linear system of equations Ax=b, quantum linear system solvers (QLSSs) approximately prepare a quantum state ∣x⟩ for which the amplitudes are proportional to the solution vector x. Asymptotically optimal QLSSs have query complexity O(κlog(1/ε)), where κ is the condition number of A, and ε is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant prefactors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple QLSS that does not use these techniques. If the solution norm ∥x∥ is known exactly, our QLSS requires only a single application of kernel reflection (a straightforward extension of the eigenstate filtering (EF) technique of previous work) and the query complexity of the QLSS is (1+O(ε))κln(22/ε). If the norm is unknown, our method allows it to be estimated up to a constant factor using O(loglog(κ)) applications of kernel projection (a direct generalization of EF) yielding a straightforward QLSS with near-optimal O(κloglog(κ)logloglog(κ)+κlog(1/ε)) total complexity. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that O(κ) complexity can be achieved for norm estimation, yielding an optimal QLSS with O(κlog(1/ε)) complexity while still avoiding the need to invoke the adiabatic theorem. Finally, we compute an explicit upper bound of 56κ+1.05κln(1/ε)+o(κ) for the complexity of our optimal QLSS.
Quantum amplitude estimation is a key sub-routine of a number of quantum algorithms with various applications. We propose an adaptive algorithm for interval estimation of amplitudes. The quantum part of the algorithm is based only on Grover's algorithm. The key ingredient is the introduction of an adjustment factor, which adjusts the amplitude of good states such that the amplitude after the adjustment, and the original amplitude, can be estimated without ambiguity in the subsequent step. We show with numerical studies that the proposed algorithm uses a similar number of quantum queries to achieve the same level of precision ε compared to state-of-the-art algorithms, but the classical part, i.e., the non-quantum part, has substantially lower computational complexity. We rigorously prove that the number of oracle queries achieves O(1/ε), i.e., a quadratic speedup over classical Monte Carlo sampling, and the computational complexity of the classical part achieves O(log(1/ε)), both up to a double-logarithmic factor.
In the accompanying paper of arXiv:2505.00697, we have presented a generalized scheme of adaptive quantum gradient estimation (QGE) algorithm, and further proposed two practical variants which not only achieve doubly quantum enhancement in query complexity regarding estimation precision and number of observables, but also enable minimal cost to estimate k-RDMs in fermionic systems among existing quantum algorithms. Here, we provide full descriptions on the algorithm, and provide theoretical guarantee for the estimation precision in terms of the root mean squared error. Furthermore, we analyze the performance of the quantum amplitude estimation algorithm, another variant of the Heisenberg-limited scaling algorithm, and show how the estimation error is minimized under the circuit structure that resembles the phase estimation algorithm. We finally describe the details for the numerical evaluation of the query complexity of the Heisenberg-limited algorithms and sampling-based methods to make a thorough comparison in the task of estimating fermionic k-RDMs.