J. William Helton

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.

Abstract We consider 3XOR games with perfect commuting operator strategies. Given any 3XOR game, we show existence of a perfect commuting operator strategy for the game can be decided in polynomial time. Previously this problem was not known to be decidable. Our proof leads to a construction, showing a 3XOR game has a perfect commuting operator strategy iff it has a perfect tensor product strategy using a 3 qubit (8 dimensional) GHZ state. This shows that for perfect 3XOR games the advantage of a quantum strategy over a classical strategy (defined by the quantum-classical bias ratio) is bounded. This is in contrast to the general 3XOR case where the optimal quantum strategies can require high dimensional states and there is no bound on the quantum advantage. To prove these results, we first show equivalence between deciding the value of an XOR game and solving an instance of the subgroup membership problem on a class of right angled Coxeter groups. We then show, in a proof that consumes most of this paper, that the instances of this problem corresponding to 3XOR games can be solved in polynomial time.