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.
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.
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most q oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model:
(i) (Unbiased) Phase estimation up to a precision ε requires Θ(qε21) queries;
(ii) (Unbiased) Amplitude estimation up to a precision ε requires Θ(qε2p(1−p)) queries;
(iii) Search among N items requires Θ(qN) queries;
(iv) Two level AND-OR tree (AND of m ORs, with n inputs to each OR) requires Θ(qnm) queries.
All of these bounds are optimal up to a constant factor, for all q from 1, corresponding to the classical complexity, to Q(f), the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor.
Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.
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.