Classical simulation of limited-width cluster-state quantum computation

Abstract

We present a classical protocol, using the matrix product state representation, to simulate cluster-state quantum computation at a cost polynomial in the number of qubits in the cluster and exponential in d -- the width of the cluster. We use this result to show that any log-depth quantum computation in the gate array model, with gates linking only nearby qubits, can be simulated efficiently on a classical computer.

4 pages, 1 figure

References in corpus (1)

• Efficient classical simulation of slightly entangled quantum computations

Cited by in corpus (22)

• Measurement-based quantum computation
• Matchgates and classical simulation of quantum circuits
• Classical simulation versus universality in measurement based quantum computation
• Fundamentals of universality in one-way quantum computation
• Efficient classical simulation of the semi-classical Quantum Fourier Transform
• Exponential complexity and ontological theories of quantum mechanics
• Classical algorithms for quantum mean values
• Efficient classical simulation of the approximate quantum Fourier transform
• On the simulation of quantum circuits
• Neural-network states for the classical simulation of quantum computing
• Solving search problems by strongly simulating quantum circuits
• Classical Ising model test for quantum circuits
• Measurement-based quantum computation and undecidable logic
• Quantum Complexity: restrictions on algorithms and architectures
• Efficient classical computation of expectation values in a class of quantum circuits with an epistemically restricted phase space representation
• A multiprecision C++ library for matrix-product-state simulation of quantum computing: Evaluation of numerical errors
• Efficient Mean-Field Simulation of Quantum Circuits Inspired by Density Functional Theory
• A condition under which classical simulability implies efficient state learnability
• Classical simulation of qubit by a new hardware design and its applications
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• Measurement-based quantum computation utilizing the graph states of Bose-Einstein condensates and continuous variables
• Clifford Gates in the Holant Framework