Posted

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 2k2^k, our goal is to output a classical description that is ϵ\epsilon-close to the unknown unitary in diamond distance. We present an algorithm that achieves this using O(2k/ϵ)O(2^k/\epsilon) queries, and we prove matching lower bounds, establishing query optimality of our algorithm. When k=2nk = 2n, so that the support is the full Pauli group, our result recovers the query-optimal O(4n/ϵ)O(4^n/\epsilon)-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/ϵ)O(4^k/\epsilon)-query algorithm for learning quantum kk-juntas -- unitary channels that act non-trivially on only kk of the nn qubits -- to accuracy ϵ\epsilon 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)O(\log \log n) circuits with near-Clifford circuits, where "near-Clifford" means a Clifford circuit augmented with at most O(logn)O(\log n) non-Clifford single-qubit gates. This unifies prior work, which could handle only constant-depth circuits or near-Clifford circuits, but not their composition.

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!