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: 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.