Iterative Quantum Amplitude Estimation
arXiv:1912.05559 · doi:10.1038/s41534-021-00379-1
Abstract
We introduce a new variant of Quantum Amplitude Estimation (QAE), called Iterative QAE (IQAE), which does not rely on Quantum Phase Estimation (QPE) but is only based on Grover's Algorithm, which reduces the required number of qubits and gates. We provide a rigorous analysis of IQAE and prove that it achieves a quadratic speedup up to a double-logarithmic factor compared to classical Monte Carlo simulation. Furthermore, we show with an empirical study that our algorithm outperforms other known QAE variants without QPE, some even by orders of magnitude, i.e., our algorithm requires significantly fewer samples to achieve the same estimation accuracy and confidence level.
arXiv commentfixed typos, figures, references
References in corpus (7)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Amplitude Amplification and Estimation
- Quantum Generative Adversarial Networks for Learning and Loading Random Distributions
- Quantum Risk Analysis
- Quantum computational finance: Monte Carlo pricing of financial derivatives
- Quantum Approximate Counting, Simplified
- Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
Cited by in corpus (70)
- Quantum computing for finance
- Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
- A Threshold for Quantum Advantage in Derivative Pricing
- Low depth algorithms for quantum amplitude estimation
- Variational quantum amplitude estimation
- Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth
- Ancilla-free implementation of generalized measurements for qubits embedded in a qudit space
- Towards Quantum Advantage in Financial Market Risk using Quantum Gradient Algorithms
- A variational quantum algorithm for the Feynman-Kac formula
- Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
- Quantum Phase Processing and its Applications in Estimating Phase and Entropies
- Amplitude Estimation from Quantum Signal Processing
- The Problem with Grover-Rudolph State Preparation for Quantum Monte-Carlo
- Efficient Hamiltonian Simulation for Solving Option Price Dynamics
- Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation
- Perturbation theory with quantum signal processing
- Quantum Signal Processing for simulating cold plasma waves
- Non-asymptotic Heisenberg scaling: experimental metrology for a wide resources range
- Quantum Monte Carlo for Economics: Stress Testing and Macroeconomic Deep Learning
- Derivative Pricing using Quantum Signal Processing
- Short Quantum Circuits in Reinforcement Learning Policies for the Vehicle Routing Problem
- Quantum Monte Carlo simulations for financial risk analytics: scenario generation for equity, rate, and credit risk factors
- Efficient option pricing with unary-based photonic computing chip and generative adversarial learning
- Quantum simulation of colour in perturbative quantum chromodynamics
- Accelerated quantum circuit Monte-Carlo simulation for heavy quark thermalization
- Noisy quantum amplitude estimation without noise estimation
- Quantum Fourier Iterative Amplitude Estimation
- Option pricing under stochastic volatility on a quantum computer
- Tight Bound for Estimating Expectation Values from a System of Linear Equations
- Loop Feynman integration on a quantum computer
- Simulation of linear non-Hermitian boundary-value problems with quantum singular value transformation
- Quantum data encoding as a distinct abstraction layer in the design of quantum circuits
- Consistency testing for robust phase estimation
- Design nearly optimal quantum algorithm for linear differential equations via Lindbladians
- More quantum chemistry with fewer qubits
- Towards practical Quantum Credit Risk Analysis
- End-to-end complexity for simulating the Schwinger model on quantum computers
- Quantum mean estimation for lattice field theory
- Noise-Aware Quantum Amplitude Estimation
- Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization
- Energy risk analysis with Dynamic Amplitude Estimation and Piecewise Approximate Quantum Compiling
- Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos
- Disti-Mator: an entanglement distillation-based state estimator
- Quantum Computing for Data Centric Engineering and Science
- Conditions for a quadratic quantum speedup in nonlinear transforms with applications to energy contract pricing
- Bayesian Quantum Amplitude Estimation
- Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications
- Quantum integration of decay rates at second order in perturbation theory
- Adaptive measurement strategy for noisy quantum amplitude estimation with variational quantum circuits
- Tensor-Programmable Quantum Circuits for Solving Differential Equations
- Quantum-enhanced mean value estimation via adaptive measurement
- Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
- Quadratic speed-ups in quantum kernelized binary classification
- Prospects for NMR Spectral Prediction on Fault-Tolerant Quantum Computers
- Low Depth Phase Oracle Using a Parallel Piecewise Circuit
- Des-q: a quantum algorithm to provably speedup retraining of decision trees
- Simulating quantum collision models with Hamiltonian simulations using early fault-tolerant quantum computers
- Conditional Generative Models for Learning Stochastic Processes
- Classical post-processing approach for quantum amplitude estimation
- A general approach to quantum integration of cross sections in high-energy physics
- Measurement Schemes for Quantum Linear Equation Solvers
- Quantum Boosting using Domain-Partitioning Hypotheses
- Efficient quantum algorithm for weighted partial sums and numerical integration
- Improved Quantum Query Complexity on Easier Inputs
- Comprehensive Study on Heisenberg-limited Quantum Algorithms for Multiple Observables Estimation
- On the bias in iterative quantum amplitude estimation
- Quantum algorithm for anisotropic diffusion and convection equations with vector norm scaling
- Quantum Machine Learning with SQUID
- Quantum Speedup for Nonreversible Markov Chains
- Quantum State Preparation and Non-Unitary Evolution with Diagonal Operators