Comprehensive Study on Heisenberg-limited Quantum Algorithms for Multiple Observables Estimation
arXiv:2505.00698 · doi:10.1103/wrkp-qd33
Abstract
In the accompanying paper of arXiv:2505.00697, we have presented a generalized scheme of adaptive quantum gradient estimation (QGE) algorithm, and further proposed two practical variants which not only achieve doubly quantum enhancement in query complexity regarding estimation precision and number of observables, but also enable minimal cost to estimate -RDMs in fermionic systems among existing quantum algorithms. Here, we provide full descriptions on the algorithm, and provide theoretical guarantee for the estimation precision in terms of the root mean squared error. Furthermore, we analyze the performance of the quantum amplitude estimation algorithm, another variant of the Heisenberg-limited scaling algorithm, and show how the estimation error is minimized under the circuit structure that resembles the phase estimation algorithm. We finally describe the details for the numerical evaluation of the query complexity of the Heisenberg-limited algorithms and sampling-based methods to make a thorough comparison in the task of estimating fermionic -RDMs.
55 pages, 9 figures. Accompanying letter arXiv:2505.00697
References in corpus (42)
- Quantum Machine Learning
- Simulated Quantum Computation of Molecular Energies
- Quantum Amplitude Amplification and Estimation
- Predicting Many Properties of a Quantum System from Very Few Measurements
- Hamiltonian Simulation by Qubitization
- Entanglement-free Heisenberg-limited phase estimation
- Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
- The randomized measurement toolbox
- Quantum certification and benchmarking
- Quantum speedup of Monte Carlo methods
- Information-theoretic bounds on quantum advantage in machine learning
- Rényi Entropies from Random Quenches in Atomic Hubbard and Spin Models
- Characterizing large-scale quantum computers via cycle benchmarking
- Amplitude estimation without phase estimation
- Optimal Quantum Measurements of Expectation Values of Observables
- Iterative Quantum Amplitude Estimation
- How to perform the most accurate possible phase measurements
- Statistical correlations between locally randomized measurements: a toolbox for probing entanglement in many-body quantum states
- Fermionic partial tomography via classical shadows
- The power of random measurements: measuring Tr(ρ^n) on single copies of ρ
- Quantum Overlapping Tomography
- Demonstrating Heisenberg-limited unambiguous phase estimation without adaptive measurements
- Parameter estimation of quantum channels
- Fast quantum algorithm for numerical gradient estimation
- Learning to Measure: Adaptive Informationally Complete Generalized Measurements for Quantum Algorithms
- Nearly Optimal Measurement Scheduling for Partial Tomography of Quantum States
- Optimal quantum circuits for general phase estimation
- Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
- Matchgate Shadows for Fermionic Quantum Simulation
- 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
- Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods
- Amplitude Estimation from Quantum Signal Processing
- Effects of Cosine Tapering Window on Quantum Phase Estimation
- Hamiltonian simulation for low-energy states with optimal time dependence
- Usefulness of an enhanced Kitaev phase-estimation algorithm in quantum metrology and computation
- Unitary Designs of Symmetric Local Random Circuits
- Characterization of randomness in quantum circuits of continuous gate sets
- Efficient measurement schemes for bosonic systems
- Heisenberg-limited adaptive gradient estimation for multiple observables
- Quantum state preparation via piecewise QSVT