2023/09/25 by Sitan Chen, Chen, Sitan, Weiyuan Gong +1 · 7 citations
Computer Science · Engineering · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Information Theory (cs.IT) #Low-power high-performance VLSI design #Machine Learning (cs.LG) #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum and electron transport phenomena #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2309.14326
openalex publication_date 2023/09/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Here we revisit one of the prototypical tasks for characterizing the structure of noise in quantum devices: estimating every eigenvalue of an n-qubit Pauli noise channel to error ε. Prior work [14] proved no-go theorems for this task in the practical regime where one has a limited amount of quantum memory, e.g. any protocol with ≤ 0.99n ancilla qubits of quantum memory must make exponentially many measurements, provided it is non-concatenating. Such protocols can only interact with the channel by repeatedly preparing a state, passing it through the channel, and measuring immediately afterward. This left open a natural question: does the lower bound hold even for general protocols, i.e. ones which chain together many queries to the channel, interleaved with arbitrary data-processing channels, before measuring? Surprisingly, in this work we show the opposite: there is a protocol that can estimate the eigenvalues of a Pauli channel to error ε using only O(log n/ε2) ancilla and O(n2/ε2) measurements. In contrast, we show that any protocol with zero ancilla, even a concatenating one, must make Ω(2n/ε2) measurements, which is tight. Our results imply, to our knowledge, the first quantum learning task where logarithmically many qubits of quantum memory suffice for an exponential statistical advantage. Our protocol can be naturally extended to a protocol that learns the eigenvalues of Pauli terms within any subset A of a Pauli channel with O(loglog(|A|)/ε2) ancilla and O(n2/ε2) measurements.