Single-copy stabilizer testing

Abstract

We consider the problem of testing whether an unknown $n$-qubit quantum state $|\psi ⟩$ is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using $O(n)$ copies, and conversely prove that $\Omega (\sqrt{n})$ copies are required for any algorithm. The main observation behind our algorithm is that when repeatedly measuring in a randomly chosen stabilizer basis, stabilizer states are the most likely among the set of all pure states to exhibit linear dependencies in measurement outcomes. Our algorithm is designed to probe deviations from this extremal behavior. For the lower bound, we first reduce stabilizer testing to the task of distinguishing random stabilizer states from the maximally mixed state. We then argue that, without loss of generality, it is sufficient to consider measurement strategies that a) lie in the commutant of the tensor action of the Clifford group and b) satisfy a Positive Partial Transpose (PPT) condition. By leveraging these constraints, together with novel results on the partial transposes of the generators of the Clifford commutant, we derive the lower bound on the sample complexity.

arXiv comment38 pages, no figures. Comments welcome

References in corpus (23)

• Predicting Many Properties of a Quantum System from Very Few Measurements
• Quantum advantage in learning from experiments
• Everything You Always Wanted to Know About LOCC (But Were Afraid to Ask)
• Hudson's Theorem for finite-dimensional quantum systems
• Stabilizer Rényi entropy
• Simulation of quantum circuits by low-rank stabilizer decompositions
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Scalable measures of magic resource for quantum computers
• Measuring magic on a quantum processor
• 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
• Efficient quantum algorithms for stabilizer entropies
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Learning t-doped stabilizer states
• Learning quantum circuits of some $T$ gates
• Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
• Improved Stabilizer Estimation via Bell Difference Sampling
• Triply efficient shadow tomography
• Efficient learning of $t$-doped stabilizer states with single-copy measurements
• Approximate orthogonality of permutation operators, with application to quantum information
• Sample-Optimal Quantum Process Tomography with Non-Adaptive Incoherent Measurements
• Tolerant Testing of Stabilizer States with Mixed State Inputs

Cited by in corpus (3)

• Efficient witnessing and testing of magic in mixed quantum states
• Operational interpretation of the Stabilizer Entropy
• The abelian state hidden subgroup problem: Learning stabilizer groups and beyond