Efficient Learning of Structured Quantum Circuits via Pauli Dimensionality and Sparsity
This work addresses the challenge of quantum circuit learning for researchers in quantum computing, offering incremental improvements by unifying and generalizing prior methods to more expressive circuit classes.
The paper tackles the problem of efficiently learning unknown n-qubit unitary channels by introducing a framework that leverages low-complexity Pauli operators under conjugation, resulting in polynomial-time algorithms for various circuit classes like O(log log n)-depth circuits and quantum O(log n)-juntas, with query complexities such as O(s^2/ε^2) for sparse Pauli spectra.
We study the problem of efficiently learning an unknown $n$-qubit unitary channel in diamond distance given query access. We present a general framework showing that if Pauli operators remain low-complexity under conjugation by a unitary, then the unitary can be learned efficiently. This framework yields polynomial-time algorithms for a wide range of circuit classes, including $O(\log \log n)$-depth circuits, quantum $O(\log n)$-juntas, near-Clifford circuits, the Clifford hierarchy, fermionic matchgate circuits, and certain compositions thereof. Our results unify and generalize prior work, and yield efficient learning algorithms for more expressive circuit classes than were previously known. Our framework is powered by new learning algorithms for unitaries whose Pauli spectrum is either supported on a small subgroup or is sparse. If the Pauli spectrum is supported on a subgroup of size $2^k$, we give an $\widetilde{O}(2^k/ε)$-query algorithm and a nearly matching $Ω(2^k/ε)$ lower bound. For $k = 2n$, we recover the optimal $O(4^n/ε)$-query algorithm of Haah, Kothari, O'Donnell, and Tang [FOCS '23]. If the Pauli spectrum is supported on $s$ Pauli operators, we give an $O(s^2/ε^2)$-query algorithm and an $Ω(s/ε)$ lower bound.