Quantum Precomputation: Parallelizing Cascade Circuits and the Moore-Nilsson Conjecture Is False

Parallelization is a major challenge in quantum algorithms due to physical constraints like no-cloning. This is vividly illustrated by the conjecture of Moore and Nilsson from their seminal work on quantum circuit complexity [MN01, announced 1998]: unitaries of a deceptively simple form-controlled-unitary "staircases"-require circuits of minimum depth Ω(n). If true, this lower bound would represent a major break from classical parallelism and prove a quantum-native analogue of the famous NC ̸ = P conjecture.

In this work we settle the Moore-Nilsson conjecture in the negative by compressing all circuits in the class to depth O(log n), which is the best possible. The parallelizations are exact, ancilla-free, and can be computed in poly(n) time. We also consider circuits restricted to 2D connectivity, for which we derive compressions of optimal depth O( √ n). More generally, we make progress on the project of quantum parallelization by introducing a quantum blockwise precomputation technique somewhat analogous to the method of Arlazarov, Dinič, Kronrod, and Faradžev [Arl+70] in classical dynamic programming, often called the "Four-Russians method." We apply this technique to moregeneral "cascade" circuits as well, obtaining for example polynomial depth reductions for staircases of controlled log(n)-qubit unitaries.

Warning. Due to limitations of arXiv and the Tik Z externalize package, your PDF viewer may not correctly render transparencies in circuit diagrams below. A patched document is available at joeslote.com/documents/precomputation.pdf.