Analogi kwantowe klas złożoności SPACE

Często rozważamy klasy złożoności, w których jesteśmy ograniczeni ilością miejsca, które może wykorzystać nasza maszyna Turinga, na przykład: $\textbf{DSPACE}(f(n))$ lub $\textbf{NSPACE}(f(n))$ . Wydaje się, że we wczesnej teorii złożoności odniesiono duży sukces z tymi klasami, takimi jak twierdzenie o hierarchii przestrzeni i tworzenie ważnych klas, takich jak $\textbf{L}$ i $\textbf{PSPACE}$ . Czy istnieją analogiczne definicje obliczeń kwantowych? Czy jest jakiś oczywisty powód, dla którego analogia kwantowa nie byłaby interesująca?

Wydaje się, że ważne byłoby posiadanie klasy takiej jak --- kwantowa wersja : wymagająca logarytmicznej liczby kubitów (a może kwantowa TM wykorzystuje przestrzeń logarytmiczną). $\textbf{QL}$ $\textbf{L}$

cc.complexity-theory complexity-classes quantum-computing space-bounded Artem Kaznatcheev
źródło

ups, wygląda na to, że kwantowy analog PSPACE jest już zdefiniowany: BQPSPACE i jest równy PSPACE.

Artem Kaznatcheev

Być może zechcesz sprawdzić „Złożoność przestrzeni złożoności” Johna Watrousa ( cs.uwaterloo.ca/~watrous/Papers/… )

Abel Molina

@Abel może to być odpowiedź.

Suresh Venkat

Dla klas przestrzeni powyżej przestrzeni wielomianowej klasy kwantowe i klasyczne są równe. Jeśli chodzi o przestrzeń logów kwantowych, niewiele mogę powiedzieć. Sądzę, że wszystko, co możemy powiedzieć, to

L \subseteq B Q L \subseteq D S P A C E (\log^{2} n)

$L \subseteq BQL \subseteq DSPACE(\log^2 n)$

Robin Kothari

@ Suresh Jasne, dodałem link jako odpowiedź i umieściłem również część informacji w streszczeniu.

Abel Molina

Odpowiedzi:

John Watrous może zechcesz sprawdzić złożoność kwantową ograniczoną przez przestrzeń kosmiczną .

Otrzymujesz wynik, że dla dowolnego kwantowa maszyna Turinga działająca w przestrzeni może być symulowana przez probabilistyczną maszynę Turinga z nieograniczonym błędem działającym w przestrzeni . Można również, że każda Quantum Turinga Maszyna działa w przestrzeni mogą być symulowane $s=\Omega(\log n)$ $s$ $O(s)$ $s$ $NC^2(2^s) \subseteq DSPACE(s^2) \cap DTIME(2^{O(s)})$

Abel Molina
źródło

Masz na myśli

? Co to jest

Ω (\log n)

$\Omega(\log n)$

N C^{2} (2^{s})

$NC^2(2^s)$

Robin Kothari

@Robin:

to klasa problemów możliwych do rozwiązania przez rodzinę jednorodnych obwodów logicznych typu

space, o rozmiarze

, głębokości

i ograniczonym wachlowaniu.

N C^{2} (2^{s})

$NC^2(2^s)$

s

$s$

2^{O (s)}

$2^{O(s)}$

O (s^{2})

$O(s^2)$

Alessandro Cosentino

N C^{2} (2^{s})

$NC^2(2^s)$

Jeśli chodzi o granice przestrzeni sublogarytmicznej, kwant okazał się silniejszy niż klasyczny, patrz

Abuzer Yakaryılmaz, AC Cem Say, „Obliczenia kwantowe z nieograniczonym błędem z małymi granicami przestrzeni”, Information and Computation, t. 209, s. 873–892, 2011. (nieco starsza wersja w arXiv: 1007.3624 )

Abuzer Yakaryılmaz, AC Cem Say, „Języki rozpoznawane przez niedeterministyczne kwantowe automaty skończone”, Informacja i obliczenia kwantowe, t. 10, s. 747–770, 2010. ( arXiv: 0902.2081 )

w przypadku nieograniczonego przypadku błędu. Papier

A. Ambainis i J. Watrous. Dwukierunkowe automaty skończone ze stanami kwantowymi i klasycznymi. Theoretical Computer Science, 287 (1): 299–311, 2002, ( arXiv: cs / 9911009v1 )

wraz z faktem, że język palindromu nie może zostać rozpoznany przez probabilistyczne maszyny Turinga z przestrzenią sublogarytmiczną, pokazują, że to samo dotyczy również ograniczonego przypadku błędu.

Cem Say
źródło