# Which results make quantum space interesting?

Time-bounded quantum computation is obviously very interesting. What about space-bounded quantum computation?

I know many interesting results for quantum computation with sublogarithmic space bounds and various kind of quantum automata models.

On the other hand, it was shown that unbounded-error probabilistic and quantum space are equivalent for any space constructable $s(n) \in \Omega(\log(n))$ (Watrous, 1999 and 2003).

I wonder whether there are some specific results making quantum space interesting (by excluding sublogarithmic-space and automata models).

(I am aware of this entry: Quantum analogues of SPACE complexity classes.)

• Sorry for ignorance. What is relation between space-bounded quantum computation and quantum circuit model? – Alex 'qubeat' Apr 24 '12 at 19:09
• @Alex'qubeat': It is convenient to use Turing machines for space-bounded computation. Circuit model is appropriate for time-bounded computation. – Abuzer Yakaryilmaz Apr 25 '12 at 8:59
• Why it is more convenient? Is it convenient in quantum or classical case? From naive point of view it is unbounded space more convenient for (classical) Turing machines. – Alex 'qubeat' Apr 25 '12 at 19:15
• @Alex'qubeat': It is convenient for both classical and quantum cases. I can highly recommend you the fundamental paper on this subject by Stearns, Hartmanis, and Lewis: "Hierarchies of memory limited computations" (computer.org/portal/web/csdl/doi/10.1109/FOCS.1965.11). You can also check both papers of Watrous (mentioned above) and a recent paper by Melkebeek and Watson (theoryofcomputing.org/articles/v008a001). – Abuzer Yakaryilmaz Apr 26 '12 at 14:24
• Thank you, I have seen that, but there is also work using quantum circuits arxiv.org/abs/0908.1467 that, at least does not suffer from necessity to manage with few different definitions of QTM. – Alex 'qubeat' Apr 26 '12 at 17:08

... We show that the inverse of a well conditioned matrix can be approximated in quantum logspace with intermediate measurements. This should be compared with the best known classical algorithm for the problem that requires $\Omega(\log^2 n)$ space. We also show how to approximate the spectrum of a normal matrix, or the singular values of an arbitrary matrix, with $\epsilon$ additive accuracy, and how to approximate the singular value decomposition (SVD) of a matrix whose singular values are well separated. ...