Speaker: Sergey Bravyi, IBM, T.J. Watson Research Center

Abstract: Quantum effects can significantly enhance information-processing capabilities and speed up solution of certain problems.  Whether a computational quantum advantage can be rigorously proved in some settings or demonstrated experimentally is the subject of active debate. Here we show that parallel quantum algorithms running in a constant time are strictly more powerful than their classical counterparts. To this end we define a computational problem associated with the well-known Magic Square Game. We show that the problem can be solved by a constant depth quantum circuit, whereas any classical circuit solving the problem must have logarithmic depth. Moreover, this advantage persists even if the quantum circuit is corrupted by noise, provided that the noise rate is below a certain constant threshold value.