Universal quantum computation with little entanglement

Abstract

We show that universal quantum computation can be achieved in the standard pure-state circuit model while, at any time, the entanglement entropy of all bipartitions is small---even tending to zero with growing system size. The result is obtained by showing that a quantum computer operating within a small region around the set of unentangled states still has universal computational power, and by using continuity of entanglement entropy. In fact an analogous conclusion applies to every entanglement measure which is continuous in a certain natural sense, which amounts to a large class. Other examples include the geometric measure, localizable entanglement, smooth epsilon-measures, multipartite concurrence, squashed entanglement, and several others. We discuss implications of these results for the believed role of entanglement as a key necessary resource for quantum speed-ups.

References in corpus (20)

• Quantum entanglement
• Efficient classical simulation of slightly entangled quantum computations
• Quantifying Entanglement
• Entanglement monotones
• On the role of entanglement in quantum computational speed-up
• Simulating quantum computation by contracting tensor networks
• "Squashed Entanglement" - An Additive Entanglement Measure
• Decoherence and multipartite entanglement
• Entanglement and the Power of One Qubit
• Diverging Entanglement Length in Gapped Quantum Spin Systems
• A potential multipartide entanglement measure
• Most quantum states are too entangled to be useful as computational resources
• Quantifying Entanglement with Witness Operators
• Universal resources for measurement-based quantum computation
• Constructing N-qubit entanglement monotones from anti-linear operators
• Good dynamics versus bad kinematics. Is entanglement needed for quantum computation?
• Quantum Computing Without Entanglement
• Classical simulation versus universality in measurement based quantum computation
• Universality of Entanglement and Quantum Computation Complexity
• Epsilon-measures of entanglement

Cited by in corpus (74)

• Adiabatic Quantum Computing
• Contextuality supplies the magic for quantum computation
• Qudits and high-dimensional quantum computing
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Generation and Confirmation of a (100x100)-dimensional entangled Quantum System
• Contextuality in Measurement-based Quantum Computation
• Quantum discord and its allies: a review
• Quantum Hypergraph States
• Native qudit entanglement in a trapped ion quantum processor
• Computational speed-up in a single qudit NMR quantum information processor
• Computational speed-up with a single qudit
• Thermodynamic cost of creating correlations
• The entropy vector formalism and the structure of multidimensional entanglement in multipartite systems
• Inequalities for the Ranks of Quantum States
• Equivalence between contextuality and negativity of the Wigner function for qudits
• Characterizing multipartite entanglement without shared reference frames
• Quantum interference as a resource for quantum speedup
• Catalysis of entanglement and other quantum resources
• Entanglement Detection Beyond Measuring Fidelities
• Discord and quantum computational resources
• Entanglement and coherence in Bernstein-Vazirani algorithm
• Characterizing entanglement dimensionality from randomized measurements
• The computational landscape of general physical theories
• Quantum State Complexity in Computationally Tractable Quantum Circuits
• Measurement-Based Quantum Computation
• Local convertibility and the quantum simulation of edge states in many-body systems
• Generalized concurrence in boson sampling
• Quantifying entanglement of maximal dimension in bipartite mixed states
• Area law in one dimension: Degenerate ground states and Renyi entanglement entropy
• Entanglement and deterministic quantum computing with one qubit
• Bounding entanglement dimensionality from the covariance matrix
• Witnessing quantum resource conversion within deterministic quantum computation using one pure superconducting qubit
• Bounds on the power of proofs and advice in general physical theories
• The Degree of Quantum Correlation Required to Speed-Up a Computation
• Power of one non-clean qubit
• Epsilon-smooth measure of coherence
• Quantum Extensive Form Games
• State complexity and quantum computation
• Sharp complexity phase transitions generated by entanglement
• Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed
• Computational complexity of non-equilibrium steady states of quantum spin chains
• Exact and Efficient Simulation of Concordant Computation
• Promoting quantum correlations in DQC1 model via post-selection
• Entanglement bounds on the performance of quantum computing architectures
• Fermionized photons in the ground state of one-dimensional coupled cavities
• Universal resources for quantum computing
• Genuine Multipartite Entanglement in Quantum Optimization
• Quantifying multiparticle entanglement with randomized measurements
• Quantum computation by teleportation and symmetry
• A multi-player, multi-team nonlocal game for the toric code
• Playing nonlocal games with phases of quantum matter
• Normalizer Circuits and Quantum Computation
• Information locking and its resource efficient extraction
• Coherence as a resource for phase estimation
• Entanglement, Complexity, and Causal Asymmetry in Quantum Theories
• Robust projective measurements through measuring code-inspired observables
• Topos logic in measurement-based quantum computation
• Stellar representation of extremal Wigner-negative spin states
• Uncertainty relations between quantum Fisher information and entanglement monotones
• Parameterized bipartite entanglement measures and entanglement constraints
• Entanglement of weighted graphs uncovers transitions in variable-range interacting models
• Entanglement hierarchies in multipartite scenarios
• Contextuality, Witness of Quantum Weirdness
• Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks
• Breaking absolute separability with quantum switch
• Sufficient Wigner Negativity Implies Genuine Multipartite Entanglement
• An Entanglement Monotone from the Contextual Fraction
• The Computational Power of Non-interacting Particles
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• Information Theoretic Resources in Quantum Theory
• Search Via quantum walks with intermediate measurements
• Oracle problems as communication tasks and optimization of quantum algorithms
• Static and dynamic coherence fraction in the Bernstein-Vazirani algorithm
• On the extremal points of the $\Lambda$-polytopes and classical simulation of quantum computation with magic states