W jaki sposób w maszynie kwantowej Turinga podejmowana jest decyzja o przemieszczeniu się wzdłuż taśmy pamięci?

14

Niech dla maszyny kwantowej Turinga (QTM) ustawionym stanem będzie , a alfabetem symboli będzie , które pojawiają się na głowicy taśmy. Następnie, zgodnie z moim zrozumieniem, w dowolnym momencie, gdy QTM jest obliczany, kubit pojawiający się na jego szczycie będzie zawierał dowolny wektor . Ponadto, jeśli | q_0 \ rangle, | q_1 \ rangle ... \ w Q , wówczas wektor stanu w tym przypadku będzie również dowolny wektor V_q = b_0 | q_0 \ rangle + b_1 | q_1 \ rangle + ... .= { 0 , 1 } V = a | 1 + b | 0 | q 0, | Q 1, . . . Q V q = b 0 | Q 0+ b 1 | Q 1+ . . .Q={0,1}V=a|1+b|0|q0,|q1,...QVq=b0|q0+b1|q1+...

Teraz, po zakończeniu cyklu instrukcji, wektory V i Vq zdecydują, czy QTM przesunie się w lewo czy w prawo wzdłuż taśmy Qubit. Moje pytanie brzmi - ponieważ przestrzeń Hilberta utworzona przez Q jest niepoliczalnym zbiorem nieskończonym, a {Lewo prawo} jest zbiorem dyskretnym, mapowanie między nimi będzie trudne do utworzenia.

Jak więc podejmowana jest decyzja o ruchu w lewo lub w prawo? Czy QTM przesuwa się jednocześnie w lewo i prawo, co oznacza, że ​​zestaw {Lewo prawo} również tworzy inną przestrzeń Hilberta, a zatem ruch QTM staje się czymś w rodzaju za|Lewo+b|Dobrze .

Lub, podobnie jak klasyczna maszyna Turinga, QTM porusza się w lewo lub w prawo, ale nie w obu jednocześnie?

Prem Kumar
źródło
Sprawdź, czy to pomoże, jak oblicza QTM
Pirate X
@ PirateX Przeczytałem ten post, ale nie rozumiem, czy wewnętrzny stan QTM jest klasycznym bytem, ​​czy kwantem. Czy może iść w superpozycji różnych stanów wewnętrznych? Czy QTM może jednocześnie poruszać się w lewo i w prawo wzdłuż taśmy pamięci? Q
Prem kumar

Odpowiedzi:

7

Jeśli mamy QTM z ustawionym stanem i alfabetem taśmy Σ = { 0 , 1 } , nie możemy powiedzieć, że kubit skanowany przez głowicę taśmy „trzyma” wektor a | 0 + b | 1 albo że (wewnętrzny) stan jest wektorem o stanach bazowych odpowiadające Q . Kubity na taśmie mogą być skorelowane ze sobą i ze stanem wewnętrznym, a także z pozycją głowicy taśmy.QΣ={0,1}za|0+b|1Q

Analogicznie nie opisalibyśmy globalnego stanu probabilistycznego urządzenia Turinga, niezależnie określając rozkład dla stanu wewnętrznego i każdego z kwadratów taśmy. Musimy raczej opisać wszystko razem, aby właściwie przedstawić korelacje między różnymi częściami maszyny. Na przykład bity przechowywane w dwóch odległych kwadratach taśmy mogą być doskonale skorelowane, zarówno 0 z prawdopodobieństwem 1/2, jak i oba 1 z prawdopodobieństwem 1/2.

Tak więc, w przypadku kwantowym i zakładając, że mówimy o czystych stanach kwantowych maszyn Turinga z ewolucjami jednostkowymi (w przeciwieństwie do bardziej ogólnego modelu opartego na stanach mieszanych), stan globalny jest reprezentowany przez wektor, którego wpisy są indeksowane przez konfiguracje (tj. klasyczne opisy stanu wewnętrznego, położenia głowicy taśmy i zawartości każdego kwadratu taśmy) maszyny Turinga. Należy zauważyć, że ogólnie zakładamy, że w alfabecie taśmy znajduje się specjalny pusty symbol (który może wynosić 0, jeśli chcemy, aby nasze kwadraty taśmy zapisały qubity) i że rozpoczynamy obliczenia, przy czym co najwyżej wiele kwadratów jest niepustych, dzięki czemu zestaw wszystkich osiągalnych konfiguracji jest policzalny. Oznacza to, że stan będzie reprezentowany przez wektor jednostkowy w oddzielnej przestrzeni Hilberta.

(q,σ)

Q={0,1}Σ={0,1}(i przyjmiemy 0 za pusty symbol). Zaczynamy od stanu 0 skanowanie kwadratu przechowującego 1, a wszystkie pozostałe kwadraty przechowują 0. Nie będę wyraźnie zapisywać funkcji przejścia, ale po prostu opiszę zachowanie w słowach. Przy każdym ruchu zawartość zeskanowanego kwadratu taśmy jest interpretowana jako bit kontrolny dla operacji Hadamarda w stanie wewnętrznym. Po wykonaniu kontrolowanego Hadamarda głowa przesuwa się w lewo, jeśli (nowy) stan ma wartość 0, i przesuwa się w prawo, jeśli (nowy) stan to 1. (W tym przykładzie nigdy tak naprawdę nie zmieniamy zawartości taśmy). Po jednym kroku , QTM będzie w równo ważonej superpozycji między byciem w stanie 0 z kwadratem skanowania głowicy taśmy -1 a byciem w stanie 1 z kwadratem skanowania głowicy taśmy +1. Przy wszystkich kolejnych ruchach kontrolowany Hadamard nic nie robi, ponieważ każdy kwadrat oprócz kwadratu 0 zawiera symbol 0. Głowica taśmy będzie zatem nadal poruszać się jednocześnie w lewo i w prawo, jak cząstka przemieszczająca się w superpozycji na lewo i na prawo.

Jeśli chcesz, możesz oczywiście zdefiniować wariant kwantowego modelu maszyny Turinga, dla którego położenie i ruch głowicy taśmy są deterministyczne, a to nie zrujnuje uniwersalności obliczeniowej modelu, ale „klasyczną” definicję kwantowego Turinga maszyny nie nakładają tego ograniczenia.

John Watrous
źródło
1
@Premkumar: Jako przypis do tej odpowiedzi --- jeśli szukasz autorytatywnego odniesienia do tego rachunku QTM, dobrym miejscem do rozważenia byłoby przełomowe dzieło „Teoria złożoności kwantowej” Bernsteina i Vazirani (Proc. 25th Annual ACM STOC (str. 1411–1473), 1997 [bezpłatny link PDF na stronie citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.144.7852 ]. Prawie wszystkie powyższe uwagi Johna są zasadniczo rozwinięciem definicji 3.2 w tym artykule oraz niektóre dyskusje w tej samej sekcji
Niel de Beaudrap,
@Niel: Nie jestem pewien, czy możesz edytować komentarz, ale jestem pewien, że wiesz, że konferencyjna wersja artykułu Bernsteina i Vazirani pojawiła się w 1993 r., A nie w 1997 r. Wersja czasopisma z 1997 r. Pojawiła się w SIAM Journal of Computing (w naprawdę monumentalny specjalny problem dotyczący obliczeń kwantowych).
John Watrous,
To prawda, a nawet darmowy link PDF opisuje rok 1993; Wydaje mi się, że skrzyżowałem trochę przewodów. (Komentarze można edytować do 10 minut.)
Niel de Beaudrap,
@NieldeBeaudrap Mała korekta: do 5 minut :) (dla zwykłych użytkowników). Mody mogą edytować komentarze w dowolnym momencie.
Sanchayan Dutta
4

Kwantowa maszyna Turinga może przejść w superpozycję ruchu w lewo i prawo. Różni się to od klasycznej maszyny Turinga, która może poruszać się tylko w lewo lub w prawo.

piramidy
źródło