Quantum Precomputation: Parallelizing Cascade Circuits and the Moore–Nilsson Conjecture Is False
Adam Bene Watts, Charles R. Chen, J. William Helton, Joseph Slote · 2026
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: unitaries of a deceptively simple form—controlled-unitary “staircases”—require circuits of minimum depth Ω(n). If true, this lower bound would represent a significant break from classical parallelism and prove a quantum-native analogue of the famous NC≠ P conjecture.