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

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$$\sum=\{0,1\}$$V_\sum = a|1\rangle+b|0\rangle$$|q_0\rangle , |q_1\rangle, ... \in Q$$V_q=b_0|q_0\rangle + b_1 |q_1\rangle+ ...$

Teraz, po zakończeniu cyklu instrukcji, wektory $V_\sum$ i $V_q$ zdecydują, czy QTM przesunie się w lewo czy w prawo wzdłuż taśmy Qubit. Moje pytanie brzmi - ponieważ przestrzeń Hilberta utworzona przez $Q \otimes \sum$ jest niepoliczalnym zbiorem nieskończonym, a $\{\text{Left,Right}\}$ 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 $\{\text{Left,Right}\}$ również tworzy inną przestrzeń Hilberta, a zatem ruch QTM staje się czymś w rodzaju $a|\text{Left}\rangle+b|\text{Right}\rangle$ .

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

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$$\Sigma = \{0,1\}$$a|0\rangle + b|1\rangle$$Q$

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,\sigma)$

$Q = \{0,1\}$$\Sigma = \{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.

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.