Quantum Algorithm for Fidelity Estimation

• URL: http://arxiv.org/abs/2103.09076v2
• Date: Thu, 29 Sep 2022 03:44:45 GMT
• Title: Quantum Algorithm for Fidelity Estimation
• Authors: Qisheng Wang, Zhicheng Zhang, Kean Chen, Ji Guan, Wang Fang, Junyi Liu, Mingsheng Ying
• Abstract summary: For two unknown mixed quantum states $rho$ and $sigma$ in an $N$-dimensional space, computing their fidelity $F(rho,sigma)$ is a basic problem. We propose a quantum algorithm that solves this problem in $namepoly(log (N), r, 1/varepsilon)$ time.
• Score: 8.270684567157987
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: For two unknown mixed quantum states $\rho$ and $\sigma$ in an $N$-dimensional Hilbert space, computing their fidelity $F(\rho,\sigma)$ is a basic problem with many important applications in quantum computing and quantum information, for example verification and characterization of the outputs of a quantum computer, and design and analysis of quantum algorithms. In this paper, we propose a quantum algorithm that solves this problem in $\operatorname{poly}(\log (N), r, 1/\varepsilon)$ time, where $r$ is the lower rank of $\rho$ and $\sigma$, and $\varepsilon$ is the desired precision, provided that the purifications of $\rho$ and $\sigma$ are prepared by quantum oracles. This algorithm exhibits an exponential speedup over the best known algorithm (based on quantum state tomography) which has time complexity polynomial in $N$.

Related papers

• On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
  lattice-based cryptography is one of the main candidates of post-quantum cryptography. cryptographic security against quantum attackers is based on lattice problems like the shortest vector problem (SVP) Asymptotic quantum speedups for solving SVP are known and rely on Grover's search.
  arXiv  Detail & Related papers  (2024-10-17T16:54:41Z)
• Resource-efficient algorithm for estimating the trace of quantum state powers [1.5133368155322298]
  Estimating the trace of quantum state powers, $textTr(rhok)$, for $k$ identical quantum states is a fundamental task. We introduce an algorithm that requires only $mathcalO(tilder)$ qubits and $mathcalO(tilder)$ multi-qubit gates. We extend our algorithm to the estimation of $textTr(rhok)$ for arbitrary observables and $textTr(rhok)
  arXiv  Detail & Related papers  (2024-08-01T06:23:52Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Time-Efficient Quantum Entropy Estimator via Samplizer [7.319050391449301]
  Estimating the entropy of a quantum state is a basic problem in quantum information. We introduce a time-efficient quantum approach to estimating the von Neumann entropy $S(rho)$ and R'enyi entropy $S_alpha(rho)$ of an $N$-dimensional quantum state $rho.
  arXiv  Detail & Related papers  (2024-01-18T12:50:20Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
  We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria. This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
  arXiv  Detail & Related papers  (2023-11-17T20:38:38Z)
• Quantum Speedups for Bayesian Network Structure Learning [0.0]
  For networks with $n$ nodes, the fastest known algorithms run in time $O(cn)$ in the worst case, with no improvement in two decades. Inspired by recent advances in quantum computing, we ask whether BNSL admits a quantum speedup. We give two algorithms achieving $c leq 1.817$ and $c leq 1.982$.
  arXiv  Detail & Related papers  (2023-05-31T09:15:28Z)
• Fast Quantum Algorithms for Trace Distance Estimation [8.646488471216262]
  We propose efficient quantum algorithms for estimating the trace distance within additive error $varepsilon$ between mixed quantum states of rank $r$. We show that the decision version of low-rank trace distance estimation is $mathsfBQP$-complete.
  arXiv  Detail & Related papers  (2023-01-17T10:16:14Z)
• Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling [30.53587208999909]
  We give a quantum algorithm for computing an $epsilon$-approximate Nash equilibrium of a zero-sum game in a $m times n$ payoff matrix with bounded entries. Given a standard quantum oracle for accessing the payoff matrix our algorithm runs in time $widetildeO(sqrtm + ncdot epsilon-2.5 + epsilon-3)$ and outputs a classical representation of the $epsilon$-approximate Nash equilibrium.
  arXiv  Detail & Related papers  (2023-01-10T02:56:49Z)
• 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)
• Quantum $k$-nearest neighbors algorithm [0.0]
  We present a quantum analog of classical $k$NN $-$ quantum $k$NN (Q$k$NN) $-$ based on fidelity as the similarity measure. Unlike classical $k$NN and existing quantum $k$NN algorithms, the proposed algorithm can be directly used on quantum data.
  arXiv  Detail & Related papers  (2020-03-20T10:48:57Z)

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.