Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness
This work addresses the challenge of quantum circuit learnability for near-term quantum computing, with implications for quantum cryptography and algorithm design, though it is incremental in building on existing learning frameworks.
The authors tackled the problem of learning shallow quantum circuits in the near term, showing that constant-depth circuits can be learned with only linear overhead in query complexity, and proved that pseudorandom unitaries cannot be constructed with constant-depth circuits by developing an efficient distinguisher.
In this work, we study the learnability of quantum circuits in the near term. We demonstrate the natural robustness of quantum statistical queries for learning quantum processes, motivating their use as a theoretical tool for near-term learning problems. We adapt a learning algorithm for constant-depth quantum circuits to the quantum statistical query setting, and show that such circuits can be learned in our setting with only a linear overhead in the query complexity. We prove average-case quantum statistical query lower bounds for learning, within diamond distance, random quantum circuits with depth at least logarithmic and at most linear in the system size. Finally, we prove that pseudorandom unitaries (PRUs) cannot be constructed using circuits of constant depth by constructing an efficient distinguisher using existing learning algorithms. To show the correctness of our distinguisher, we prove a new variation of the quantum no free lunch theorem.