Comprehensive Study on Heisenberg-limited Quantum Algorithms for Multiple Observables Estimation

• URL: http://arxiv.org/abs/2505.00698v1
• Date: Thu, 01 May 2025 17:57:27 GMT
• Title: Comprehensive Study on Heisenberg-limited Quantum Algorithms for Multiple Observables Estimation
• Authors: Yuki Koizumi, Kaito Wada, Wataru Mizukami, Nobuyuki Yoshioka,
• Abstract summary: We propose two practical variants of adaptive quantum gradient estimation (QGE) algorithm.<n>We provide theoretical guarantee for the estimation precision in terms of the root mean squared error.<n>We show how the estimation error is minimized under the circuit structure that resembles the phase estimation algorithm.
• Score: 0.19999259391104385
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the accompanying paper of arXiv:25XX.XXXXX, 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 $k$-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 $k$-RDMs.

Related papers

• Faster Quantum Algorithm for Multiple Observables Estimation in Fermionic Problems [0.19999259391104385]
  We propose two variants which enable us to estimate the collective properties of fermionic systems using the smallest cost among existing quantum algorithms.<n>We show that our proposal offers a quadratic speedup compared with prior QGE algorithms in the task of fermionic partial tomography for systems with limited particle numbers.
  arXiv  Detail & Related papers  (2025-05-01T17:57:19Z)
• Fast Expectation Value Calculation Speedup of Quantum Approximate Optimization Algorithm: HoLCUs QAOA [55.2480439325792]
  We present a new method for calculating expectation values of operators that can be expressed as a linear combination of unitary (LCU) operators.<n>This method is general for any quantum algorithm and is of particular interest in the acceleration of variational quantum algorithms.
  arXiv  Detail & Related papers  (2025-03-03T17:15:23Z)
• Heisenberg-limited adaptive gradient estimation for multiple observables [0.39102514525861415]
  In quantum mechanics, measuring the expectation value of a general observable has an inherent statistical uncertainty. We provide an adaptive quantum algorithm for estimating the expectation values of $M$ general observables within root mean squared error. Our method paves a new way to precisely understand and predict various physical properties in complicated quantum systems using quantum computers.
  arXiv  Detail & Related papers  (2024-06-05T14:16:47Z)
• Optimal Coherent Quantum Phase Estimation via Tapering [0.0]
  Quantum phase estimation is one of the fundamental primitives that underpins many quantum algorithms. We propose an improved version of the standard algorithm called the tapered quantum phase estimation algorithm. Our algorithm achieves the optimal query complexity without requiring the expensive coherent median technique.
  arXiv  Detail & Related papers  (2024-03-27T18:17:23Z)
• An adaptive Bayesian quantum algorithm for phase estimation [0.0]
  We present a coherence-based phase-estimation algorithm which can achieve the optimal quadratic scaling in the mean absolute error and the mean squared error. In the presence of noise, our algorithm produces errors that approach the theoretical lower bound.
  arXiv  Detail & Related papers  (2023-03-02T19:00:01Z)
• Quantum-enhanced mean value estimation via adaptive measurement [0.39102514525861415]
  Mean value estimation of observables is an essential subroutine in quantum computing algorithms. The quantum estimation theory identifies the ultimate precision of such an estimator, which is referred to as the quantum Cram'er-Rao (QCR) lower bound or equivalently the inverse of the quantum Fisher information. We propose a quantum-enhanced mean value estimation method in a depolarizing noisy environment that saturates the QCR bound in the limit of a large number of qubits.
  arXiv  Detail & Related papers  (2022-10-27T17:13:07Z)
• Unbiased quantum phase estimation [5.324438395515079]
  Quantum phase estimation algorithm (PEA) is one of the most important algorithms in early studies of quantum computation. We find that the PEA is not an unbiased estimation, which prevents the estimation error from achieving an arbitrarily small level. We propose an unbiased phase estimation algorithm (A) based on the original PEA, and study its application in quantum counting.
  arXiv  Detail & Related papers  (2022-10-01T09:38:20Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Improved maximum-likelihood quantum amplitude estimation [0.0]
  Quantum estimation is a key subroutine in a number of powerful quantum algorithms, including quantum-enhanced Monte Carlo simulation and quantum machine learning. In this article, we deepen the analysis of Maximum-likelihood quantum amplitude estimation (MLQAE) to put the algorithm in a more prescriptive form, including scenarios where quantum circuit depth is limited. We then propose and numerically validate a modification to the algorithm to overcome this problem, bringing the algorithm even closer to being useful as a practical subroutine on near- and mid-term quantum hardware.
  arXiv  Detail & Related papers  (2022-09-07T17:30:37Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Reducing the cost of energy estimation in the variational quantum eigensolver algorithm with robust amplitude estimation [50.591267188664666]
  Quantum chemistry and materials is one of the most promising applications of quantum computing. Much work is still to be done in matching industry-relevant problems in these areas with quantum algorithms that can solve them.
  arXiv  Detail & Related papers  (2022-03-14T16:51:36Z)
• Dual-Frequency Quantum Phase Estimation Mitigates the Spectral Leakage of Quantum Algorithms [76.15799379604898]
  Quantum phase estimation suffers from spectral leakage when the reciprocal of the record length is not an integer multiple of the unknown phase. We propose a dual-frequency estimator, which approaches the Cramer-Rao bound, when multiple samples are available.
  arXiv  Detail & Related papers  (2022-01-23T17:20:34Z)
• Numerical Simulations of Noisy Quantum Circuits for Computational Chemistry [51.827942608832025]
  Near-term quantum computers can calculate the ground-state properties of small molecules. We show how the structure of the computational ansatz as well as the errors induced by device noise affect the calculation.
  arXiv  Detail & Related papers  (2021-12-31T16:33:10Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Efficient qubit phase estimation using adaptive measurements [0.0]
  Estimating the quantum phase of a physical system is a central problem in quantum parameter estimation theory. Current methods to estimate quantum phases fail to reach the quantum Cram'er-Rao bound. We propose a new adaptive scheme based on covariant measurements to circumvent this problem.
  arXiv  Detail & Related papers  (2020-12-21T02:43:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.