On the simulation of quantum circuits

Abstract

We consider recent works on the simulation of quantum circuits using the formalism of matrix product states and the formalism of contracting tensor networks. We provide simplified direct proofs of many of these results, extending an explicit class of efficiently simulable circuits (log depth circuits with 2-qubit gates of limited range) to the following: let C be any poly sized quantum circuit (generally of poly depth too) on n qubits comprising 1- and 2- qubit gates and 1-qubit measurements (with 2-qubit gates acting on arbitrary pairs of qubit lines). For each qubit line j let D_j be the number of 2-qubit gates that touch or cross the line j i.e. the number of 2-qubit gates that are applied to qubits i,k with i \leq j \leq k. Let D=max_j D_j. Then the quantum process can be classically simulated in time n poly(2^D). Thus if D=O(log n) then C may be efficiently classically simulated.

12 pages, latex

References in corpus (7)

• Efficient classical simulation of slightly entangled quantum computations
• DMRG and periodic boundary conditions: a quantum information perspective
• Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
• Simulating quantum computation by contracting tensor networks
• Valence Bond Solids for Quantum Computation
• An introduction to measurement based quantum computation
• Classical simulation of limited-width cluster-state quantum computation

Cited by in corpus (25)

• Measurement-based quantum computation
• Simulating quantum computation by contracting tensor networks
• Simulating Large Quantum Circuits on a Small Quantum Computer
• Nearly optimal lattice simulation by product formulas
• Lecture Notes of Tensor Network Contractions
• Quantum computing and the entanglement frontier
• Simulating boson sampling in lossy architectures
• Quantum interference as a resource for quantum speedup
• Neural-network states for the classical simulation of quantum computing
• The quantum FFT can be classically simulated
• How to simulate quantum measurement without computing marginals
• Efficient computation of permanents, with applications to boson sampling and random matrices
• Solving search problems by strongly simulating quantum circuits
• Simulation Paths for Quantum Circuit Simulation with Decision Diagrams
• ZKCM: a C++ library for multiprecision matrix computation with applications in quantum information
• On Stability of Tensor Networks and Canonical Forms
• Efficient certification and simulation of local quantum many-body Hamiltonians
• Sampling and the complexity of nature
• Twopartite, combinatorial approach to partial k-separability problem for general multipartite states
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• A condition under which classical simulability implies efficient state learnability
• Classical simulation of qubit by a new hardware design and its applications
• Operator Imprecision and Scaling of Shor's Algorithm
• Clifford Gates in the Holant Framework
• Entanglement, Flow and Classical Simulatability in Measurement Based Quantum Computation