Bell sampling from quantum circuits

Abstract

A central challenge in the verification of quantum computers is benchmarking their performance as a whole and demonstrating their computational capabilities. In this work, we find a universal model of quantum computation, Bell sampling, that can be used for both of those tasks and thus provides an ideal stepping stone towards fault-tolerance. In Bell sampling, we measure two copies of a state prepared by a quantum circuit in the transversal Bell basis. We show that the Bell samples are classically intractable to produce and at the same time constitute what we call a circuit shadow: from the Bell samples we can efficiently extract information about the quantum circuit preparing the state, as well as diagnose circuit errors. In addition to known properties that can be efficiently extracted from Bell samples, we give several new and efficient protocols: an estimator of state fidelity, a test for the depth of the circuit and an algorithm to estimate a lower bound to the number of T gates in the circuit. With some additional measurements, our algorithm learns a full description of states prepared by circuits with low T-count.

arXiv comment7+17 pages, 5 figures. Comments welcome. v2: corrected typos, added references v3: added results, improved proofs v4: extended noise analysis v5: added analysis of Bell sampling as a fidelity estimator

References in corpus (40)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Average Entropy of a Subsystem
• Characterizing Quantum Supremacy in Near-Term Devices
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Logical quantum processor based on reconfigurable atom arrays
• Quantum Entanglement Growth Under Random Unitary Dynamics
• Noise tailoring for scalable quantum computation via randomized compiling
• Direct Fidelity Estimation from Few Pauli Measurements
• Local random quantum circuits are approximate polynomial-designs
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Emergent statistical mechanics of entanglement in random unitary circuits
• Unconditionally verifiable blind computation
• Information-theoretic bounds on quantum advantage in machine learning
• Assessing the progress of trapped-ion processors towards fault-tolerant quantum computation
• Preparing random states and benchmarking with many-body quantum chaos
• Computational advantage of quantum random sampling
• Exponential Error Suppression for Near-Term Quantum Devices
• Scalable measures of magic resource for quantum computers
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
• A polynomial-time classical algorithm for noisy random circuit sampling
• Performance of quantum error correction with coherent errors
• Coherence in quantum error-correcting codes
• Typicality in random matrix product states
• Benchmarking highly entangled states on a 60-atom analog quantum simulator
• Learning t-doped stabilizer states
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Quantum Virtual Cooling
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Benchmarking Quantum Simulators using Ergodic Quantum Dynamics
• Learning quantum circuits of some $T$ gates
• Fast estimation of outcome probabilities for quantum circuits
• Crystalline Quantum Circuits
• Matrix Product States, Random Matrix Theory and the Principle of Maximum Entropy
• Looped Pipelines Enabling Effective 3D Qubit Lattices in a Strictly 2D Device
• Typical entanglement for Gaussian states
• Page curves and typical entanglement in linear optics

Cited by in corpus (21)

• Logical quantum processor based on reconfigurable atom arrays
• Benchmarking quantum computers
• Learning quantum states and unitaries of bounded gate complexity
• Magic-induced computational separation in entanglement theory
• Probing quantum complexity via universal saturation of stabilizer entropies
• Efficient mutual magic and magic capacity with matrix product states
• Efficient learning of quantum states prepared with few fermionic non-Gaussian gates
• Efficient distributed inner product estimation via Pauli sampling
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Optimal trace-distance bounds for free-fermionic states: Testing and improved tomography
• QSlack: A slack-variable approach for variational quantum semi-definite programming
• Optimal estimates of trace distance between bosonic Gaussian states and applications to learning
• Resource-Efficient Cross-Platform Verification with Modular Superconducting Devices
• PAC-learning of free-fermionic states is NP-hard
• Experimental measurement and a physical interpretation of quantum shadow enumerators
• Adaptivity is not helpful for Pauli channel learning
• Bell sampling in Quantum Monte Carlo simulations
• Agnostic Tomography of Stabilizer Product States
• The abelian state hidden subgroup problem: Learning stabilizer groups and beyond
• Pseudoentanglement Ain't Cheap