Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

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. As a step towards even stronger lower bounds, we present a search problem that we call the Parity Bending Problem, which is in QNC^0/qpoly (QNC^0 circuits that are allowed to start with a quantum state of their choice that is independent of the input), but is not even in AC^0[2] (the class AC^0 with unbounded fan-in XOR gates). All the quantum circuits in our paper are simple, and the main difficulty lies in proving the classical lower bounds. For this we employ a host of techniques, including a refinement of Håstad's switching lemmas for multi-output circuits that may be of independent interest, the Razborov-Smolensky AC^0[2] lower bound, Vazirani's XOR lemma, and lower bounds for non-local games.

References in corpus (4)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum advantage with shallow circuits
• Architectures for quantum simulation showing a quantum speedup
• Quantum Circuits with Unbounded Fan-out

Cited by in corpus (22)

• Quantum advantage with noisy shallow circuits in 3D
• State preparation by shallow circuits using feed forward
• Quantum advantage for computations with limited space
• Multivariate trace estimation in constant quantum depth
• A brief introduction to quantum algorithms
• Learning shallow quantum circuits
• Quantum computational advantage with string order parameters of 1D symmetry-protected topological order
• Depth-efficient proofs of quantumness
• Distributed Quantum Computing with QMPI
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Fast simulation of planar Clifford circuits
• Device-independent and semi-device-independent entanglement certification in broadcast Bell scenarios
• Single-qubit gate teleportation provides a quantum advantage
• Readout Error Mitigation for Mid-Circuit Measurements and Feedforward
• Constant-time Quantum Algorithm for Homology Detection in Closed Curves
• Unconditionally separating noisy ${\mathsf{QNC}}^0$ from bounded polynomial threshold circuits of constant depth
• Quantum advantage in temporally flat measurement-based quantum computation
• 3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time
• Catalytic $z$-rotations in constant $T$-depth
• Quantum advantage through the magic pentagram problem
• Learning Feedback Mechanisms for Measurement-Based Variational Quantum State Preparation