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

• Matrix product states represent ground states faithfully
• Universal resources for measurement-based quantum computation
• Fast simulation of stabilizer circuits using a graph state representation
• Classical simulation of limited-width cluster-state quantum computation

Cited by in corpus (30)

• On the role of entanglement and correlations in mixed-state quantum computation
• Novel schemes for measurement-based quantum computation
• Measurement-based quantum computation beyond the one-way model
• 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
• Efficient classical simulation of the approximate quantum Fourier transform
• Quantum computation by local measurement
• Measurement-Based Quantum Computation
• Quantum spin systems for measurement-based quantum computation
• Universal measurement-based quantum computation in two-dimensional SPT phases
• LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States
• 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
• Entanglement phase transition with spin glass criticality
• Sharp complexity phase transitions generated by entanglement
• Epsilon-measures of entanglement
• Universal resources for quantum computing
• The Gauge Theory of Measurement-Based Quantum Computation
• Classical spin systems and the quantum stabilizer formalism: general mappings and applications
• 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
• The Foliage Partition: An Easy-to-Compute LC-Invariant for Graph States
• 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