Instantaneous non-local computation of low T-depth quantum circuits

Abstract

Instantaneous non-local quantum computation requires multiple parties to jointly perform a quantum operation, using pre-shared entanglement and a single round of simultaneous communication. We study this task for its close connection to position-based quantum cryptography, but it also has natural applications in the context of foundations of quantum physics and in distributed computing. The best known general construction for instantaneous non-local quantum computation requires a pre-shared state which is exponentially large in the number of qubits involved in the operation, while efficient constructions are known for very specific cases only. We partially close this gap by presenting new schemes for efficient instantaneous non-local computation of several classes of quantum circuits, using the Clifford+T gate set. Our main result is a protocol which uses entanglement exponential in the T-depth of a quantum circuit, able to perform non-local computation of quantum circuits with a (poly-)logarithmic number of layers of T gates with quasi-polynomial entanglement. Our proofs combine ideas from blind and delegated quantum computation with the garden-hose model, a combinatorial model of communication complexity which was recently introduced as a tool for studying certain schemes for quantum position verification. As an application of our results, we also present an efficient attack on a recently-proposed scheme for position verification by Chakraborty and Leverrier.

Cited by in corpus (224)

• Surface codes: Towards practical large-scale quantum computation
• Quantum Resource Theories
• Multi-party entanglement in graph states
• Scalable Designs for Quasiparticle-Poisoning-Protected Topological Quantum Computation with Majorana Zero Modes
• Measurement-driven entanglement transition in hybrid quantum circuits
• Scalable probes of measurement-induced criticality
• Is the quantum state real? An extended review of $\psi$-ontology theorems
• Information Scrambling in Computationally Complex Quantum Circuits
• Stabilizer Rényi entropy
• Observation of measurement-induced quantum phases in a trapped-ion quantum computer
• The SIC Question: History and State of Play
• Quantum discord and its allies: a review
• Statistical mechanics of quantum error correcting codes
• Measurement Protected Quantum Phases
• Measurement-induced criticality in (2+1)-d hybrid quantum circuits
• Open source software in quantum computing
• Emerging quantum computing algorithms for quantum chemistry
• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
• Introduction to the book "Quantum Theory: Informational Foundations and Foils"
• Linear growth of quantum circuit complexity
• Fermionic partial tomography via classical shadows
• Conformal invariance and quantum non-locality in critical hybrid circuits
• Efficient classical simulation of random shallow 2D quantum circuits
• Quantifying the quantum gate fidelity of single-atom spin qubits in silicon by randomized benchmarking
• Quantum Error Correction with the Gottesman-Kitaev-Preskill Code
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Entanglement-Assisted Quantum Networks: Mechanics, Enabling Technologies, Challenges, and Research Directions
• Roadmap to Majorana surface codes
• Continuous-variable quantum computing in the quantum optical frequency comb
• Tutorial: Gate-based superconducting quantum computing
• Stabilizer entropies and nonstabilizerness monotones
• qHiPSTER: The Quantum High Performance Software Testing Environment
• Measuring magic on a quantum processor
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Measurement-induced phase transitions in quantum automaton circuits
• Both Toffoli and Controlled-NOT need little help to do universal quantum computation
• A randomized quantum algorithm for statistical phase estimation
• Low overhead fault-tolerant quantum error correction with the surface-GKP code
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Verification of Many-Qubit States
• Relaxing Hardware Requirements for Surface Code Circuits using Time-dynamics
• Emergence of typical entanglement in two-party random processes
• Combining Topological Hardware and Topological Software: Color Code Quantum Computing with Topological Superconductor Networks
• Phase space simulation method for quantum computation with magic states on qubits
• Encoding a qubit in a spin
• Correlation measures and the entanglement wedge cross-section after quantum quenches in two-dimensional conformal field theories
• Phase transition in magic with random quantum circuits
• Efficient classical simulation of matchgate circuits with generalized inputs and measurements
• Pauli stabilizer models of twisted quantum doubles
• Scalable and Flexible Classical Shadow Tomography with Tensor Networks
• Resource theory of quantum scrambling
• Entanglement phase transitions in random stabilizer tensor networks
• Decoding algorithms for surface codes
• On Optimality of CSS Codes for Transversal $T$
• Real Randomized Benchmarking
• Threshold Error Penalty for Fault Tolerant Computation with Nearest Neighbour Communication
• Braiding Majorana zero modes using quantum dots
• qTorch: The Quantum Tensor Contraction Handler
• The ZX-calculus is incomplete for quantum mechanics
• Simulating a measurement-induced phase transition for trapped ion circuits
• Quantum chemistry simulation of ground- and excited-state properties of the sulfonium cation on a superconducting quantum processor
• Braiding by Majorana Tracking and Long-Range CNOT Gates with Color Codes
• Symmetry-protected sign problem and magic in quantum phases of matter
• Photonic resource state generation from a minimal number of quantum emitters
• Quantum Entropy and Central Limit Theorem
• The Road From Classical to Quantum Codes: A Hashing Bound Approaching Design Procedure
• Fundamental limits on the capacities of bipartite quantum interactions
• Network architecture for a topological quantum computer in silicon
• Transitions in Entanglement Complexity in Random Circuits
• Artificial Intelligence for Quantum Computing
• Unforgeable Quantum Encryption
• Error mitigation and quantum-assisted simulation in the error corrected regime
• Quantum computing by color-code lattice surgery
• Entanglement and secret-key-agreement capacities of bipartite quantum interactions and read-only memory devices
• Learning quantum circuits of some $T$ gates
• Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding
• Measurement-based generation and preservation of cat and grid states within a continuous-variable cluster state
• Fast estimation of outcome probabilities for quantum circuits
• Stabilizer extent is not multiplicative
• State preparation by shallow circuits using feed forward
• Accelerated quantum Monte Carlo with mitigated error on noisy quantum computer
• Optimising Clifford Circuits with Quantomatic
• Character randomized benchmarking for non-multiplicity-free groups with applications to subspace, leakage, and matchgate randomized benchmarking
• Measurement-Based Quantum Computation
• Infinite-randomness criticality in monitored quantum dynamics with static disorder
• Introduction to Quantum Error Correction and Fault Tolerance
• Quantum butterfly effect in polarized Floquet systems
• Scrambling and Lyapunov Exponent in Unitary Networks with Tunable Interactions
• Fast Stabiliser Simulation with Quadratic Form Expansions
• Further extensions of Clifford circuits and their classical simulation complexities
• Analytical Framework for Quantum Alternating Operator Ansätze
• Phase transition in Stabilizer Entropy and efficient purity estimation
• Closed-form analytic expressions for shadow estimation with brickwork circuits
• Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
• Graphical Structures for Design and Verification of Quantum Error Correction
• Superluminal X-waves in a polariton quantum fluid
• Exact solution of long-range stabilizer Rényi entropy in the dual-unitary XXZ model
• Robustness of QMA against witness noise
• A quantum primality test with order finding
• Efficient rate-adaptive reconciliation for continuous-variable quantum key distribution
• Quantifying non-stabilizerness via information scrambling
• Limits on Efficient Computation in the Physical World
• Near-Hashing-Bound Multiple-Rate Quantum Turbo Short-Block Codes
• Quantum Error Correction via Noise Guessing Decoding
• Deterministic Fast Scrambling with Neutral Atom Arrays
• A toy model for decoherence in the black hole information problem
• Constructions for Quantum Indistinguishability Obfuscation
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Negative Wigner function at telecommunication wavelength from homodyne detection
• Efficient mutual magic and magic capacity with matrix product states
• Propagation of generalized Pauli errors in qudit Clifford circuits
• Topological quantum error correction in the Kitaev honeycomb model
• Relating Measurement Patterns to Circuits via Pauli Flow
• Classical simulation of quantum circuits by half Gauss sums
• Quantum error correction with the color-Gottesman-Kitaev-Preskill code
• A SAT Encoding for Optimal Clifford Circuit Synthesis
• Compilation of algorithm-specific graph states for quantum circuits
• Effects of quantum resources on the statistical complexity of quantum circuits
• What the foundations of quantum computer science teach us about chemistry
• The Quantum House Of Cards
• Entanglement and Stabilizer entropies of random bipartite pure quantum states
• Entanglement of random hypergraph states
• Power of one non-clean qubit
• Measurement-Based Time Evolution for Quantum Simulation of Fermionic Systems
• Transformations of Stabilizer States in Quantum Networks
• Designing the Quantum Channels Induced by Diagonal Gates
• The principle of majorization: application to random quantum circuits
• Error-correcting codes for fermionic quantum simulation
• Topological Defects in Floquet Circuits
• Magic phase transition and non-local complexity in generalized $W$ State
• Quantum Circuit Mapping for Universal and Scalable Computing in MZI-based Integrated Photonics
• Mitigating Coherent Noise by Balancing Weight-2 $Z$-Stabilizers
• Fractional Chern insulator edges and layer-resolved lattice contacts
• Entanglement Purification with Quantum LDPC Codes and Iterative Decoding
• Mixing and localisation in random time-periodic quantum circuits of Clifford unitaries
• Simulation of open quantum systems via low-depth convex unitary evolutions
• Hybrid quantum computing with ancillas
• Popescu-Rohrlich correlations imply efficient instantaneous nonlocal quantum computation
• Gottesman Types for Quantum Programs
• ZX-Calculus and Extended Wolfram Model Systems II: Fast Diagrammatic Reasoning with an Application to Quantum Circuit Simplification
• Contextuality in composite systems: the role of entanglement in the Kochen-Specker theorem
• Interplay of entanglement structures and stabilizer entropy in spin models
• Quantum convolutional data-syndrome codes
• Realistic simulation of quantum computation using unitary and measurement channels
• Entanglement buffering with two quantum memories
• Emulating Quantum Interference with Generalized Ising Machines
• From the Bloch sphere to phase space representations with the Gottesman-Kitaev-Preskill encoding
• Intrinsic mixed state topological order in a stabilizer system under stochastic decoherence: Strong-to-weak spontaneous symmetry breaking from percolation point of view
• Complementarity and Entanglement in Quantum Information Theory
• Applications and resource reductions in measurement-based variational quantum eigensolvers
• Abstraqt: Analysis of Quantum Circuits via Abstract Stabilizer Simulation
• A Solvable Model of Quantum Darwinism-Encoding Transitions
• Quantum simulation from the bottom up: the case of rebits
• Scalable evaluation of quantum-circuit error loss using Clifford sampling
• Interleaving: Modular architectures for fault-tolerant photonic quantum computing
• Blind Quantum Computation Using a Circuit-Based Quantum Computer
• Quantum Chaos and Circuit Parameter Optimization
• The Gauge Theory of Measurement-Based Quantum Computation
• Classical realization of the quantum Deutsch algorithm
• Observability of fidelity decay at the Lyapunov rate in few-qubit quantum simulations
• Computing quantum magic of state vectors
• Feynman-path type simulation using stabilizer projector decomposition of unitaries
• Quantum circuits with classically simulable operator scrambling
• Understanding the Quantum Computational Speed-up via De-quantisation
• Towards a Minimal Stabilizer ZX-calculus
• Qubit assignment using time reversal
• With a Few Square Roots, Quantum Computing is as Easy as Π
• Is the SIC Outcome There When Nobody Looks?
• New techniques for bounding stabilizer rank
• Partition Function Estimation: Quantum and Quantum-Inspired Algorithms
• Automatic Test Pattern Generation for Robust Quantum Circuit Testing
• Control landscapes for high-fidelity generation of C-NOT and C-PHASE gates with coherent and environmental driving
• Hands-on Introduction to Randomized Benchmarking
• Counting stabiliser codes for arbitrary dimension
• Dynamical phase transitions of information flow in random quantum circuits
• Quantum Darwinism and the spreading of classical information in non-classical theories
• On the average-case complexity of learning output distributions of quantum circuits
• Decoherence and Quantum Error Correction for Quantum Computing and Communications
• Supercomputer simulations of transmon quantum computers
• Normalizer Circuits and Quantum Computation
• Generating $k$ EPR-pairs from an $n$-party resource state
• Multireference error mitigation for quantum computation of chemistry
• Abelian Hypergroups and Quantum Computation
• Measurement-based interleaved randomised benchmarking using IBM processors
• Exotic equilibration dynamics on a 1-D quantum CNOT gate lattice
• Clifford Orbits from Cayley Graph Quotients
• Entanglement spectrum of matchgate circuits with universal and non-universal resources
• Transforming graph states via Bell state measurements
• Wigner's Theorem for stabilizer states and quantum designs
• Clifford circuit based heuristic optimization of fermion-to-qubit mappings
• Measurement-Driven Transitions between Area Law Phases
• Error Correction for Reliable Quantum Computing
• Decoding quantum error correction with Ising model hardware
• Magic Boundaries of 3D Color Codes
• Monte Carlo Simulation of Operator Dynamics and Entanglement in Dual-Unitary Circuits
• Applications of differential geometry and representation theory to description of quantum correlations
• Quantum Lego and XP Stabilizer Codes
• Classical Coding Approaches to Quantum Applications
• Quantum Goppa Codes over Hyperelliptic Curves
• BGLS: A Python Package for the Gate-by-Gate Sampling Algorithm to Simulate Quantum Circuits
• The decomposition of an arbitrary $2^w\times 2^w$ unitary matrix into signed permutation matrices
• Planar Floquet Codes
• A local-realistic theory for fermions
• Plaquette Models, Cellular Automata, and Measurement-induced Criticality
• Partition of 3-qubits using local gates
• Theory-independent monitoring of the decoherence of a superconducting qubit with generalized contextuality
• Quantum collapse as undecidable proposition in an Everettian multiverse
• Proceedings 13th International Conference on Quantum Physics and Logic
• On The Stabilizer Formalism And Its Generalization
• The ABC of Deutsch-Hayden Descriptors
• Twenty years of quantum contextuality at USTC
• On character table of Clifford groups
• Classical simulation of qubit by a new hardware design and its applications
• Explicitly Quantum-parallel Computation by Displacements
• Fault-tolerant Quantum Error Correction Using a Linear Array of Emitters
• Hyperspheres and control of spin chains
• Four qubits generated by Clifford gates
• Optimized Clifford Noise Reduction: Theory, Simulations and Experiments
• Information Bounds on phase transitions in disordered systems
• Distilling GHZ States using Stabilizer Codes
• Programming quantum computers using 3-D puzzles, coffee cups, and doughnuts
• Interference in the Heisenberg Picture of Quantum Field Theory, Local Elements of Reality and Fermions
• The magic of top quarks
• Reduced Sampling Overhead for Probabilistic Error Cancellation by Pauli Error Propagation