Efficient learning of $t$-doped stabilizer states with single-copy measurements

Abstract

One of the primary objectives in the field of quantum state learning is to develop algorithms that are time-efficient for learning states generated from quantum circuits. Earlier investigations have demonstrated time-efficient algorithms for states generated from Clifford circuits with at most $\log (n)$ non-Clifford gates. However, these algorithms necessitate multi-copy measurements, posing implementation challenges in the near term due to the requisite quantum memory. On the contrary, using solely single-qubit measurements in the computational basis is insufficient in learning even the output distribution of a Clifford circuit with one additional $T$ gate under reasonable post-quantum cryptographic assumptions. In this work, 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, filling a gap between the previous positive and negative results.

8 pages

References in corpus (6)

• Coding Theorem and Strong Converse for Quantum Channels
• Quantum Process Tomography: Resource Analysis of Different Strategies
• Hadamard-free circuits expose the structure of the Clifford group
• Learning quantum circuits of some $T$ gates
• A single $T$-gate makes distribution learning hard
• Fast and robust quantum state tomography from few basis measurements

Cited by in corpus (13)

• Magic-induced computational separation in entanglement theory
• Doped stabilizer states in many-body physics and where to find them
• Learning quantum states of continuous variable systems
• Efficient distributed inner product estimation via Pauli sampling
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• Learning topological states from randomized measurements using variational tensor network tomography
• Single-copy stabilizer testing
• Highly-entangled, highly-doped states that are efficiently cross-device verifiable
• Anticoncentration in Clifford Circuits and Beyond: From Random Tensor Networks to Pseudo-Magic States
• Pseudoentanglement Ain't Cheap
• The abelian state hidden subgroup problem: Learning stabilizer groups and beyond
• Uncertainty-disturbance relations and applications