17

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.)

Glorfindel
  • 359
  • 1
  • 4
  • 10
Abuzer Yakaryilmaz
  • 3,707
  • 1
  • 20
  • 38
  • 1
    Sorry for ignorance. What is relation between space-bounded quantum computation and quantum circuit model? – Alex 'qubeat' Apr 24 '12 at 19:09
  • 1
    @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 08:59
  • 1
    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
  • 1
    @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" (http://www.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 (http://theoryofcomputing.org/articles/v008a001/). – Abuzer Yakaryilmaz Apr 26 '12 at 14:24
  • 1
    Thank you, I have seen that, but there is also work using quantum circuits http://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

1 Answers1

5

I think Amnon Ta-Shma's new result is a good answer to my own question.

... 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. ...

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Abuzer Yakaryilmaz
  • 3,707
  • 1
  • 20
  • 38