Shallow Quantum Circuits: Unconditional Separations Between Quantum and Classical Computing

Watch an invited conference talk from TQC 2023 exploring the computational power differences between constant depth quantum and classical circuits. Learn about circuit classes, separations, and practical circuit identities used in constructing constant depth quantum circuits with superior computational capabilities. Discover how to create a constant depth, width n quantum circuit that samples from distributions impossible for classical NC^0 circuits with random input bits. Delve into topics including classical circuit complexity, sampling parity with NCO, QNCO circuits, unconditional quantum/classical separations, the GHZ state, rotation by Hamming weight, and mutual rotation techniques. Based on joint research with Natalie Parham presented at the 18th Conference on Theory of Quantum Computation, Communication and Cryptography at the University of Aveiro, this technical presentation provides deep insights into the theoretical advantages of shallow quantum circuits over their classical counterparts.