Efficient learning of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>t</mml:mi></mml:math>-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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>log</mml:mi><mml:mo>&amp;#x2061;</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mo>&amp;#x2061;</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> non-Clifford gates, filling a gap between the previous positive and negative results.