Exponential Separation Between Shallow Quantum Circuits and Unbounded Fan-In Shallow Classical Circuits

          @misc{ scivideos_15438,
            doi = {},
            url = {https://simons.berkeley.edu/talks/exponential-separation-between-shallow-quantum-circuits-and-unbounded-fan-shallow-classical},
            author = {},
            keywords = {},
            language = {en},
            title = {Exponential Separation Between Shallow Quantum Circuits and Unbounded Fan-In Shallow Classical Circuits},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {feb},
            note = {15438 see, \url{https://scivideos.org/index.php/Simons-Institute/15438}}
          }
          

Abstract

Recently, Bravyi, Gosset, and König (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (or NC^0 circuits). In other words, they exhibited a search problem in QNC^0 that is not in NC^0. We strengthen their result by proving that the 2D HLF problem is not contained in AC^0, the class of classical, polynomial-size, constant-depth circuits over the gate set of unbounded fan-in AND and OR gates, and NOT gates. We also supplement this worst-case lower bound with an average-case result: There exists a simple distribution under which any AC^0 circuit (even of nearly exponential size) has exponentially small correlation with the 2D HLF problem. Our results are shown by constructing a new problem in QNC^0, which we call the Relaxed Parity Halving Problem, which is easier to work with. We prove our AC^0 lower bounds for this problem, and then show that it reduces to the 2D HLF problem.  https://arxiv.org/abs/1906.08890