We prove that adaptive strategies offer no advantage over non-adaptive ones for learning and testing Pauli channels using entangled inputs. This key observation allows us to characterize the query complexity for several fundamental tasks by translating optimal classical estimation algorithms into the quantum setting. First, we determine the tight query complexity for learning a Pauli channel under the general ℓp norm, providing results that improve upon or match the best-known bounds for the ℓ1,ℓ2, and ℓ∞ distances. Second, we resolve the complexity of testing whether a Pauli channel is a white noise source. Finally, we show that the optimal query complexities for estimating the Shannon entropy and support size of the channel's error distribution, and for estimating the diamond distance between two Pauli channels, are all Θ(4nnϵ2) .
Quantum entanglement is a crucial resource for learning properties from nature, but a precise characterization of its advantage can be challenging. In this Letter, we consider learning algorithms without entanglement to be those that only utilize states, measurements, and operations that are separable between the main system of interest and an ancillary system. Interestingly, we show that these algorithms are equivalent to those that apply quantum circuits on the main system interleaved with mid-circuit measurements and classical feedforward. Within this setting, we prove a tight lower bound for Pauli channel learning without entanglement that closes the gap between the best-known upper and lower bound. In particular, we show that Θ(2^{n}ϵ^{-2}) rounds of measurements are required to estimate each eigenvalue of an n-qubit Pauli channel to ϵ error with high probability when learning without entanglement. In contrast, a learning algorithm with entanglement only needs Θ(ϵ^{-2}) copies of the Pauli channel. The tight lower bound strengthens the foundation for an experimental demonstration of entanglement-enhanced advantages for Pauli noise characterization.
Understanding the noise affecting a quantum device is of fundamental importance for scaling quantum technologies. A particularly important class of noise models is that of Pauli channels, as randomized compiling techniques can effectively bring any quantum channel to this form and are significantly more structured than general quantum channels. In this paper, we show fundamental lower bounds on the sample complexity for learning Pauli channels in diamond norm. We consider strategies that may not use auxiliary systems entangled with the input to the unknown channel and have to perform a measurement before reusing the channel. For non-adaptive algorithms, we show a lower bound of Ω(23nε−2) to learn an n-qubit Pauli channel. In particular, this shows that the recently introduced learning procedure by [1] is essentially optimal. In the adaptive setting, we show a lower bound of Ω(22.5nε−2) for ε = O(2−n), and a lower bound of Ω(22nε−2) for any ε > 0. This last lower bound holds even in a stronger model where in each step, before performing the measurement, the unknown channel may be used arbitrarily many times sequentially interspersed with unital operations.
We study the problem of learning nearly
(s,ε)-sparse unitaries, meaning that the Pauli spectrum is concentrated on at most
s components with at most
ε residual mass in Pauli
ℓ1-norm. This class generalizes well-studied families, including sparse unitaries, quantum
k-juntas,
2k-Pauli dimensional channels, and compositions of depth
O(loglogn) circuits with near-Clifford circuits.
Given query access to an unknown nearly sparse unitary
U, our goal is to efficiently (both in time and query complexity) construct a quantum channel that is close in diamond distance to
U. We design a learning algorithm achieving this guarantee using
O~(s6/ε4) forward queries to
U, and running time polynomial in relevant parameters.
A key contribution is an efficient quantum algorithm that, given query access to an arbitrary unknown unitary
U, estimates all Pauli coefficients (up to a shared global phase) whose magnitude exceeds a given threshold
θ, extending existing sparse recovery techniques to general unitaries.
We also study the broader class of unitaries with bounded Pauli
ℓ1-norm. For that class, we prove an exponential query lower bound
Ω(2n/2). We introduce a more relaxed accuracy metric which is the diamond distance restricted to a set of input states. Then, we show that, under this metric, unitaries with Pauli
ℓ1-norm uniformly bounded by
L1 are learnable with
O~(L18/ε16).
We consider the problems of testing and learning an unknown n -qubit quantum Hamiltonian H =∑ x λ x σ x expressed in its Pauli basis, from queries to its evolution operator e − iHt under the normalized Frobenius norm. To this end, we prove the following results (with and without quantum memory) for Hamiltonians whose Pauli spectrum involves only k -local terms or has sparsity at most s : (1) Local Hamiltonians : We give a tolerant testing protocol to decide if a Hamiltonian is ε 1 -close to k -local or ε 2 -far from k -local, with O (1/(ε 2 −ε 1 ) 4 ) queries, thereby solving two open questions posed in a recent work by Bluhm, Caro and Oufkir [BCO’24]. For learning a k -local Hamiltonian up to error ε, we give a protocol with query complexity and total time evolution exp( O ( k 2 + k log(1/ε))). Our algorithm leverages the non-commutative Bohnenblust-Hille inequality in order to get a complexity independent of n . (2) Sparse Hamiltonians : We give a protocol for testing whether a Hamiltonian is ε 1 -close to being s -sparse or ε 2 -far from being s -sparse, with O ( s 6 /(ε 2 2 −ε 1 2 ) 6 ) queries. For learning up to error ε, we show that O ( s 4 /ε 8 ) queries suffices. (3) Learning without quantum memory : The learning results stated above have no dependence on the system size n , but require n -qubit quantum memory. We give subroutines that allow us to reproduce all the above learning results without quantum memory; increasing the query complexity by a (log n )-factor in the local case and an n -factor in the sparse case. (4) Testing without quantum memory : We give a new subroutine called Pauli hashing , which allows one to tolerantly test s -sparse Hamiltonians using Õ( s 14 /(ε 2 2 −ε 1 2 ) 18 ) query complexity. A key ingredient is showing that s -sparse Pauli channels can be tested in a tolerant fashion as being ε 1 -close to being s -sparse or ε 2 -far under the diamond norm, using Õ( s 2 /(ε 2 −ε 1 ) 6 ) queries via Pauli hashing. In order to prove these results, we prove new structural theorems for local Hamiltonians, sparse Pauli channels and sparse Hamiltonians. We complement our learning algorithms with lower bounds that are polynomially weaker. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms on which the Pauli spectrum is supported on, i.e., we do not require prior knowledge about the support of the Hamiltonian terms.
Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be
Θ(din3dout3/ε2), where
din and
dout are the channel input and output dimensions, respectively, and
ε is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires
Ω(din3dout3/ε2) queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound
O(din3dout3/ε2). Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case
din=1. By contrast, coherent protocols with quantum memory achieve query complexity
Θ(din2dout2/ε2). Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.
We show that entangled measurements provide an exponential advantage in sample complexity for Pauli channel estimation, which is both a fundamental problem and a practically important subroutine for benchmarking near-term quantum devices. The specific task we consider is to simultaneously learn all the eigenvalues of an
n-qubit Pauli channel to $\ifmmode\pm\else\textpm\fi{}\ensuremath{\varepsilon}$ precision. We give an estimation protocol with an
n-qubit ancilla that succeeds with high probability using only $O(n/{\ensuremath{\varepsilon}}^{2})$ copies of the Pauli channel, while proving that any ancilla-free protocol (possibly with adaptive control and channel concatenation) would need at least $\mathrm{\ensuremath{\Omega}}({2}^{n/3})$ rounds of measurement. We further study the advantages provided by a small number of ancillas. For the case that a
k-qubit ancilla ($k\ensuremath{\le}n$) is available, we obtain a sample complexity lower bound of $\mathrm{\ensuremath{\Omega}}({2}^{(n\ensuremath{-}k)/3})$ for any nonconcatenating protocol, and a stronger lower bound of $\mathrm{\ensuremath{\Omega}}(n{2}^{n\ensuremath{-}k})$ for any nonadaptive, nonconcatenating protocol, which is shown to be tight. We also show how to apply the ancilla-assisted estimation protocol to a practical quantum benchmarking task in a noise-resilient and sample-efficient manner, given reasonable noise assumptions. Our results provide a practically interesting example for quantum advantages in learning and also bring insights for quantum benchmarking.