Efficient classical simulation of cluster state quantum circuits with alternative inputs

Abstract

We provide new examples of pure entangled systems related to cluster state quantum computation that can be efficiently simulated classically. In cluster state quantum computation input qubits are initialised in the `equator' of the Bloch sphere, $CZ$ gates are applied, and finally the qubits are measured adaptively using $Z$ measurements or measurements of $\cos (\theta )X+\sin (\theta )Y$ operators. We consider what happens when the initialisation step is modified, and show that for lattices of finite degree $D$, there is a constant $\lambda \approx 2.06$ such that if the qubits are prepared in a state that is within ${\lambda }^{-D}$ in trace distance of a state that is diagonal in the computational basis, then the system can be efficiently simulated classically in the sense of sampling from the output distribution within a desired total variation distance. In the square lattice with $D=4$ for instance, ${\lambda }^{-D}\approx 0.056$. We develop a coarse grained version of the argument which increases the size of the classically efficient region. In the case of the square lattice of qubits, the size of the classically simulatable region increases in size to at least around $\approx 0.070$, and in fact probably increases to around $\approx 0.1$. The results generalise to a broader family of systems, including qudit systems where the interaction is diagonal in the computational basis and the measurements are either in the computational basis or unbiased to it. Potential readers who only want the short version can get much of the intuition from figures 1 to 3.

References in corpus (25)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Entanglement versus Correlations in Spin Systems
• Valence Bond Solids for Quantum Computation
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Universal resources for measurement-based quantum computation
• Measurement-based quantum computation beyond the one-way model
• Matchgates and classical simulation of quantum circuits
• Solving the sampling problem of the Sycamore quantum circuits
• Discrete Wigner functions and quantum computational speedup
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Universal quantum computation with little entanglement
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Classical simulation versus universality in measurement based quantum computation
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Fault-Tolerant Postselected Quantum Computation: Schemes
• Classical simulatability, entanglement breaking, and quantum computation thresholds
• On the simulation of quantum circuits
• A hidden variable model for universal quantum computation with magic states on qubits
• Phase transition of computational power in the resource states for one-way quantum computation
• Coherent states, entanglement, and geometric invariant theory
• Quantum computing 40 years later
• Fast estimation of outcome probabilities for quantum circuits
• Classical simulation of limited-width cluster-state quantum computation
• Sharp complexity phase transitions generated by entanglement
• Families of pure PEPS with efficiently simulatable local hidden variable models for most measurements