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 (6)

• Error mitigation for short-depth quantum circuits
• Multi-party entanglement in graph states
• Architectures for quantum simulation showing a quantum speedup
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Modeling Pauli measurements on graph states with nearest-neighbor classical communication
• How long can a quantum memory withstand depolarizing noise?

Cited by in corpus (207)

• 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
• Enhancing Generative Models via Quantum Correlations
• Verification of Many-Qubit States
• 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
• Boundaries of quantum supremacy via random circuit sampling
• Quantum unary approach to option pricing
• A hybrid quantum-classical approach to mitigating measurement errors
• Classically-Verifiable Quantum Advantage from a Computational Bell Test
• 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
• Combinatorial optimisation via highly efficient quantum walks
• Cost-Reduced All-Gaussian Universality with the Gottesman-Kitaev-Preskill Code: Resource-Theoretic Approach to Cost Analysis
• Variational Quantum Algorithm for Non-equilibrium Steady States
• Experimental quantum advantage with quantum coupon collector
• A hardware-efficient leakage-reduction scheme for quantum error correction with superconducting transmon qubits
• LEAP: Scaling Numerical Optimization Based Synthesis Using an Incremental Approach
• Toward Trainability of Quantum Neural Networks
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• 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
• Entanglement and coherence in Bernstein-Vazirani algorithm
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• 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
• Analytical Framework for Quantum Alternating Operator Ansätze
• Quantum supremacy and random circuits
• Unifying the Clifford Hierarchy via Symmetric Matrices over Rings
• Phase transition in Stabilizer Entropy and efficient purity estimation
• 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
• A mathematical framework for operational fine tunings
• Bell non-locality and Kochen-Specker contextuality: How are they connected?
• Analogue Quantum Simulation: A New Instrument for Scientific Understanding
• Quantum Latent Diffusion Models
• Towards Efficient Quantum Hybrid Diffusion Models
• A Tutorial on Quantum Convolutional Neural Networks (QCNN)
• 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
• Quantum Advantage for the LOCAL Model in Distributed Computing
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs
• Quantum computational advantage attested by nonlocal games with the cyclic cluster state
• Automatic Depth-Optimized Quantum Circuit Synthesis for Diagonal Unitary Matrices with Asymptotically Optimal Gate Count
• Entanglement-induced provable and robust quantum learning advantages
• Calculus on parameterized quantum circuits
• Benchmarks of Nonclassicality for Qubit Arrays
• Equivalence between face nonsignaling correlations, full nonlocality, all-versus-nothing proofs, and pseudotelepathy
• Investigating microwave loss of SiGe using superconducting transmon qubits
• Hierarchies of resources for measurement-based quantum computation
• QSW_MPI: a framework for parallel simulation of quantum stochastic walks
• Reasoning about Parallel Quantum Programs
• QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Optimal and tight Bell inequalities for state-independent contextuality sets
• Universal resources for quantum computing
• Phase-space negativity as a computational resource for quantum kernel methods
• Robust and Resource-Efficient Quantum Circuit Approximation
• Kerdock Codes Determine Unitary 2-Designs
• Complexity Classification of Conjugated Clifford Circuits
• Simplest bipartite perfect quantum strategies
• Parametrized constant-depth quantum neuron
• Forbidden subspaces for level-1 QAOA and IQP circuits
• Characterization and tomography of a hidden qubit
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• An Iterative Method to Improve the Precision of Quantum Phase Estimation Algorithm
• Fault-tolerant quantum speedup from constant depth quantum circuits
• Quantum Random Access Stored-Program Machines
• Efficient contextual ontological model of $n$-qubit stabilizer quantum mechanics
• Entanglement preserving local thermalization
• Preparing Greenberger-Horne-Zeilinger state on ground levels of neutral atoms
• Estimating Gibbs partition function with quantumClifford sampling
• Evolving Quantum Circuits
• Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
• All tight correlation Bell inequalities have quantum violations
• Test of the physical significance of Bell nonlocality
• Measurement-induced entanglement and complexity in random constant-depth 2D quantum circuits
• Fast simulation of planar Clifford circuits
• Quantum nonlocality for entanglement of quasiclassical states
• Characterization, synthesis, and optimization of quantum circuits over multiple-control $\text{Z}$-rotation gates: A systematic study
• Self-testing of multiple unsharpness parameters through sequential violations of non-contextual inequality
• Experimental pairwise entanglement estimation for an N-qubit system :A machine learning approach for programming quantum hardware
• Efficient and quantum-adaptive machine learning with fermion neural networks
• Forging quantum data: classically defeating an IQP-based quantum test
• Quantum Circuit Depth Lower Bounds For Homological Codes
• Information causality as a tool for bounding the set of quantum correlations
• The rank of contextuality
• Variational measurement-based quantum computation for generative modeling
• Bell nonlocality between sequential pairs of observers
• Device-independent and semi-device-independent entanglement certification in broadcast Bell scenarios
• A multi-player, multi-team nonlocal game for the toric code
• Universal quantum control with dynamical correction
• Playing nonlocal games with phases of quantum matter
• Quantum topological data analysis via the estimation of the density of states
• Combining contextuality and causality: a game semantics approach
• Irreducible magic sets for $n$-qubit systems
• The Future of Computing: Bits + Neurons + Qubits
• The simplest Kochen-Specker set
• ArsoNISQ: Analyzing Quantum Algorithms on Near-Term Architectures
• Possibilistic simulation of quantum circuits by classical circuits
• Unconditional quantum magic advantage in shallow circuit computation
• Single-qubit rotation algorithm with logarithmic Toffoli count and gate depth
• Quantum Bell inequalities from Information Causality -- tight for Macroscopic Locality
• Reachability in Controlled Markovian Quantum Systems: An Operator-Theoretic Approach
• Quantum Graph Convolutional Neural Networks
• Lifting noncontextuality inequalities
• Topics in Quantum Networking
• Generalised Kochen-Specker Theorem for Finite Non-Deterministic Outcome Assignments
• Depth-2 QAC circuits cannot simulate quantum parity
• Probing many-body Bell correlation depth with superconducting qubits
• Thresholds for post-selected quantum error correction from statistical mechanics
• Fundamental limitations on the recoverability of quantum processes
• Test of Quantumness with Small-Depth Quantum Circuits
• Analogue Quantum Simulation: A Philosophical Prospectus
• Single-qubit gate teleportation provides a quantum advantage
• Tabu-driven Quantum Neighborhood Samplers
• Optimized synthesis of circuits for diagonal unitary matrices with reflection symmetry
• Utility of NISQ devices: optimizing experimental parameters for the fabrication of Au atomic junction using gate-based quantum computers
• Optimal allocation of quantum resources
• Characterizing high-dimensional quantum contextuality
• 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
• Policy Gradient Approach to Compilation of Variational Quantum Circuits
• Detecting Entanglement Generating Circuits in Cloud-Based Quantum Computing
• Quantum advantage in temporally flat measurement-based quantum computation
• Optimal conversion of Kochen-Specker sets into bipartite perfect quantum strategies
• Quantum state preparation and one qubit logic from third-order nonlinear interactions
• Two fundamental solutions to the rigid Kochen-Specker set problem and the solution to the minimal Kochen-Specker set problem under one assumption
• Multipartite entanglement distribution in a topological photonic network
• 3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time
• Universal quantum control over Majorana zero modes
• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
• Classical Coding Approaches to Quantum Applications
• Constant-time Quantum Algorithm for Homology Detection in Closed Curves
• Exploring the boundary of quantum correlations with a time-domain optical processor
• Boson sampling with ultracold atoms in a programmable optical lattice
• Quantum computational advantage implies contextuality
• Analog Errors in Quantum Annealing: Doom and Hope
• Quantum Theory from Principles, Quantum Software from Diagrams
• Demonstration of sequential processors with quantum advantage and analysis of classical performance limits
• Supersinglets can be self-tested with perfect quantum strategies
• Interactive quantum advantage with noisy, shallow Clifford circuits
• Squashed quantum non-Markovianity: a measure of genuine quantum non-Markovianity in states
• Compressed sensing enhanced by quantum approximate optimization algorithm
• Orbital Expansion Variational Quantum Eigensolver: Enabling Efficient Simulation of Molecules with Shallow Quantum Circuit
• Phase Coordinate Uncomputation in Quantum Recursive Fourier Sampling
• Software tool-set for automated quantum system identification and device bring up
• Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources
• A Quantum Convolutional Neural Network for Image Classification
• Self-Testing Graph States Permitting Bounded Classical Communication
• Quantum advantage through the magic pentagram problem
• Cryptographic Characterization of Quantum Advantage
• Practical implementation of Toffoli-based qubit rotation
• Contextuality and Expressivity of Non-locality
• Consideration of the Need for Quantum Grid Computing
• Convexity of noncontextual wirings and how they order the set of correlations
• Compression of quantum shallow-circuit states
• Special-Purpose Quantum Processor Design
• High-performance parallel classical scheme for simulating shallow quantum circuits
• Real-time hybrid quantum-classical computations for trapped-ions with Python control-flow
• A Classification Program for Nonlocality Paradoxes of Three Qubits
• Static and dynamic coherence fraction in the Bernstein-Vazirani algorithm
• Resonant Coupling Parameter Estimation with Superconducting Qubits
• Evaluating NISQ Devices with Quadratic Nonresidues