Unconditionally separating noisy ${\mathsf{QNC}}^0$ from bounded polynomial threshold circuits of constant depth

Abstract

The rapid evolution of quantum devices fuels concerted efforts to experimentally establish quantum advantage over classical computing. Many demonstrations of quantum advantage, however, rely on computational assumptions and face verification challenges. Furthermore, steady advances in classical algorithms and machine learning make the issue of provable, practically demonstrable quantum advantage a moving target. In this work, we unconditionally demonstrate that parallel quantum computation can exhibit greater computational power than previously recognized. We prove that polynomial-size biased threshold circuits of constant depth -- which model neural networks with tunable expressivity -- fail to solve certain problems solvable by small constant-depth quantum circuits with local gates, for values of the bias that allow quantifiably large computational power. Additionally, we identify a family of problems that are solvable in constant depth by a universal quantum computer over prime-dimensional qudits with bounded connectivity, but remain hard for polynomial-size biased threshold circuits. We thereby bridge the foundational theory of non-local games in higher dimensions with computational advantage on emerging devices operating on a wide range of physical platforms. Finally, we show that these quantum advantages are robust to noise across all prime qudit dimensions with all-to-all connectivity, enhancing their practical appeal.

Close to published version

References in corpus (36)

• A strong loophole-free test of local realism
• Logical quantum processor based on reconfigurable atom arrays
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Quantum advantage with shallow circuits
• A universal qudit quantum processor with trapped ions
• Efficient Representation of Quantum Many-body States with Deep Neural Networks
• Quantum simulation and computing with Rydberg-interacting qubits
• Hudson's Theorem for finite-dimensional quantum systems
• Single-qubit quantum memory exceeding $10$-minute coherence time
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Analytic and numerical demonstration of quantum self-correction in the 3D Cubic Code
• Long-range quantum entanglement in noisy cluster states
• Cosmic Bell Test using Random Measurement Settings from High-Redshift Quasars
• Application-Oriented Performance Benchmarks for Quantum Computing
• Quantum advantage with noisy shallow circuits in 3D
• Hardware efficient quantum simulation of non-abelian gauge theories with qudits on Rydberg platforms
• Efficient Decoders for Qudit Topological Codes
• Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering cross section of a 2D target
• A fast fault-tolerant decoder for qubit and qudit surface codes
• Transversal Clifford gates on folded surface codes
• Quantum advantage of unitary Clifford circuits with magic state inputs
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Interpretable Quantum Advantage in Neural Sequence Learning
• Fault-Tolerant One-Bit Addition with the Smallest Interesting Colour Code
• Quantum Contextuality with Stabilizer States
• Learning shallow quantum circuits
• Constant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication
• What Formal Languages Can Transformers Express? A Survey
• Mermin inequalities for perfect correlations in many-qutrit systems
• Average-Case Quantum Advantage with Shallow Circuits
• Error rate reduction of single-qubit gates via noise-aware decomposition into native gates
• Robust sparse IQP sampling in constant depth
• Fault-tolerant quantum speedup from constant depth quantum circuits
• Space Complexity of Streaming Algorithms on Universal Quantum Computers
• Quantum Advantage with Shallow Circuits Under Arbitrary Corruption
• Noisy decoding by shallow circuits with parities: classical and quantum