17
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Sorry for ignorance. What is relation between space-bounded quantum computation and quantum circuit model? $\endgroup$
    – Alex 'qubeat'
    Apr 24, 2012 at 19:09
  • 1
    $\begingroup$ @Alex'qubeat': It is convenient to use Turing machines for space-bounded computation. Circuit model is appropriate for time-bounded computation. $\endgroup$
    – Abuzer Yakaryilmaz
    Apr 25, 2012 at 8:59
  • 1
    $\begingroup$ 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. $\endgroup$
    – Alex 'qubeat'
    Apr 25, 2012 at 19:15
  • 1
    $\begingroup$ @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). $\endgroup$
    – Abuzer Yakaryilmaz
    Apr 26, 2012 at 14:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – Alex 'qubeat'
    Apr 26, 2012 at 17:08

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.