Unconditional quantum magic advantage in shallow circuit computation

Xingjian Zhang, Zhaokai Pan, Guoding Liu

Quantum theory promises computational speed-ups over classical approaches. The celebrated Gottesman-Knill Theorem implies that the full power of quantum computation resides in the…