Classical Simulation of Quantum Computations
Abstract
TThe main development has been the invention of the holographic method for deriving polynomial time algorithms where none were known before. The method is heavily inspired by the quantum computational model, but the algorithms we have derived to date can all be executed on classical computers in polynomial time. The problems for which such polynomial time algorithms have been derived include versions a restricted monomer-dimerproblem from statistical physics, various coloring and embedding problems from graph theory, and finding maximal sets of planar linear equations that have a common solution. The holographic method is closely related to the matchgate approach the author derived earlier, which offers one of the few known methods for simulating significant subclasses of quantum computations classically in polynomial time.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 31, 2005
- Accession Number
- ADA441205
Entities
People
- Leslie G. Valiant
Organizations
- Harvard University