Quantum advantage with shallow circuits

Abstract

We prove that constant-depth quantum circuits are more powerful than their classical counterparts. To this end we introduce a non-oracular version of the Bernstein-Vazirani problem which we call the 2D Hidden Linear Function problem. An instance of the problem is specified by a quadratic form q that maps n-bit strings to integers modulo four. The goal is to identify a linear boolean function which describes the action of q on a certain subset of n-bit strings. We prove that any classical probabilistic circuit composed of bounded fan-in gates that solves the 2D Hidden Linear Function problem with high probability must have depth logarithmic in n. In contrast, we show that this problem can be solved with certainty by a constant-depth quantum circuit composed of one- and two-qubit gates acting locally on a two-dimensional grid.

References in corpus (18)

• Measurement-based quantum computation with cluster states
• Improved Simulation of Stabilizer Circuits
• Error mitigation for short-depth quantum circuits
• Characterizing Quantum Supremacy in Near-Term Devices
• Quantum algorithms: an overview
• Multi-party entanglement in graph states
• Efficient variational quantum simulator incorporating active error minimisation
• Average-case complexity versus approximate simulation of commuting quantum computations
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Architectures for quantum simulation showing a quantum speedup
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Fast parallel circuits for the quantum Fourier transform
• Local Hamiltonians Whose Ground States are Hard to Approximate
• Modeling Pauli measurements on graph states with nearest-neighbor classical communication
• How long can a quantum memory withstand depolarizing noise?
• Fault-Tolerant Quantum Computation with Constant Overhead
• Quantum algorithms to solve the hidden shift problem for quadratics and for functions of large Gowers norm

Cited by in corpus (208)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Computing for Finance: State of the Art and Future Prospects
• Quantum simulation and computing with Rydberg-interacting qubits
• Experimental Quantum Generative Adversarial Networks for Image Generation
• Scalable mitigation of measurement errors on quantum computers
• Kochen-Specker Contextuality
• Challenges and Opportunities of Near-Term Quantum Computing Systems
• A fast, low-leakage, high-fidelity two-qubit gate for a programmable superconducting quantum computer
• Operational Resource Theory of Imaginarity
• Computational advantage of quantum random sampling
• Verifying Multipartite Entangled GHZ States via Multiple Quantum Coherences
• Quantum advantage with noisy shallow circuits in 3D
• Exponential Error Suppression for Near-Term Quantum Devices
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• From pulses to circuits and back again: A quantum optimal control perspective on variational quantum algorithms
• Constructing a virtual two-qubit gate by sampling single-qubit operations
• Magic-state resource theory for the ground state of the transverse-field Ising model
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• Verification of Many-Qubit States
• Enhancing Generative Models via Quantum Correlations
• Variational Benchmarks for Quantum Many-Body Problems
• Nonstabilizerness determining the hardness of direct fidelity estimation
• Leakage detection for a transmon-based surface code
• Demonstration of algorithmic quantum speedup
• Determining the proton content with a quantum computer
• Quantum Advantage from Sequential-Transformation Contextuality
• Quantum Neural Network Classifiers: A Tutorial
• Benchmarking neural networks for quantum computation
• A hybrid quantum-classical approach to mitigating measurement errors
• Creation of Optical Cat and GKP States Using Shaped Free Electrons
• Overcoming I/O bottleneck in superconducting quantum computing: multiplexed qubit control with ultra-low-power, base-temperature cryo-CMOS multiplexer
• Classically-Verifiable Quantum Advantage from a Computational Bell Test
• Quantum unary approach to option pricing
• Boundaries of quantum supremacy via random circuit sampling
• Cost-Reduced All-Gaussian Universality with the Gottesman-Kitaev-Preskill Code: Resource-Theoretic Approach to Cost Analysis
• Combinatorial optimisation via highly efficient quantum walks
• Variational Quantum Algorithm for Non-equilibrium Steady States
• Experimental quantum advantage with quantum coupon collector
• LEAP: Scaling Numerical Optimization Based Synthesis Using an Incremental Approach
• A hardware-efficient leakage-reduction scheme for quantum error correction with superconducting transmon qubits
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Toward Trainability of Quantum Neural Networks
• Machine learning \& artificial intelligence in the quantum domain
• Physical-Layer Supervised Learning Assisted by an Entangled Sensor Network
• Quantum nonlocality in networks can be demonstrated with an arbitrarily small level of independence between the sources
• Formal Verification of Quantum Programs: Theory, Tools and Challenges
• Quantum computing for chemistry and physics applications from a Monte Carlo perspective
• Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states
• Significant-loophole-free test of Kochen-Specker contextuality using two species of atomic-ions
• Clifford Circuit Optimization with Templates and Symbolic Pauli Gates
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Entanglement and coherence in Bernstein-Vazirani algorithm
• Electrical Control of Coherent Spin Rotation of a Single-Spin Qubit
• Quantum advantage for computations with limited space
• A brief introduction to quantum algorithms
• Quantum correlations from simple assumptions
• Magic-induced computational separation in entanglement theory
• Energy-Consumption Advantage of Quantum Computation
• Quantum supremacy and random circuits
• Phase transition in Stabilizer Entropy and efficient purity estimation
• Unifying the Clifford Hierarchy via Symmetric Matrices over Rings
• Analytical Framework for Quantum Alternating Operator Ansätze
• New techniques for fault-tolerant decomposition of Multi-Controlled Toffoli gate
• Efficient Deterministic Preparation of Quantum States Using Decision Diagrams
• Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer
• Quantum computational advantage with string order parameters of 1D symmetry-protected topological order
• Collective optimization for variational quantum eigensolvers
• Fast Quantum Algorithms for Trace Distance Estimation
• Experimental demonstration of quantum advantage for NP verification with limited information
• Logical Clifford Synthesis for Stabilizer Codes
• Quantum Dropout: On and Over the Hardness of Quantum Approximate Optimization Algorithm
• Networked Quantum Services
• Average-Case Quantum Advantage with Shallow Circuits
• Barren plateaus from learning scramblers with local cost functions
• Quantum Amplitude Amplification Operators
• Quantum Latent Diffusion Models
• Analogue Quantum Simulation: A New Instrument for Scientific Understanding
• A mathematical framework for operational fine tunings
• Bell non-locality and Kochen-Specker contextuality: How are they connected?
• Towards Efficient Quantum Hybrid Diffusion Models
• Special Session: Noisy Intermediate-Scale Quantum (NISQ) Computers -- How They Work, How They Fail, How to Test Them?
• Playing quantum nonlocal games with six noisy qubits on the cloud
• A Tutorial on Quantum Convolutional Neural Networks (QCNN)
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs
• Quantum computational advantage attested by nonlocal games with the cyclic cluster state
• Quantum Advantage for the LOCAL Model in Distributed Computing
• Automatic Depth-Optimized Quantum Circuit Synthesis for Diagonal Unitary Matrices with Asymptotically Optimal Gate Count
• Investigating microwave loss of SiGe using superconducting transmon qubits
• Benchmarks of Nonclassicality for Qubit Arrays
• Entanglement-induced provable and robust quantum learning advantages
• Equivalence between face nonsignaling correlations, full nonlocality, all-versus-nothing proofs, and pseudotelepathy
• Calculus on parameterized quantum circuits
• Reasoning about Parallel Quantum Programs
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Hierarchies of resources for measurement-based quantum computation
• QSW_MPI: a framework for parallel simulation of quantum stochastic walks
• QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis
• Optimal and tight Bell inequalities for state-independent contextuality sets
• Robust and Resource-Efficient Quantum Circuit Approximation
• Phase-space negativity as a computational resource for quantum kernel methods
• Universal resources for quantum computing
• Kerdock Codes Determine Unitary 2-Designs
• Complexity Classification of Conjugated Clifford Circuits
• Power of Uninitialized Qubits in Shallow Quantum Circuits
• Quantum Random Access Stored-Program Machines
• An Iterative Method to Improve the Precision of Quantum Phase Estimation Algorithm
• Fault-tolerant quantum speedup from constant depth quantum circuits
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Parametrized constant-depth quantum neuron
• Efficient contextual ontological model of $n$-qubit stabilizer quantum mechanics
• Forbidden subspaces for level-1 QAOA and IQP circuits
• Characterization and tomography of a hidden qubit
• Simplest bipartite perfect quantum strategies
• Entanglement preserving local thermalization
• Evolving Quantum Circuits
• Estimating Gibbs partition function with quantumClifford sampling
• Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
• All tight correlation Bell inequalities have quantum violations
• Preparing Greenberger-Horne-Zeilinger state on ground levels of neutral atoms
• Test of the physical significance of Bell nonlocality
• Efficient and quantum-adaptive machine learning with fermion neural networks
• The rank of contextuality
• Quantum Circuit Depth Lower Bounds For Homological Codes
• Forging quantum data: classically defeating an IQP-based quantum test
• Characterization, synthesis, and optimization of quantum circuits over multiple-control $\text{Z}$-rotation gates: A systematic study
• Measurement-induced entanglement and complexity in random constant-depth 2D quantum circuits
• Self-testing of multiple unsharpness parameters through sequential violations of non-contextual inequality
• Quantum nonlocality for entanglement of quasiclassical states
• Variational measurement-based quantum computation for generative modeling
• Bell nonlocality between sequential pairs of observers
• Fast simulation of planar Clifford circuits
• Experimental pairwise entanglement estimation for an N-qubit system :A machine learning approach for programming quantum hardware
• Information causality as a tool for bounding the set of quantum correlations
• Playing nonlocal games with phases of quantum matter
• Universal quantum control with dynamical correction
• Quantum topological data analysis via the estimation of the density of states
• A multi-player, multi-team nonlocal game for the toric code
• Device-independent and semi-device-independent entanglement certification in broadcast Bell scenarios
• Unconditional quantum magic advantage in shallow circuit computation
• The simplest Kochen-Specker set
• ArsoNISQ: Analyzing Quantum Algorithms on Near-Term Architectures
• Irreducible magic sets for $n$-qubit systems
• Combining contextuality and causality: a game semantics approach
• Possibilistic simulation of quantum circuits by classical circuits
• Single-qubit rotation algorithm with logarithmic Toffoli count and gate depth
• The Future of Computing: Bits + Neurons + Qubits
• Optimal allocation of quantum resources
• Analogue Quantum Simulation: A Philosophical Prospectus
• Quantum Graph Convolutional Neural Networks
• Tabu-driven Quantum Neighborhood Samplers
• Quantum Bell inequalities from Information Causality -- tight for Macroscopic Locality
• Generalised Kochen-Specker Theorem for Finite Non-Deterministic Outcome Assignments
• Test of Quantumness with Small-Depth Quantum Circuits
• Thresholds for post-selected quantum error correction from statistical mechanics
• Lifting noncontextuality inequalities
• Probing many-body Bell correlation depth with superconducting qubits
• Optimized synthesis of circuits for diagonal unitary matrices with reflection symmetry
• Depth-2 QAC circuits cannot simulate quantum parity
• Single-qubit gate teleportation provides a quantum advantage
• Topics in Quantum Networking
• Utility of NISQ devices: optimizing experimental parameters for the fabrication of Au atomic junction using gate-based quantum computers
• Fundamental limitations on the recoverability of quantum processes
• Reachability in Controlled Markovian Quantum Systems: An Operator-Theoretic Approach
• Multipartite entanglement distribution in a topological photonic network
• Quantum advantage in temporally flat measurement-based quantum computation
• Characterizing high-dimensional quantum contextuality
• Policy Gradient Approach to Compilation of Variational Quantum Circuits
• Detecting Entanglement Generating Circuits in Cloud-Based Quantum Computing
• Quantum state preparation and one qubit logic from third-order nonlinear interactions
• 3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time
• Cost of Locally Approximating High-Dimensional Ground States of Contextual Quantum Models
• Unconditionally separating noisy ${\mathsf{QNC}}^0$ from bounded polynomial threshold circuits of constant depth
• Optimal conversion of Kochen-Specker sets into bipartite perfect quantum strategies
• Two fundamental solutions to the rigid Kochen-Specker set problem and the solution to the minimal Kochen-Specker set problem under one assumption
• Universal quantum control over Majorana zero modes
• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
• Classical Coding Approaches to Quantum Applications
• Exploring the boundary of quantum correlations with a time-domain optical processor
• Boson sampling with ultracold atoms in a programmable optical lattice
• Constant-time Quantum Algorithm for Homology Detection in Closed Curves
• Analog Errors in Quantum Annealing: Doom and Hope
• Orbital Expansion Variational Quantum Eigensolver: Enabling Efficient Simulation of Molecules with Shallow Quantum Circuit
• Supersinglets can be self-tested with perfect quantum strategies
• Phase Coordinate Uncomputation in Quantum Recursive Fourier Sampling
• Quantum computational advantage implies contextuality
• Compressed sensing enhanced by quantum approximate optimization algorithm
• Quantum Theory from Principles, Quantum Software from Diagrams
• Interactive quantum advantage with noisy, shallow Clifford circuits
• Squashed quantum non-Markovianity: a measure of genuine quantum non-Markovianity in states
• Software tool-set for automated quantum system identification and device bring up
• Demonstration of sequential processors with quantum advantage and analysis of classical performance limits
• Compression of quantum shallow-circuit states
• A Quantum Convolutional Neural Network for Image Classification
• Contextuality and Expressivity of Non-locality
• A Classification Program for Nonlocality Paradoxes of Three Qubits
• Static and dynamic coherence fraction in the Bernstein-Vazirani algorithm
• Special-Purpose Quantum Processor Design
• High-performance parallel classical scheme for simulating shallow quantum circuits
• Convexity of noncontextual wirings and how they order the set of correlations
• Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources
• Quantum advantage through the magic pentagram problem
• Cryptographic Characterization of Quantum Advantage
• Practical implementation of Toffoli-based qubit rotation
• Evaluating NISQ Devices with Quadratic Nonresidues
• Real-time hybrid quantum-classical computations for trapped-ions with Python control-flow
• Resonant Coupling Parameter Estimation with Superconducting Qubits
• Consideration of the Need for Quantum Grid Computing
• Self-Testing Graph States Permitting Bounded Classical Communication