Charles R. Chen

In their seminal work on quantum circuit complexity, Moore and Nilsson conjectured that unitaries of a deceptively simple form—controlled-unitary "staircases"—require circuits of minimum depth Ω(n). If true, this lower bound would answer a quantum-native analogue of the famous NC ≠ P conjecture. 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 parallelization is exact, ancilla-free, and can be computed in poly(n) time. We also parallelize Moore–Nilsson circuits to the best-possible depth of O(√n) in circuits restricted to 2D connectivity. The main ingredient in these proofs is a blockwise precomputation technique that is in some sense a quantum analogue of the method introduced by Arlazarov, Dinic, Kronrod, and Faradzev in classical dynamic programming, sometimes called the "Four-Russians speedup." We also show that this quantum precomputation technique can be applied to more-general classes of circuits. As examples, we construct both exact and approximate parallelizations which give polynomial depth reductions for cascades of controlled log(n)-qubit unitaries.