On the complexity of simulating space-bounded quantum computations
type: Item
instance of: scholarly article
title: On the complexity of simulating space-bounded quantum computations
zbMATH Open document ID: 1068.68066
author: John Watrous
published in: Computational Complexity
publication date: 2004-12-13T00:00:00Z
review text: It is well known that quantum computations enable us to compute some functions much faster than deterministic or non-quantum probabilistic ones. For some problems, like factoring large integers, known quantum algorithms are exponentially faster than the best known deterministic ones. As a result, while it is possible to simulate a quantum computer on a non-quantum one, all known simulations require, in the worst case, an exponential increase in time. A natural question is: what about space? The author proves, for space, no large increase is needed for simulations: namely, we can simulate quantum computations that require space \(s\) by a probabilistic non-quantum computer with space \(O(s)\). Thus, we can simulate it on a deterministic non-quantum computer in space \(O(s^2)\). This result is similar to the known relation between non-deterministic and deterministic computations: if we simulate non-deterministic computations on a deterministic machine, time may grow exponentially but space only grows as \(O(s^2)\).
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 81P68
zbMATH DE Number: 2121781
zbMATH Keywords: space-bounded quantum computation
zbMATH Keywords: space-bounded computation
zbMATH Keywords: space complexity
reviewed by: Vladik Kreinovich
MaRDI profile type: Publication
full work available at URL: s00037-003-0177-8
OpenAlex ID: W2069609886
DOI: 10.1007/S00037-003-0177-8
description: scientific article; zbMATH DE number 2121781