Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates II: Single-Copy Measurements

• URL: http://arxiv.org/abs/2308.07175v2
• Date: Thu, 4 Apr 2024 21:27:11 GMT
• Title: Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates II: Single-Copy Measurements
• Authors: Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang,
• Abstract summary: Recent work has shown that $n$-qubit quantum states output by circuits with at most $t$ single-qubit non-Clifford gates can be learned to trace distance $epsilon$ using $mathsfpoly(n,2t,1/epsilon)$ time and samples. In this work, we give a similarly efficient algorithm that learns the same class of states using only single-copy measurements.
• Score: 0.43123403062068827
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent work has shown that $n$-qubit quantum states output by circuits with at most $t$ single-qubit non-Clifford gates can be learned to trace distance $\epsilon$ using $\mathsf{poly}(n,2^t,1/\epsilon)$ time and samples. All prior algorithms achieving this runtime use entangled measurements across two copies of the input state. In this work, we give a similarly efficient algorithm that learns the same class of states using only single-copy measurements.

Related papers

• 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)
• 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)
• Efficient learning of quantum states prepared with few fermionic non-Gaussian gates [0.0]
  We present an efficient algorithm for learning states on $n$ fermion modes prepared by any number of Gaussian gates. Our work sheds light on the structure of states prepared with few non-Gaussian gates and offers an improved upper bound on their circuit complexity.
  arXiv  Detail & Related papers  (2024-02-28T19:18:27Z)
• Efficient learning of $t$-doped stabilizer states with single-copy measurements [7.5275459858139175]
  We introduce an efficient quantum algorithm that employs only nonadaptive single-copy measurement to learn states produced by Clifford circuits with a maximum of $O(log n)$ non-Clifford gates.
  arXiv  Detail & Related papers  (2023-08-14T09:01:47Z)
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates [0.43123403062068827]
  We give a pair of algorithms that efficiently learn a quantum state prepared by Clifford gates and $O(log n)$ non-Clifford gates. Specifically, for an $n$-qubit state $|psirangle$ prepared with at most $t$ non-Clifford gates, our algorithms use $mathsfpoly(n,2t,1/varepsilon)$ time and copies of $|psirangle$ to learn $|psirangle$ to trace distance at most gates.
  arXiv  Detail & Related papers  (2023-05-22T18:49:52Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• 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)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  We learn the set of $epsilon$-optimal goal-conditioned policies attaining all states that are incrementally reachable within $L$ steps. DisCo is the first algorithm that can return an $epsilon/c_min$-optimal policy for any cost-sensitive shortest-path problem.
  arXiv  Detail & Related papers  (2020-12-29T14:06:09Z)
• 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.