Sabee Grewal, Daniel Liang (Oct 02 2025).
Abstract: We study process tomography of unitary channels whose Pauli spectrum is supported on a small subgroup. Given query access to an unknown unitary channel whose Pauli spectrum is supported on a subgroup of size
2k, our goal is to output a classical description that is
ϵ-close to the unknown unitary in diamond distance. We present an algorithm that achieves this using
O(2k/ϵ) queries, and we prove matching lower bounds, establishing query optimality of our algorithm. When
k=2n, so that the support is the full Pauli group, our result recovers the query-optimal
O(4n/ϵ)-query algorithm of Haah, Kothari, O'Donnell, and Tang [FOCS '23]. Our result has two notable consequences. First, we give a query-optimal
O(4k/ϵ)-query algorithm for learning quantum
k-juntas -- unitary channels that act non-trivially on only
k of the
n qubits -- to accuracy
ϵ in diamond distance. This represents an exponential improvement in both query and time complexity over prior work. Second, we give a computationally efficient algorithm for learning compositions of depth-
O(loglogn) circuits with near-Clifford circuits, where "near-Clifford" means a Clifford circuit augmented with at most
O(logn) non-Clifford single-qubit gates. This unifies prior work, which could handle only constant-depth circuits or near-Clifford circuits, but not their composition.