Które wyniki sprawiają, że przestrzeń kwantowa jest interesująca?

Obliczenia kwantowe ograniczone w czasie są oczywiście bardzo interesujące. A co z obliczeniami kwantowymi ograniczonymi przestrzenią?

Znam wiele interesujących wyników obliczeń kwantowych z sublogarytmicznymi granicami przestrzeni i różnego rodzaju modelami automatów kwantowych.

Z drugiej strony wykazano, że probabilistyczna i kwantowa przestrzeń bez ograniczeń związanych z błędem jest równoważna dla dowolnej konstruowalnej przestrzeni (Watrous, 1999 i 2003 ).$s(n) \in \Omega(\log(n))$

Zastanawiam się, czy istnieją jakieś konkretne wyniki, które sprawiają, że przestrzeń kwantowa jest interesująca ( wykluczając modele sublogarytmiczne i modele automatów).

(Jestem świadomy tego wpisu: analogi kwantowe klas złożoności SPACE .)

Myślę, że nowy wynik Amnona Ta-Shmy jest dobrą odpowiedzią na moje własne pytanie.

• Amnon Ta-Shma: Odwracanie dobrze uwarunkowanych macierzy w kwantowej przestrzeni logicznej. STOC 2013: 881–890 . ( kopia ze strony autora )

$\Omega(\log^2 n)$$\epsilon$