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

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Separability Criterion for Density Matrices
• Separability of Mixed States: Necessary and Sufficient Conditions
• Efficient classical simulation of slightly entangled quantum computations
• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• An Area Law for One Dimensional Quantum Systems
• Quantum Computational Supremacy
• Bell Inequalities and the Separability Criterion
• On the role of entanglement in quantum computational speed-up
• Simulating quantum computation by contracting tensor networks
• Entanglement versus Correlations in Spin Systems
• Quantum Theory From Five Reasonable Axioms
• Cluster-state quantum computation
• Discrete phase space based on finite fields
• Valence Bond Solids for Quantum Computation
• Hudson's Theorem for finite-dimensional quantum systems
• Classical simulation of noninteracting-fermion quantum circuits
• A subsystem-independent generalization of entanglement
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Trading classical and quantum computational resources
• Average-case complexity versus approximate simulation of commuting quantum computations
• Largest separable balls around the maximally mixed bipartite quantum state
• Universal resources for measurement-based quantum computation
• Measurement-based quantum computation beyond the one-way model
• Matchgates and classical simulation of quantum circuits
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• How robust is a quantum gate in the presence of noise?
• Generalizations of entanglement based on coherent states and convex sets
• Solving the sampling problem of the Sycamore quantum circuits
• Quantum advantage with noisy shallow circuits in 3D
• 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
• Hierarchy of universal entanglement in 2D measurement-based quantum computation
• Fault-Tolerant Postselected Quantum Computation: Schemes
• A separability criterion for density operators
• Phase space simulation method for quantum computation with magic states on qubits
• Efficient classical simulation of matchgate circuits with generalized inputs and measurements
• Classical simulatability, entanglement breaking, and quantum computation thresholds
• On the simulation of quantum circuits
• From estimation of quantum probabilities to 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
• Quantum advantage of unitary Clifford circuits with magic state inputs
• Coherent states, entanglement, and geometric invariant theory
• Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states
• Quantum computing 40 years later
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Efficient solvability of Hamiltonians and limits on the power of some quantum computational models
• The computational landscape of general physical theories
• Fast estimation of outcome probabilities for quantum circuits
• Universal MBQC with generalised parity-phase interactions and Pauli measurements
• Classical simulation of limited-width cluster-state quantum computation
• Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
• Universal resources for approximate and stochastic measurement-based quantum computation
• Transitions in the computational power of thermal states for measurement-based quantum computation
• Efficient Inner-product Algorithm for Stabilizer States
• Sharp complexity phase transitions generated by entanglement
• Generalised state spaces and non-locality in fault tolerant quantum computing schemes
• Families of pure PEPS with efficiently simulatable local hidden variable models for most measurements
• Smallest state spaces for which bipartite entangled quantum states are separable
• Exploiting non-quantum entanglement to widen applicability of limited-entanglement classical simulations of quantum systems