pipette
ESEspañol

All Unitaries Have Constant Depth Quantum Circuits

Barak Nehoran, Henry Yuen

PreprintClaims a big step

In the authors' words

It is well-known that every -qubit unitary can be implemented by a -depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is necessary for general unitaries, even when allowing for unlimited number of ancilla qubits. We show, perhaps surprisingly, that all unitaries can be approximated to operator norm by a circuit of one- and two-qubit gates of depth with ancilla qubits. In other words, every -qubit unitary can be parallelized to polynomial depth. Moreover, if we allow unbounded fan-out gates, these circuits can be reduced further 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.

Main resultLimitation the authors admit

Appeared: Thursday, October 1. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 35 pages