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

• Diverging Entanglement Length in Gapped Quantum Spin Systems
• Quantifying Entanglement with Witness Operators
• Universal resources for measurement-based quantum computation
• Constructing N-qubit entanglement monotones from anti-linear operators
• Classical simulation versus universality in measurement based quantum computation
• Epsilon-measures of entanglement

Cited by in corpus (71)

• 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
• Quantum discord and its allies: a review
• Native qudit entanglement in a trapped ion quantum processor
• Computational speed-up with a single qudit
• Computational speed-up in a single qudit NMR quantum information processor
• 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
• 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
• Entanglement and deterministic quantum computing with one qubit
• Area law in one dimension: Degenerate ground states and Renyi entanglement entropy
• 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
• Epsilon-smooth measure of coherence
• Power of one non-clean qubit
• Quantum Extensive Form Games
• Sharp complexity phase transitions generated by entanglement
• State complexity and quantum computation
• Computational complexity of non-equilibrium steady states of quantum spin chains
• Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed
• 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
• Universal resources for quantum computing
• Fermionized photons in the ground state of one-dimensional coupled cavities
• Genuine Multipartite Entanglement in Quantum Optimization
• Quantifying multiparticle entanglement with randomized measurements
• Quantum computation by teleportation and symmetry
• Playing nonlocal games with phases of quantum matter
• A multi-player, multi-team nonlocal game for the toric code
• Normalizer Circuits and Quantum Computation
• Information locking and its resource efficient extraction
• Entanglement hierarchies in multipartite scenarios
• Stellar representation of extremal Wigner-negative spin states
• Entanglement, Complexity, and Causal Asymmetry in Quantum Theories
• Entanglement of weighted graphs uncovers transitions in variable-range interacting models
• Robust projective measurements through measuring code-inspired observables
• Uncertainty relations between quantum Fisher information and entanglement monotones
• Parameterized bipartite entanglement measures and entanglement constraints
• Coherence as a resource for phase estimation
• Topos logic in measurement-based quantum computation
• Sufficient Wigner Negativity Implies Genuine Multipartite Entanglement
• An Entanglement Monotone from the Contextual Fraction
• Breaking absolute separability with quantum switch
• Contextuality, Witness of Quantum Weirdness
• Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks
• On the extremal points of the $\Lambda$-polytopes and classical simulation of quantum computation with magic states
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• Oracle problems as communication tasks and optimization of quantum algorithms
• Search Via quantum walks with intermediate measurements
• Static and dynamic coherence fraction in the Bernstein-Vazirani algorithm
• The Computational Power of Non-interacting Particles
• Information Theoretic Resources in Quantum Theory