Source-linked AI summary
Amplitude estimation without phase estimation
Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tomoki Tanaka, Tamiya Onodera, Naoki Yamamoto
TL;DR
Amplitude estimation is an important quantum-computing subroutine, while conventional phase-estimation implementations require controlled operations and are problematic for NISQ devices. The paper replaces those controlled operations with maximum likelihood estimation over combined measurements from circuits using different amplification counts. Numerical simulations show quantum-speedup scaling, with fitted error slopes of -0.76 for LIS and -0.95 for EIS, and estimation errors comparable to the conventional phase-estimation approach.
Problem
Conventional amplitude estimation relies on phase estimation with many controlled operations and additional qubits, making it difficult to implement on NISQ devices.
Method
The algorithm combines measurement outcomes from amplitude-amplification circuits with different operation counts and applies maximum likelihood estimation.
Results
The algorithm achieves quantum speedup with reduced controlled gates; simulations give fitted error slopes of -0.76 for LIS and -0.95 for EIS, with errors comparable to conventional phase estimation.
Takeaways & Limitations
The approach provides a quantum amplitude-estimation procedure suited to shorter, less demanding circuits while retaining asymptotically advantageous scaling.
Takeaways & Limitations
The quantum advantages are guaranteed only asymptotically, while the parallel approach still requires rigorous proofs and depth-limited speedups remain future work.
Abstract
from arXiv · showhide
This paper focuses on the quantum amplitude estimation algorithm, which is a core subroutine in quantum computation for various applications. The conventional approach for amplitude estimation is to use the phase estimation algorithm, which consists of many controlled amplification operations followed by a quantum Fourier transform. However, the whole procedure is hard to implement with current and near-term quantum computers. In this paper, we propose a quantum amplitude estimation algorithm without the use of expensive controlled operations; the key idea is to utilize the maximum likelihood estimation based on the combined measurement data produced from quantum circuits with different numbers of amplitude amplification operations. Numerical simulations we conducted demonstrate that our algorithm asymptotically achieves nearly the optimal quantum speedup with a reasonable circuit length.
1 Introduction
Amplitude estimation is an important quantum-computing subroutine, but conventional phase-estimation implementations are difficult for NISQ devices. The paper proposes combining measurements from amplitude-amplification circuits with different operation counts through maximum likelihood estimation.
- NISQ devices impose practical limitations on gate operations and available qubits, motivating specialized quantum subroutines.
- Amplitude estimation supports applications in chemistry, finance, and machine learning, including quantum speedup for Monte Carlo sampling.
- Conventional amplitude estimation uses phase estimation with controlled amplification operations and a subsequent quantum Fourier transform.
- The proposed scheme estimates θ by combining likelihood functions from measurements of amplified states with several m values.
2 Preliminary
Amplitude amplification increases the probability of measuring a good state, providing the quantum mechanism used for amplitude estimation. The preliminary analysis relates this amplification to quadratic query advantages while identifying the role of the amplification count.
- The algorithm combines quantum amplitude amplification with likelihood-based amplitude estimation.
- The unknown parameter a is inferred from repeated measurements of good and bad states, but measuring immediately after A uses the same query count as classical sampling.
- Amplitude amplification transforms the good-state probability through repeated applications of Q, with θ_a defined by sin^2 θ_a = a.
- For sufficiently small a, m applications of Q use 2m queries and produce a good-state probability at least 4m^2 times larger than applying A alone.
- Conventional phase-estimation-based amplitude estimation requires multiple controlled-Q operations and additional ancilla qubits, creating difficulties for NISQ devices.
3 Amplitude estimation without phase estimation
The algorithm estimates amplitudes by combining likelihood functions from measurements after different numbers of amplitude-amplification operations, without controlled operations or a quantum Fourier transform. Its exponentially incremental sequence achieves asymptotically optimal scaling, while simulations show near-theoretical performance and comparable error to conventional phase estimation.
- Algorithm: The algorithm measures good-state counts after applying Q^m_k for selected amplification counts, constructs likelihoods L_k, combines them into L(h;θ_a), and maximizes the result.The estimate is θ̂_a = arg max L(h;θ_a), with â = sin^2 θ̂_a.
- Algorithm: Using only one amplified circuit can make the maximum-likelihood estimate non-unique, whereas using no amplification preserves uniqueness but provides no quantum advantage.The method therefore combines circuits with different amplification counts to determine the target uniquely while retaining quantum advantage.
- Statistics: Maximum-likelihood estimation becomes unbiased and attains the Cramér–Rao lower bound asymptotically as the measurement-data volume grows.This property motivates analyzing Fisher information to design amplification-count and shot sequences.
- Statistics: For LIS, N_q = N_shot(M + 1)^2 and the asymptotic estimation error scales as N_q^-3/4, yielding a quantum advantage below the Heisenberg limit.The Fisher information scales as N_shot M^3/[3a(1 − a)] when M ≫ 1.
- Statistics: For EIS, N_q ∼ N_shot 2^(M+1) and the estimation error scales as N_q^-1, which the paper identifies as asymptotically optimal.The paper cautions that these advantages are guaranteed asymptotically and require finite-depth performance evaluation.
- Numerical simulation: Simulations fit slopes γ = −0.76 for LIS, γ = −0.95 for EIS, and γ = −0.50 for classical sampling; EIS errors approach the Cramér–Rao bound and are comparable to conventional phase estimation.The fitted slopes use target probability a = 1/48 over N_q ≃ 10^3 to 10^5, with similar slopes for other target probabilities.
4 Application to the Monte Carlo integration
The paper applies its amplitude-estimation approach to Monte Carlo integration by encoding an expected value as an amplitude and comparing the resulting circuits with conventional amplitude estimation. In the illustrated implementation, the proposed algorithm uses fewer CNOT gates and a constant number of qubits as the number of amplification operations grows.
- Monte Carlo integration: The application estimates the expected value of a real-valued function f(x), with 0 ≤ f(x) ≤ 1, over n-bit inputs distributed according to p(x).The expected value is treated as the quantity to compute through amplitude estimation.
- State preparation: The quantum construction introduces an ancilla qubit and uses operators P and R to prepare a state whose good-state amplitude encodes the square root of the expected value.The operator P prepares the input distribution, while R performs controlled Y-rotations on the ancilla.
- State preparation: By writing the expected value as a = sin^2 θ_a, the Monte Carlo integral becomes an amplitude-estimation problem to which the proposed algorithm can be applied.The amplitude-amplification operator is constructed from reflections about the prepared state and the good-state basis state.
- Simple example: For the sine-integral example, the integral is discretized on an n-qubit register, with the operator P constructed from n Hadamard gates and R from controlled Y-rotations.The operator R acts on the n-qubit input register and one ancilla qubit.
- Circuit comparison: In the n = 2 circuit example, conventional amplitude estimation tends to use more gates and qubits, while its multi-controlled operation may require additional ancillas.The comparison assumes all-to-all qubit connectivity.
- Circuit comparison: 7–18 times smaller CNOT counts are reported for the proposed algorithm, whose qubit requirement remains constant as the number of Q operations increases.The comparison uses the supported Qiskit ver. 0.7 gate set and evaluates the proposed circuit with the largest m_k.
5 Conclusion
The proposed amplitude estimation algorithm reduces controlled gates through maximum-likelihood estimation of measurements from amplitude-amplified states. Simulations found fewer queries than classical estimation and errors close to the Heisenberg limit, while future work remains for rigorous parallel-analysis proofs and depth-limited speedups.
- Conclusion: The algorithm achieves quantum speedup by reducing controlled gates through maximum-likelihood estimation.It constructs one likelihood function from measurement outcomes of several amplitude-amplified quantum states.
- Conclusion: Numerical simulations found that the algorithm estimated target values with fewer queries than the classical algorithm.
- Conclusion: The observed estimation error was sufficiently close to the Heisenberg limit based on a Fisher-information lower bound.
- Conclusion: The proposed parallel approach still needs rigorous proofs, while depth-limited quantum speedups remain a future-work direction.Simplified alternatives are adaptive, sequential, and may require millions of measurement samples.
Appendix A: Comparison of estimation errors with conventional amplitude estimation
The appendix compares estimation error versus query count for conventional phase-estimation-based amplitude estimation and the proposed method. With Nshot = 30, the proposed method has nearly the same error as the conventional algorithm, while increasing shots reduces its relative quantum speedup.
- Comparison setup: The comparison evaluates estimation error against query count for conventional amplitude estimation and the proposed algorithm.For simplicity, the appendix reports only a = sin2 θa = 1/48.
- Comparison results: Nshot = 30 produces estimation error almost the same as the conventional algorithm.The conventional approach uses controlled Q operations followed by a quantum Fourier transform.
- Comparison results: Increasing the number of shots gradually increases the proposed method’s estimation error.
- Comparison results: When shots approach the total query count, quantum speedup becomes relatively smaller because sampling becomes essentially classical.
- Figure encoding: The figure compares conventional results with 81-percentile errors for Nshot = 30, Nshot = 100, and classical sampling.The conventional data are black circles; the proposed results are red triangles and blue squares, and classical sampling is shown with green crosses.