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

17

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

Abuzer Yakaryilmaz
źródło
1
Przepraszam za ignorancję. Jaki jest związek między obliczeniami kwantowymi ograniczonymi przestrzenią a modelem obwodu kwantowego?
Alex 'qubeat'
1
@ Alex'qubeat ': Wygodne jest używanie maszyn Turinga do obliczeń przestrzennych. Model obwodu jest odpowiedni do obliczeń czasowych.
Abuzer Yakaryilmaz,
1
Dlaczego jest to wygodniejsze? Czy jest to wygodne w przypadku kwantowym czy klasycznym? Z naiwnego punktu widzenia jest to przestrzeń bez granic wygodniejsza dla (klasycznych) maszyn Turinga.
Alex 'qubeat'
1
@ Alex'qubeat ': Jest to wygodne zarówno dla przypadków klasycznych, jak i kwantowych. Gorąco mogę polecić podstawowy artykuł na ten temat autorstwa Stearnsa, Hartmanisa i Lewisa: „Hierarchie obliczeń ograniczonych pamięci” ( computer.org/portal/web/csdl/doi/10.1109/FOCS.1965.11 ). Możesz także sprawdzić zarówno artykuły Watrous (wspomniane powyżej), jak i najnowszą pracę Melkebeek i Watson ( teoriiofcomputing.org/articles/v008a001 ).
Abuzer Yakaryilmaz
1
Dziękuję, widziałem to, ale są też prace z wykorzystaniem obwodów kwantowych arxiv.org/abs/0908.1467, które przynajmniej nie cierpią z powodu konieczności zarządzania kilkoma różnymi definicjami QTM.
Alex 'qubeat'

Odpowiedzi: