Quantum Circuits That Can Be Simulated Classically in Polynomial Time

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Erratum to: ``Signature theory in holographic algorithms ⋮ On blockwise symmetric matchgate signatures and higher domain \#CSP ⋮ On the theory of matchgate computations ⋮ The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems ⋮ On blockwise symmetric signatures for matchgates ⋮ Holant problems for 3-regular graphs with complex edge functions ⋮ Valiant's holant theorem and matchgate tensors ⋮ Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain ⋮ On the Satisfiability of Quantum Circuits of Small Treewidth ⋮ Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits ⋮ Classification of a Class of Counting Problems Using Holographic Reductions ⋮ Evaluations of Tutte polynomials of regular graphs ⋮ Counting degree-constrained subgraphs and orientations ⋮ \(P\) versus \(NP\) and geometry ⋮ On the satisfiability of quantum circuits of small treewidth ⋮ Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions ⋮ Holographic algorithms by Fibonacci gates ⋮ Holographic algorithms without matchgates ⋮ Holographic algorithms: from art to science ⋮ Commuting quantum circuits and complexity of Ising partition functions ⋮ Holographic algorithms on domains of general size ⋮ Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits ⋮ Quantum circuit dynamics via path integrals: Is there a classical action for discrete-time paths? ⋮ Undirected determinant and its complexity ⋮ The computational complexity of Holant problems on 3-regular graphs ⋮ Holographic algorithms beyond matchgates ⋮ Complexity classification of the six-vertex model ⋮ The rational approximations of the unitary groups ⋮ Classical Ising model test for quantum circuits ⋮ Signature theory in holographic algorithms ⋮ Generalized counting constraint satisfaction problems with determinantal circuits ⋮ A Complete Characterization of Unitary Quantum Space ⋮ On the Complexity of Holant Problems ⋮ Infrared-dressed entanglement of cold open-shell polar molecules for universal matchgate quantum computing ⋮ Matchgates and classical simulation of quantum circuits ⋮ Free fermions behind the disguise ⋮ Spin systems on \(k\)-regular graphs with complex edge functions ⋮ Approximate counting for complex-weighted Boolean constraint satisfaction problems ⋮ A computational proof of complexity of some restricted counting problems ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ On symmetric signatures in holographic algorithms ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ Clifford gates in the Holant framework ⋮ Dichotomy for Holant\(^\ast\) problems on the Boolean domain ⋮ Exponential decay of correlations implies area law ⋮ The Complexity of Symmetric Boolean Parity Holant Problems ⋮ Quantum matchgate computations and linear threshold gates ⋮ Holographic algorithms: the power of dimensionality resolved ⋮ Classical simulability, entanglement breaking, and quantum computation thresholds ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints ⋮ Boundary theories of critical matchgate tensor networks ⋮ Boson-sampling with non-interacting fermions