Efficient Pauli Channel Estimation with Logarithmic Quantum Memory

In this work, we consider one of the prototypical tasks for characterizing the structure of noise in quantum devices: estimating eigenvalues of an <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline"><a:mi>n</a:mi></a:math>-qubit Pauli noise channel. Prior work [Chen , Phys. Rev. A 105, 032435 (2022)] has proved no-go theorems for this task in the practical regime in which one has a limited amount of quantum memory; i.e., any protocol with <c:math xmlns:c="http://www.w3.org/1998/Math/MathML" display="inline"><c:mo>≤</c:mo><c:mn>0.99</c:mn><c:mi>n</c:mi></c:math> ancilla qubits of quantum memory must make exponentially many measurements, provided that it is . Such protocols can only interact with the channel by repeatedly preparing a state, passing it through the channel, and measuring immediately afterward. Surprisingly, in this work we show that protocols with an extremely small amount of quantum memory achieve an exponential advantage for this task. We give a protocol that can estimate any prescribed set of eigenvalues <e:math xmlns:e="http://www.w3.org/1998/Math/MathML" display="inline"><e:mi>A</e:mi></e:math> of a Pauli channel to error <g:math xmlns:g="http://www.w3.org/1998/Math/MathML" display="inline"><g:mi>ε</g:mi></g:math> using only <i:math xmlns:i="http://www.w3.org/1998/Math/MathML" display="inline"><i:mi>O</i:mi><i:mo stretchy="false">(</i:mo><i:mi>log</i:mi><i:mo></i:mo><i:mi>log</i:mi><i:mo></i:mo><i:mo stretchy="false">(</i:mo><i:mrow><i:mo stretchy="false">|</i:mo></i:mrow><i:mi>A</i:mi><i:mrow><i:mo stretchy="false">|</i:mo></i:mrow><i:mo stretchy="false">)</i:mo><i:mo>/</i:mo><i:msup><i:mi>ε</i:mi><i:mn>2</i:mn></i:msup><i:mo stretchy="false">)</i:mo></i:math> ancilla qubits, <q:math xmlns:q="http://www.w3.org/1998/Math/MathML" display="inline"><q:mrow><q:mrow><q:mrow><q:mover><q:mrow><q:mi>O</q:mi><q:mspace width="0.167em"/></q:mrow><q:mo stretchy="false">~</q:mo></q:mover></q:mrow><q:mspace width="-0.167em"/></q:mrow><q:mrow/></q:mrow><q:mo stretchy="false">(</q:mo><q:msup><q:mi>n</q:mi><q:mn>2</q:mn></q:msup><q:mo>/</q:mo><q:msup><q:mi>ε</q:mi><q:mn>2</q:mn></q:msup><q:mo stretchy="false">)</q:mo></q:math> measurements, and <x:math xmlns:x="http://www.w3.org/1998/Math/MathML" display="inline"><x:mi>O</x:mi><x:mo stretchy="false">(</x:mo><x:msup><x:mi>n</x:mi><x:mn>2</x:mn></x:msup><x:mrow><x:mo stretchy="false">|</x:mo></x:mrow><x:mi>A</x:mi><x:mrow><x:mo stretchy="false">|</x:mo></x:mrow><x:mo>/</x:mo><x:msup><x:mi>ε</x:mi><x:mn>2</x:mn></x:msup><x:mo stretchy="false">)</x:mo></x:math> queries to the Pauli channel. In contrast, we show that any protocol with zero ancilla—even a concatenating one—must make <db:math xmlns:db="http://www.w3.org/1998/Math/MathML" display="inline"><db:mi mathvariant="normal">Ω</db:mi><db:mo stretchy="false">(</db:mo><db:msup><db:mn>2</db:mn><db:mi>n</db:mi></db:msup><db:mo>/</db:mo><db:msup><db:mi>ε</db:mi><db:mn>2</db:mn></db:msup><db:mo stretchy="false">)</db:mo></db:math> measurements. We also prove that the number of queries cannot be improved significantly: with <ib:math xmlns:ib="http://www.w3.org/1998/Math/MathML" display="inline"><ib:mi>k</ib:mi></ib:math> ancilla qubits, <kb:math xmlns:kb="http://www.w3.org/1998/Math/MathML" display="inline"><kb:mi mathvariant="normal">Ω</kb:mi><kb:mo stretchy="false">(</kb:mo><kb:msup><kb:mn>2</kb:mn><kb:mrow><kb:mo stretchy="false">(</kb:mo><kb:mi>n</kb:mi><kb:mo>−</kb:mo><kb:mi>k</kb:mi><kb:mo stretchy="false">)</kb:mo><kb:mo>/</kb:mo><kb:mn>3</kb:mn></kb:mrow></kb:msup><kb:mo stretchy="false">)</kb:mo></kb:math> queries to the channel are necessary to learn all eigenvalues, even for concatenating protocols.