A randomized quantum algorithm for statistical phase estimation

• URL: http://arxiv.org/abs/2110.12071v2
• Date: Wed, 13 Jul 2022 19:37:23 GMT
• Title: A randomized quantum algorithm for statistical phase estimation
• Authors: Kianna Wan and Mario Berta and Earl T. Campbell
• Abstract summary: We propose and rigorously analyse a randomized phase estimation algorithm with two distinctive features. First, our algorithm has complexity independent of the number of terms L in the Hamiltonian. Second, unlike previous L-independent approaches, all sources of error in our algorithm can be suppressed by collecting more data samples.
• Score: 8.701566919381223
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Phase estimation is a quantum algorithm for measuring the eigenvalues of a Hamiltonian. We propose and rigorously analyse a randomized phase estimation algorithm with two distinctive features. First, our algorithm has complexity independent of the number of terms L in the Hamiltonian. Second, unlike previous L-independent approaches, such as those based on qDRIFT, all sources of error in our algorithm can be suppressed by collecting more data samples, without increasing the circuit depth.

Related papers

• Comprehensive Study on Heisenberg-limited Quantum Algorithms for Multiple Observables Estimation [0.19999259391104385]
  We propose two practical variants of adaptive quantum gradient estimation (QGE) algorithm. We provide theoretical guarantee for the estimation precision in terms of the root mean squared error. We show how the estimation error is minimized under the circuit structure that resembles the phase estimation algorithm.
  arXiv  Detail & Related papers  (2025-05-01T17:57:27Z)
• Survey on Algorithms for multi-index models [45.143425167349314]
  We review the literature on algorithms for estimating the index space in a multi-index model.<n>The primary focus is on computationally efficient (polynomial-time) algorithms in Gaussian space, the assumptions under which consistency is guaranteed by these methods, and their sample complexity.
  arXiv  Detail & Related papers  (2025-04-07T18:50:11Z)
• Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information [45.18582668677648]
  We consider the problem of estimating the energy of a quantum state preparation for a given Hamiltonian in Pauli decomposition. We construct an adaptive estimator using the state's actual variance.
  arXiv  Detail & Related papers  (2025-02-03T19:00:01Z)
• Error convergence of quantum linear system solvers [0.0]
  We analyze the performance of the Harrow-Hassidim-Lloyd algorithm (HHL algorithm) for solving linear problems. We prove that the computational error of the variant algorithm does not always converge to zero when the number of qubits is increased.
  arXiv  Detail & Related papers  (2024-10-24T13:41:29Z)
• 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)
• 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)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method. We provide nonasymptotic theoretical guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-04-07T00:11:05Z)
• 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)
• Quantum Algorithms for Prediction Based on Ridge Regression [0.7612218105739107]
  We propose a quantum algorithm based on ridge regression model, which get the optimal fitting parameters. The proposed algorithm has a wide range of application and the proposed algorithm can be used as a subroutine of other quantum algorithms.
  arXiv  Detail & Related papers  (2021-04-27T11:03:52Z)
• Variational Quantum Algorithms for Trace Distance and Fidelity Estimation [7.247285982078057]
  We introduce hybrid quantum-classical algorithms for two distance measures on near-term quantum devices. First, we introduce the Variational Trace Distance Estimation (VTDE) algorithm. Second, we introduce the Variational Fidelity Estimation (VFE) algorithm.
  arXiv  Detail & Related papers  (2020-12-10T15:56:58Z)
• Algorithmic Primitives for Quantum-Assisted Quantum Control [1.52292571922932]
  We discuss two primitive algorithms to evaluate overlaps and transition matrix time series. They are used to construct a variety of quantum-assisted quantum control algorithms implementable on NISQ devices.
  arXiv  Detail & Related papers  (2020-11-27T15:20:29Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
  We give a row sampling algorithm for the quantile loss function with sample complexity nearly linear in the dimensionality of the data. Based upon our row sampling algorithm, we give the fastest known algorithm for quantile regression and a graph sparsification algorithm for balanced directed graphs.
  arXiv  Detail & Related papers  (2020-06-15T13:40:07Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)

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.