Heisenberg-limited adaptive gradient estimation for multiple observables

Abstract

In quantum mechanics, measuring the expectation value of a general observable has an inherent statistical uncertainty that is quantified by variance or mean squared error of measurement outcome. While the uncertainty can be reduced by averaging several samples, the number of samples should be minimized when each sample is very costly. This is especially the case for fault-tolerant quantum computing that involves measurement of multiple observables of non-trivial states in large quantum systems that exceed the capabilities of classical computers. In this work, we provide an adaptive quantum algorithm for estimating the expectation values of $M$ general observables within root mean squared error $\epsilon$ simultaneously, using $\mathcal{O}({\epsilon }^{-1}\sqrt{M}\log M)$ queries to a state preparation oracle of a target state. This remarkably achieves the scaling of Heisenberg limit $1/\epsilon$, a fundamental bound on the estimation precision in terms of mean squared error, together with the sublinear scaling of the number of observables $M$. The proposed method is an adaptive version of the quantum gradient estimation algorithm and has a resource-efficient implementation due to its adaptiveness. Specifically, the space overhead in the proposed method is $\mathcal{O}(M)$ which is independent from the estimation precision $\epsilon$ unlike non-iterative algorithms. In addition, our method can avoid the numerical instability problem for constructing quantum circuits in a large-scale task (e.g., $\epsilon \ll 1$ in our case), which appears in the actual implementation of many algorithms relying on quantum signal processing techniques. Our method paves a new way to precisely understand and predict various physical properties in complicated quantum systems using quantum computers.

arXiv commentFinal version, add new analytical and numerical results

References in corpus (47)

• Quantum Machine Learning
• Advances in Quantum Metrology
• Quantum-enhanced measurements: beating the standard quantum limit
• Quantum metrology
• Simulated Quantum Computation of Molecular Energies
• Quantum Amplitude Amplification and Estimation
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Quantum Metrology in Non-Markovian Environments
• Entanglement-free Heisenberg-limited phase estimation
• Toward the first quantum simulation with quantum speedup
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• A rigorous and robust quantum speed-up in supervised machine learning
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Improved quantum metrology using quantum error-correction
• Quantum Error Correction for Metrology
• Achieving the Heisenberg limit in quantum metrology using quantum error correction
• Amplitude estimation without phase estimation
• Provably efficient machine learning for quantum many-body problems
• Option Pricing using Quantum Computers
• Magnet field sensing beyond the standard quantum limit under the effect of decoherence
• Optimal Quantum Measurements of Expectation Values of Observables
• Increasing sensing resolution with error correction
• How to perform the most accurate possible phase measurements
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Efficient phase-factor evaluation in quantum signal processing
• The methodology of resonant equiangular composite quantum gates
• Demonstrating Heisenberg-limited unambiguous phase estimation without adaptive measurements
• Parameter estimation of quantum channels
• Fast quantum algorithm for numerical gradient estimation
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• A Threshold for Quantum Advantage in Derivative Pricing
• Optimal quantum circuits for general phase estimation
• $\pi$-Corrected Heisenberg Limit
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Minimizing estimation runtime on noisy quantum computers
• Quantum Algorithms for Estimating Physical Quantities using Block-Encodings
• Efficient quantum computation of molecular forces and other energy gradients
• Hunting for quantum-classical crossover in condensed matter problems
• Towards Quantum Advantage in Financial Market Risk using Quantum Gradient Algorithms
• Achieving Heisenberg scaling with maximally entangled states: an analytic upper bound for the attainable root mean square error
• Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits
• Stable factorization for phase factors of quantum signal processing
• The advantage of quantum control in many-body Hamiltonian learning
• Usefulness of an enhanced Kitaev phase-estimation algorithm in quantum metrology and computation
• Quantum-enhanced mean value estimation via adaptive measurement

Cited by in corpus (2)

• Comprehensive Study on Heisenberg-limited Quantum Algorithms for Multiple Observables Estimation
• Faster Quantum Algorithm for Multiple Observables Estimation in Fermionic Problems