3 papers
quant-ph2026
All Unitaries Have Constant Depth Quantum Circuits
Barak Nehoran, Henry Yuen, Joseph Slote
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…
quant-ph2026
A Separation Between Types of Quantum Oracle Separations
Scott Aaronson, Adam Bouland, Jordan Docter +1
Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of cer…
quant-ph2026
Distributional Variants of the Aaronson-Ambainis Conjecture
Uma Girish, Kunal Mittal, Barak Nehoran +1
A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query…