Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
Abstract
We prove that any n -qubit unitary can be implemented (i) approximately in time O ~ ( 2 n / 2 ) with query access to an appropriate classical oracle, and also (ii) exactly by a circuit of depth O ~ ( 2 n / 2 ) with one- and two-qubit gates and 2 O ( n ) ancillae. The proofs involve similar reductions to Grover search. The proof of (ii) also involves a linear-depth construction of arbitrary quantum states using one- and two-qubit gates (in fact, this can be improved to constant depth with the addition of fanout and generalized Toffoli gates) which may be of independent interest. We also prove a matching Ω ( 2 n / 2 ) lower bound for (i) and (ii) for a certain class of implementations.
Fields of Study & Subjects
Quantum Computing Algorithms and Architecture
Quantum Information and Cryptography
Computability
Logic
AI Algorithms
Publication details
- Journal / source
- Quantum
- Publisher
- Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften
- Volume
- 10
- Pages
- 2144–2144
- Publication date
- 30 June 2026
- Language
- EN