All Unitaries Have Constant Depth Quantum Circuits
Barak Nehoran | Columbia
It is well-known that every n-qubit unitary can be implemented by a 2^O(n)-depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is *necessary* for general unitaries, even when allowing an unlimited number of ancilla qubits. Here we show, perhaps surprisingly, that all unitaries can be implemented exactly by a circuit of one- and two-qubit gates of depth 𝗉𝗈𝗅𝗒(n) with 2^O(n) ancilla qubits. In other words, every n-qubit unitary can be parallelized to polynomial depth. In fact, our depth bound is *linear* in n, which is the best possible, and an exponential improvement on the previous best bound of 2^n/2 due to Rosenthal [TQC 2022, Quantum 2026]. Moreover, if we allow unbounded fan-out gates, these circuits can be further reduced to *constant* depth. Our construction takes advantage of a novel relationship connecting the unitary synthesis problem of Aaronson and Kuperberg to locally-decodable codes and private information retrieval from complexity theory and cryptography, and has a natural interpretation in bosonic quantum computation.
Location
- QNC 1201
- Online on Zoom
-
Meeting ID: 912 8146 6256
Passcode: 494237
-
Add event to calendar
