Jackson Morris, University of California, San Diego gave an online talk on Quantum Threshold is Powerful on 23 July. Here is the summary of the talk as explained by Jackson Morris :
In 2005, Høyer and Špalek showed that constant-depth quantum circuits augmented with multi-qubit Fanout gates are quite powerful, able to compute a wide variety of Boolean functions as well as the quantum Fourier transform. They also asked what other multi-qubit gates could rival Fanout in terms of computational power, and suggested that the quantum Threshold gate might be one such candidate. Threshold is the gate that indicates if the Hamming weight of a classical basis state input is greater than some target value.

We prove that Threshold is indeed powerful—there are polynomialsize constant-depth quantum circuits with Threshold gates that compute Fanout to high fidelity. Our proof is a generalization of a proof by Rosenthal that exponential-size constant-depth circuits with generalized Toffoli gates can compute Fanout. Our construction reveals that other quantum gates able to “weakly approximate” Parity can also be used as substitutes for Fanout.

 Jackson Morris is a second year Ph.D student in the theory group at UCSD advised by Daniel Grier. Previously, he spent two years as a software engineer at Google in the Bay Area. Before that he was an undergraduate in math at UCLA. His research interests are at the intersection of complexity theory and quantum computing.

July 2025