Parallelization is a significant 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 (SIAM J. Comput. ’01): 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 talk we’ll develop a quantum precomputation technique and use it to 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. We’ll also give polynomial depth improvements for certain generalizations of Moore–Nilsson circuits and discuss open problems in the area.
