Classical simulation versus universality in measurement based quantum computation

Abstract

We investigate for which resource states an efficient classical simulation of measurement based quantum computation is possible. We show that the Schmidt--rank width, a measure recently introduced to assess universality of resource states, plays a crucial role in also this context. We relate Schmidt--rank width to the optimal description of states in terms of tree tensor networks and show that an efficient classical simulation of measurement based quantum computation is possible for all states with logarithmically bounded Schmidt--rank width (with respect to the system size). For graph states where the Schmidt--rank width scales in this way, we efficiently construct the optimal tree tensor network descriptions, and provide several examples. We highlight parallels in the efficient description of complex systems in quantum information theory and graph theory.

16 pages, 4 figures

References in corpus (9)

• The density-matrix renormalization group
• Efficient classical simulation of slightly entangled quantum computations
• Persistent entanglement in arrays of interacting particles
• Matrix product states represent ground states faithfully
• Entanglement monotones
• Universal resources for measurement-based quantum computation
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Fast simulation of stabilizer circuits using a graph state representation
• Classical simulation of limited-width cluster-state quantum computation

Cited by in corpus (62)

• Measurement-based quantum computation
• Simulating quantum computation by contracting tensor networks
• Positive Wigner functions render classical simulation of quantum computation efficient
• Most quantum states are too entangled to be useful as computational resources
• On the role of entanglement and correlations in mixed-state quantum computation
• Novel schemes for measurement-based quantum computation
• Contextuality in Measurement-based Quantum Computation
• Measurement-based quantum computation beyond the one-way model
• The Tensor Networks Anthology: Simulation techniques for many-body quantum lattice systems
• Avoiding barren plateaus using classical shadows
• Universal quantum computation with little entanglement
• Fundamentals of universality in one-way quantum computation
• Tensor operators: constructions and applications for long-range interaction systems
• On measurement-based quantum computation with the toric code states
• Equivalence between contextuality and negativity of the Wigner function for qudits
• Efficient classical simulation of the approximate quantum Fourier transform
• Classical spin models and the quantum stabilizer formalism
• Quantum computation by local measurement
• Transforming graph states using single-qubit operations
• Mapping graph state orbits under local complementation
• No-go Theorem for One-way Quantum Computing on Naturally Occurring Two-level Systems
• Concatenated tensor network states
• Measurement-Based Quantum Computation
• Quantum spin systems for measurement-based quantum computation
• Local convertibility and the quantum simulation of edge states in many-body systems
• Transforming graph states to Bell-pairs is NP-Complete
• Universal measurement-based quantum computation in two-dimensional SPT phases
• LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States
• Universal resources for approximate and stochastic measurement-based quantum computation
• Quantum computational universality of spin-3/2 Affleck-Kennedy-Lieb-Tasaki states beyond the honeycomb lattice
• Solving search problems by strongly simulating quantum circuits
• Acausal measurement-based quantum computing
• Classical simulability and the significance of modular exponentiation in Shor's algorithm
• Measurement-based quantum computation and undecidable logic
• An algorithmic proof for the completeness of two-dimensional Ising model
• Simulation of Quantum Computing on Classical Supercomputers
• Sharp complexity phase transitions generated by entanglement
• State complexity and quantum computation
• Entanglement phase transition with spin glass criticality
• Tensor network methods with graph enhancement
• Completeness of classical ${\varphi }^4$ theory on 2D lattices
• Epsilon-measures of entanglement
• Universal resources for quantum computing
• Counting single-qubit Clifford equivalent graph states is #P-Complete
• Classical spin systems and the quantum stabilizer formalism: general mappings and applications
• The Gauge Theory of Measurement-Based Quantum Computation
• Quantum simulation of classical thermal states
• Symmetry constraints on temporal order in measurement-based quantum computation
• The Hadamard gate cannot be replaced by a resource state in universal quantum computation
• What Can be Observed Locally? Round-based Models for Quantum Distributed Computing
• Optimal accessing and non-accessing structures for graph protocols
• Nearest-neighbor coupling asymmetry in the generation of cluster states
• Maximal tree size of few-qubit states
• Topos logic in measurement-based quantum computation
• The Foliage Partition: An Easy-to-Compute LC-Invariant for Graph States
• Studies on the Role of Entanglement in Mixed-state Quantum Computation
• Classical simulation of measurement-based quantum computation on higher-genus surface-code states
• Practical recipes for the model order reduction, dynamical simulation, and compressive sampling of large-scale open quantum systems
• Quantum information and statistical mechanics: an introduction to frontier
• 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
• Entanglement, Flow and Classical Simulatability in Measurement Based Quantum Computation