Joseph Slote

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.

A recent line of work has shown the unconditional advantage of constant-depth quantum computation, or QNC0, over NC0, AC0, and related models of classical computation. Problems exhibiting this advantage include search and sampling tasks related to the parity function, and it is natural to ask whether QNC0 can be used to help compute parity itself. Namely, we study AC0◦QNC0—a hybrid circuit model where AC0 operates on measurement outcomes of a QNC0 circuit—and we ask whether Par ∈ AC0◦QNC0. We believe the answer is negative. In fact, we conjecture AC0◦QNC0 cannot even achieve Ω(1) correlation with parity. As evidence for this conjecture, we prove the following: • When the QNC0 circuit is ancilla-free, we show this model can achieve only negligible correlation with parity, even when AC0 is replaced with any function having LMN-like decay in its Fourier spectrum. • For the general (non-ancilla-free) case, we show via a connection to nonlocal games that the conjecture holds for any class of postprocessing functions that has approximate degree o(n) and is closed under restrictions. Moreover, this is true even when the QNC0 circuit is given arbitrary quantum advice. By known results, this confirms the conjecture for linear-size AC0 circuits. • Another approach to proving the conjecture is to show a switching lemma for AC0◦QNC0. Towards this goal, we study the effect of quantum preprocessing on the decision tree complexity of Boolean functions. We find that from the point of view of a decision tree, nonlocal channels are no better than randomness: a Boolean function f precomposed with an n-party nonlocal channel is together equal to a randomized decision tree with depth no greater than DTdepth[f]. Taken together, our results suggest that while QNC0 is surprisingly powerful for search and sampling, that power is “locked away” in the global correlations of its output, inaccessible to simple classical computation for solving decision problems.

Analysis on the Boolean hypercube −1,1^n, particularly Fourier analysis, has played a crucial role in many areas of mathematics and computer science, including learning algorithms. In view of the success and importance of quantum algorithms, it is natural to transfer classical learning results to the quantum realm. In this contribution, we extend the recent progress on learning low-degree functions and quantum operators to the setting of general qudit systems, as well as develop novel Fourier-analytic tools for studying (generalized) Pauli decompositions of Hermitian operators. These tools also allow us to deduce new results in quantum Boolean analysis and approximate theory, such as the junta-type theorem and dimension-free discrete Remez-type inequalities.