In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries U such that no quantum polynomial-time oracle algorithm A^f can implement U, even approximately, if it only makes one (quantum) query to f. Our approach also has implications for quantum cryptography: we prove (relative to a random oracle O) the existence of quantum cryptographic primitives that remain secure against all one-query adversaries A^f. Since such one-query algorithms can decide any language, solve any classical search problem, and even prepare any quantum state, this result suggests that implementing random unitaries and breaking quantum cryptography may be harder than all of these tasks.
No background in quantum computing will be assumed.
This is a joint work with Alex Lombardi and John Wright. arXiv:
https://arxiv.org/pdf/2310.08870.pdf