Quantum Computational Complexity with Photons and Linear Optics

On this wonderful occasion to celebrate Professor Yang Chen Ning’s 100th birthday, we are deeply honored to contribute a chapter on our recent study on the demonstration of quantum computational advantage, which is a dialogue among mathematics, computational complexity, and quantum optics. The concept of quantum computational advantage denotes a milestone that a quantum device can solve a specific mathematical problem that no classical computer can solve within a reasonable amount of time. Just like using the Bell experiments to refute Einstein’s local hidden variable model and establish the quantum entanglement as a valuable resource with strong-than-classical correlation, quantum computational advantage experiments provide evidences to refute the Extended Church-Turing thesis and prove the potential of faster-than-classical computation using quantum mechanics, a widely believed but unproven conjecture proposed by Richard Feynman about forty years ago. The first feasible proposal to demonstrate the quantum computational advantage is boson sampling based on multi-photon interference, where non-classical light is injected into a linear optical network, and the output highly random, photon-number- and path-entangled state is measured by single-photon detectors. We perform experiments which have produced up to 113 photon detection events out of a 144-mode photonic circuit. These rudimentary photonic quantum computers, Jiuzhang, yield an output state space dimension of 1043 and a sampling rate that is 1010 faster than using the state-of-the-art simulation strategy and supercomputers.