Fast Quantum Algorithms for Trace Distance Estimation

• URL: http://arxiv.org/abs/2301.06783v3
• Date: Mon, 13 Nov 2023 13:47:33 GMT
• Title: Fast Quantum Algorithms for Trace Distance Estimation
• Authors: Qisheng Wang, Zhicheng Zhang
• Abstract summary: 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.
• Score: 8.646488471216262
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In quantum information, trace distance is a basic metric of distinguishability between quantum states. However, there is no known efficient approach to estimate the value of trace distance in general. In this paper, we propose efficient quantum algorithms for estimating the trace distance within additive error $\varepsilon$ between mixed quantum states of rank $r$. Specifically, we first provide a quantum algorithm using $r \cdot \widetilde O(1/\varepsilon^2)$ queries to the quantum circuits that prepare the purifications of quantum states. Then, we modify this quantum algorithm to obtain another algorithm using $\widetilde O(r^2/\varepsilon^5)$ samples of quantum states, which can be applied to quantum state certification. These algorithms have query/sample complexities that are independent of the dimension $N$ of quantum states, and their time complexities only incur an extra $O(\log (N))$ factor. In addition, we show that the decision version of low-rank trace distance estimation is $\mathsf{BQP}$-complete.

Related papers

• 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)
• Exploring quantum weight enumerators from the $n$-qubit parallelized SWAP test [19.183393329155567]
  We build the connection between quantum weight enumerators and the $n$-qubit parallelized SWAP test. We find that each shadow enumerator corresponds precisely to a probability in the $n$-qubit parallelized SWAP test. For applications, we employ the $n$-qubit parallelized SWAP test to determine the distances of quantum error-correcting codes.
  arXiv  Detail & Related papers  (2024-06-26T12:06:40Z)
• 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)
• A generalized framework for quantum state discrimination, hybrid algorithms, and the quantum change point problem [3.4683494246563606]
  We present a hybrid quantum-classical algorithm based on semidefinite programming to calculate the maximum reward when the states are pure and have efficient circuits. We give now-possible algorithms for the quantum change point identification problem which asks, given a sequence of quantum states, determine the time steps when the quantum states changed.
  arXiv  Detail & Related papers  (2023-12-07T03:42:40Z)
• Quantum State Tomography for Matrix Product Density Operators [28.799576051288888]
  Reconstruction of quantum states from experimental measurements is crucial for the verification and benchmarking of quantum devices. Many physical quantum states, such as states generated by noisy, intermediate-scale quantum computers, are usually structured. We establish theoretical guarantees for the stable recovery of MPOs using tools from compressive sensing and the theory of empirical processes.
  arXiv  Detail & Related papers  (2023-06-15T18:23:55Z)
• Quantum Distance Calculation for $\epsilon$-Graph Construction [0.0]
  We investigate the potential for quantum advantage in the case of quantum distance calculation for computing $epsilon$-graphs. We show that, relying on existing quantum multi-state SWAP test based algorithms, the query complexity for correctly identifying two points are not $epsilon$-neighbours is at least O(n3 / ln n)
  arXiv  Detail & Related papers  (2023-06-07T09:43:28Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• New Quantum Algorithms for Computing Quantum Entropies and Distances [9.242097678969161]
  We propose a series of quantum algorithms for computing a wide range of quantum entropies and distances. The proposed algorithms significantly outperform the prior best (and even quantum) ones in the low-rank case.
  arXiv  Detail & Related papers  (2022-03-25T09:15:45Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• Quantum Algorithm for Fidelity Estimation [8.270684567157987]
  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.
  arXiv  Detail & Related papers  (2021-03-16T13:57:01Z)
• 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.