Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Solovay-Kitaev:
TR10-147 | 22nd September 2010
Dieter van Melkebeek, Thomas Watson

Time-Space Efficient Simulations of Quantum Computations

Revisions: 1

We give two time- and space-efficient simulations of quantum computations with
intermediate measurements, one by classical randomized computations with
unbounded error and the other by quantum computations that use an arbitrary
fixed universal set of gates. Specifically, our simulations show that every
language solvable by a bounded-error quantum algorithm running ... more >>>

ISSN 1433-8092 | Imprint