Faster Amplitude Estimation
arXiv:2003.02417 · doi:10.26421/QIC20.13-14-2
Abstract
In this paper, we introduce an efficient algorithm for the quantum amplitude estimation task which works in noisy intermediate-scale quantum(NISQ) devices. 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 cannot be executed in NISQ devices, 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.
arXiv comment10 pages
References in corpus (13)
- Quantum Computing in the NISQ era and beyond
- Quantum Amplitude Amplification and Estimation
- Quantum measurements and the Abelian Stabilizer Problem
- Polynomial-time quantum algorithm for the simulation of chemical dynamics
- Quantum speedup of Monte Carlo methods
- Quantum Risk Analysis
- Quantum computational finance: Monte Carlo pricing of financial derivatives
- Amplitude estimation without phase estimation
- Optimal Quantum Measurements of Expectation Values of Observables
- Quantum Approximate Counting, Simplified
- q-means: A quantum algorithm for unsupervised machine learning
- Quantum Perceptron Models
- Reduction of Qubits in Quantum Algorithm for Monte Carlo Simulation by Pseudo-random Number Generator
Cited by in corpus (15)
- Approximate amplitude encoding in shallow parameterized quantum circuits and its application to financial market indicator
- Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth
- Grover search revisited; application to image pattern matching
- Amplitude Estimation from Quantum Signal Processing
- The Problem with Grover-Rudolph State Preparation for Quantum Monte-Carlo
- Modified Grover operator for amplitude estimation
- Noisy quantum amplitude estimation without noise estimation
- Quantum Amplitude Estimation in the Presence of Noise
- Quantum amplitude estimation algorithms on IBM quantum devices
- Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization
- Noise-Aware Quantum Amplitude Estimation
- Comparison of Amplitude Estimation Algorithms by Implementation
- Quantum-enhanced mean value estimation via adaptive measurement
- Quantum Approximate Counting with Nonadaptive Grover Iterations
- Quantum State Preparation and Non-Unitary Evolution with Diagonal Operators