Quantum Threshold is Powerful

Understand

In 2005, H{\o}yer and \v{S}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 polynomial-size constant-depth quantum circuits with Threshold gates that compute Fanout to high fidelity.