Quantum computers that can be simulated classically in polynomial time

DOI10.1145/380752.380785MaRDI QIDQ5175959zbMATH OpenOpenAlexFDO

Authors Leslie G. Valiant

Publication date 27 February 2015

Published in Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/380752.380785

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Analysis of algorithms and problem complexity (68Q25) Quantum computation (81P68)

Recommendations

• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Quantum Complexity Theory
• Quantum computers speed up classical with probability zero
• Classical simulation and complexity of quantum computations (invited talk)
• On the Power of Quantum Computation

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)

Cited in

(35)

• Quantum computers speed up classical with probability zero
• Tensor decomposition and homotopy continuation
• Deterministic polynomial-time quantum algorithms for Simon's problem
• Expressiveness of matchgates.
• Holographic algorithms without matchgates
• Effective simulation of state distribution in qubit chains
• A finite-tame-wild trichotomy theorem for tensor diagrams
• The Hitchhiker guide to: secant varieties and tensor decomposition
• Super-quantum states in \(\mathrm{SU}(2)\) invariant \(3\times N\) level systems
• A common algebraic description for probabilistic and quantum computations
• Time-space efficient simulations of quantum computations
• Simulating quantum computers with probabilistic methods
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Phase space methods for Majorana fermions
• A LOGIC FOR QUANTUM COMPUTATION AND CLASSICAL SIMULATION OF QUANTUM ALGORITHMS
• scientific article; zbMATH DE number 1303028 (Why is no real title available?)
• Computational Power of Quantum Machines, Quantum Grammars and Feasible Computation
• Quantum computing classical physics
• A collapse theorem for holographic algorithms with matchgates on domain size at most 4
• Computing the Tutte polynomial of lattice path matroids using determinantal circuits
• A diagrammatic calculus of fermionic quantum circuits
• QUANTUM COMPUTATION WITH RESTRICTED AMPLITUDES
• A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY
• Clifford Algebras, Spin Groups and Qubit Trees
• \(P\) versus \(NP\) and geometry
• From dual-unitary to biunitary: a 2-categorical model for exactly-solvable many-body quantum dynamics
• Geometric representations of braid and Yang-Baxter gates
• Stabilizer testing and magic entropy via quantum Fourier analysis
• Quantum linear optics via string diagrams
• Displaced fermionic Gaussian states and their classical simulation
• Decompositions of powers of quadrics
• Gaussianity and simulability of Cliffords and matchgates
• Dichotomy for non-negative valued Holant problems on 3-regular bipartite graphs
• Matchgate signatures under variable permutations
• A note on observables for counting trails and paths in graphs

This page was built for publication: Quantum computers that can be simulated classically in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5175959)