Optimal Quantum Algorithm for Estimating Fidelity to a Pure State

• URL: http://arxiv.org/abs/2506.23650v1
• Date: Mon, 30 Jun 2025 09:24:03 GMT
• Title: Optimal Quantum Algorithm for Estimating Fidelity to a Pure State
• Authors: Wang Fang, Qisheng Wang,
• Abstract summary: We present an optimal quantum algorithm for fidelity estimation between two quantum states when one of them is pure.<n>To the best of our knowledge, this is the first query-optimal approach to fidelity estimation involving mixed states.
• Score: 3.2951511916931167
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present an optimal quantum algorithm for fidelity estimation between two quantum states when one of them is pure. In particular, the (square root) fidelity of a mixed state to a pure state can be estimated to within additive error $\varepsilon$ by using $\Theta(1/\varepsilon)$ queries to their state-preparation circuits, achieving a quadratic speedup over the folklore $O(1/\varepsilon^2)$. Our approach is technically simple, and can moreover estimate the quantity $\sqrt{\operatorname{tr}(\rho\sigma^2)}$ that is not common in the literature. To the best of our knowledge, this is the first query-optimal approach to fidelity estimation involving mixed states.

Related papers

• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer [7.319050391449301]
  Trace distance and infidelity, as basic measures of the closeness of quantum states, are commonly used in quantum state discrimination, certification, and tomography. We present a quantum algorithm that estimates the trace distance and square root fidelity between pure states to within additive error $varepsilon$, given sample access to their identical copies.
  arXiv  Detail & Related papers  (2024-10-28T16:48:21Z)
• Optimal Trace Distance and Fidelity Estimations for Pure Quantum States [3.1157817010763136]
  In this paper, we develop optimal quantum algorithms that estimate both the trace distance and the (square root) fidelity between pure states to within additive error. At the heart of our construction is an algorithmic tool for quantum square root amplitude estimation, which generalizes the well-known quantum amplitude estimation.
  arXiv  Detail & Related papers  (2024-08-29T15:59:55Z)
• The role of shared randomness in quantum state certification with unentangled measurements [36.19846254657676]
  We study quantum state certification using unentangled quantum measurements. $Theta(d2/varepsilon2)$ copies are necessary and sufficient for state certification. We develop a unified lower bound framework for both fixed and randomized measurements.
  arXiv  Detail & Related papers  (2024-01-17T23:44:52Z)
• Quantum Metropolis-Hastings algorithm with the target distribution calculated by quantum Monte Carlo integration [0.0]
  Quantum algorithms for MCMC have been proposed, yielding the quadratic speedup with respect to the spectral gap $Delta$ compered to classical counterparts. We consider not only state generation but also finding a credible interval for a parameter, a common task in Bayesian inference. In the proposed method for credible interval calculation, the number of queries to the quantum circuit to compute $ell$ scales on $Delta$, the required accuracy $epsilon$ and the standard deviation $sigma$ of $ell$ as $tildeO(sigma/epsilon
  arXiv  Detail & Related papers  (2023-03-10T01:05:16Z)
• Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation [5.746732081406236]
  We develop a phase estimation method with a distinct feature. The total cost of the algorithm satisfies the Heisenberg-limited scaling $widetildemathcalO(epsilon-1)$. Our algorithm may significantly reduce the circuit depth for performing phase estimation tasks on early fault-tolerant quantum computers.
  arXiv  Detail & Related papers  (2022-11-22T03:15:40Z)
• Quantum tomography using state-preparation unitaries [0.22940141855172028]
  We describe algorithms to obtain an approximate classical description of a $d$-dimensional quantum state when given access to a unitary. We show that it takes $widetildeTheta(d/varepsilon)$ applications of the unitary to obtain an $varepsilon$-$ell$-approximation of the state. We give an efficient algorithm for obtaining Schatten $q$-optimal estimates of a rank-$r$ mixed state.
  arXiv  Detail & Related papers  (2022-07-18T17:56:18Z)
• 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)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  We provide the first non-asymptotic, finite-time analysis for double Q-learning. We show that both synchronous and asynchronous double Q-learning are guaranteed to converge to an $epsilon$-accurate neighborhood of the global optimum.
  arXiv  Detail & Related papers  (2020-09-29T18:48:21Z)
• Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
  We devise an efficient quantum differentially private (QDP) Lasso estimator to solve sparse regression tasks. Last, we exhibit that the QDP Lasso attains a near-optimal utility bound $tildeO(N-2/3)$ with privacy guarantees.
  arXiv  Detail & Related papers  (2020-07-23T10:50:42Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.