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
- 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) - How to simulate quantum measurement without computing marginals [3.222802562733787]
We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis.
Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
arXiv Detail & Related papers (2021-12-15T21:44:05Z) - 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) - Preparation of excited states for nuclear dynamics on a quantum computer [117.44028458220427]
We study two different methods to prepare excited states on a quantum computer.
We benchmark these techniques on emulated and real quantum devices.
These findings show that quantum techniques designed to achieve good scaling on fault tolerant devices might also provide practical benefits on devices with limited connectivity and gate fidelity.
arXiv Detail & Related papers (2020-09-28T17:21:25Z) - 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.