Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates

Abstract

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 $|\psi ⟩$ prepared with at most $t$ non-Clifford gates, our algorithms use $\mathsf{poly}(n,2^t,1/\epsilon )$ time and copies of $|\psi ⟩$ to learn $|\psi ⟩$ to trace distance at most $\epsilon$. The first algorithm for this task is more efficient, but requires entangled measurements across two copies of $|\psi ⟩$. The second algorithm uses only single-copy measurements at the cost of polynomial factors in runtime and sample complexity. Our algorithms more generally learn any state with sufficiently large stabilizer dimension, where a quantum state has stabilizer dimension $k$ if it is stabilized by an abelian group of $2^k$ Pauli operators. We also develop an efficient property testing algorithm for stabilizer dimension, which may be of independent interest.

54 pages. v4 to be published in Quantum journal. Merged v3 with arXiv:2308.07175. This version now subsumes arXiv:2308.07175

References in corpus (30)

• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Improved Simulation of Stabilizer Circuits
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Efficient quantum state tomography
• Synthesis of Quantum Logic Circuits
• Quantum advantage in learning from experiments
• 10-qubit entanglement and parallel logic operations with a superconducting circuit
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Information-theoretic bounds on quantum advantage in machine learning
• Quantum Tomography
• Sample-optimal tomography of quantum states
• Optimal state estimation for d-dimensional quantum systems
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Hadamard-free circuits expose the structure of the Clifford group
• How to efficiently select an arbitrary Clifford group element
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Improved upper bounds on the stabilizer rank of magic states
• Learning t-doped stabilizer states
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Learning quantum circuits of some $T$ gates
• A single $T$-gate makes distribution learning hard
• Bell sampling from quantum circuits
• Improved Stabilizer Estimation via Bell Difference Sampling
• Doped stabilizer states in many-body physics and where to find them
• Efficient learning of $t$-doped stabilizer states with single-copy measurements
• Fast and robust quantum state tomography from few basis measurements
• The Parameterized Complexity of Quantum Verification

Cited by in corpus (6)

• Designs from magic-augmented Clifford circuits
• Non-Clifford Cost of Random Unitaries
• Artificial intelligence for representing and characterizing quantum systems
• The abelian state hidden subgroup problem: Learning stabilizer groups and beyond
• Pseudoentanglement Ain't Cheap
• Agnostic Tomography of Stabilizer Product States