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

<ul>
<li><a href="http://doi.acm.org/10.1145/2488608.2488720" rel="nofollow">Amnon Ta-Shma: Inverting well conditioned matrices in quantum logspace. STOC 2013: 881-890</a>. (<a href="http://www.cs.tau.ac.il/~amnon/Papers/T.stoc13.IntQLog.pdf" rel="nofollow">copy from author's website</a>)</li>
</ul>

<blockquote>
  <p>...  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. ...</p>
</blockquote>

CC BY-SA 3.0
2014-03-10T23:52:18.363Z
2014-03-11T05:49:44.990Z
2014-03-11T05:49:44.990Z
Abuzer Yakaryilmaz
<p>Time-bounded quantum computation is obviously very interesting. What about space-bounded quantum computation?</p>
<p>I know many interesting results for quantum computation with sublogarithmic space bounds and various kind of quantum automata models.</p>
<p>On the other hand, it was shown that unbounded-error probabilistic and quantum space are equivalent for any space constructable <span class="math-container">$ s(n) \in \Omega(\log(n)) $</span> (Watrous, <a href="https://www.sciencedirect.com/science/article/pii/S0022000099916550" rel="nofollow noreferrer">1999</a> and <a href="https://doi.org/10.1007/s00037-003-0177-8" rel="nofollow noreferrer">2003</a>).</p>
<p>I wonder whether there are some specific results making quantum space interesting (by <strong>excluding</strong> sublogarithmic-space and automata models).</p>
<p>(I am aware of this entry: <a href="https://cstheory.stackexchange.com/q/4448/7358">Quantum analogues of SPACE complexity classes</a>.)</p>

CC BY-SA 3.0
2012-04-24T19:09:30.757Z
Sorry for ignorance. What is relation between space-bounded quantum computation and quantum circuit model?
Alex 'qubeat'
CC BY-SA 3.0
2012-04-25T08:59:27.870Z
@Alex'qubeat': It is convenient to use Turing machines for space-bounded computation. Circuit model is appropriate for time-bounded computation.
Abuzer Yakaryilmaz
CC BY-SA 3.0
2012-04-25T19:15:00.943Z
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'
CC BY-SA 3.0
2012-04-26T14:24:52.373Z
@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
CC BY-SA 3.0
2012-04-26T17:08:48.680Z
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'
<quantum-computing><space-bounded>
Which results make quantum space interesting?
Abuzer Yakaryilmaz
# Which results make quantum space interesting?

(Asked by: username_0 on 2012-04-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](https://www.sciencedirect.com/science/article/pii/S0022000099916550) and [2003](https://doi.org/10.1007/s00037-003-0177-8)).

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](https://cstheory.stackexchange.com/q/4448/7358).)

**Tags:** quantum-computing, space-bounded

> **Comments:**
> **username_1**: Sorry for ignorance. What is relation between space-bounded quantum computation and quantum circuit model?  
> **username_0**: @Alex'qubeat': It is convenient to use Turing machines for space-bounded computation. Circuit model is appropriate for time-bounded computation.  
> **username_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.  
> **username_0**: @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/).  
> **username_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.  

---

## 1 answers

### Answer by username_0 on 2014-03-10. Score: 5

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

* [Amnon Ta-Shma: Inverting well conditioned matrices in quantum logspace. STOC 2013: 881-890](http://doi.acm.org/10.1145/2488608.2488720). ([copy from author's website](http://www.cs.tau.ac.il/~amnon/Papers/T.stoc13.IntQLog.pdf))

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


---

