Jak zdefiniować kwantowe maszyny Turinga?

52

W obliczeniach kwantowych jaki jest równoważny model maszyny Turinga? Jest dla mnie całkiem jasne, w jaki sposób można zbudować obwody kwantowe z bram kwantowych, ale jak możemy zdefiniować kwantową maszynę Turinga (QTM), która może faktycznie korzystać z efektów kwantowych, a mianowicie działać na układach wielowymiarowych?

quantum-computing turing-machines computation-models

— Ran G.
źródło

9

Ta nota wykładowa z Berkeley daje odpowiedź. www.eecs.berkeley.edu/~vazirani/f97qcom/lec19.ps

— Mohammad Al-Turkistany

1

W rzeczywistości model obwodów kwantowych i maszyna kwantowa są równoważne, co zostało udowodnione przez ACYao.

— Strin,

30

^{( uwaga : pełny opis jest nieco skomplikowany i zawiera kilka subtelności, które wolałem zignorować. Poniżej podano jedynie ogólne pomysły na model QTM)}

Definiując maszynę kwantową Turinga (QTM), chciałoby się mieć prosty model, podobny do klasycznej TM (to znaczy maszynę skończoną plus nieskończoną taśmę), ale pozwolić, aby nowy model miał przewagę mechaniki kwantowej.

Podobnie jak w klasycznym modelu, QTM ma:

$Q=\{q_0,q_1,..\}$ - skończony zestaw stanów. Niech będzie stanem początkowym. $q_0$
$\Sigma=\{\sigma_0,\sigma_1,...\}$ , - zestaw alfabetu wejściowego / roboczego $\Gamma=\{\gamma_0,..\}$
nieskończona taśma i pojedyncza „głowa”.

Jednak definiując funkcję przejścia, należy pamiętać, że wszelkie obliczenia kwantowe muszą być odwracalne . Przypomnijmy, że konfiguracja TM to krotka oznaczająca, że TM jest w stanie , taśma zawiera a głowa wskazuje na tą komórkę taśma. $C=(q,T,i)$ $q\in Q$ $T\in \Gamma^*$ $i$

Ponieważ w danym momencie taśma składa się tylko ze skończonej liczby niepustych komórek, definiujemy (kwantowy) stan QTM jako wektor jednostkowy w przestrzeni Hilberta generowany przez przestrzeń konfiguracji . Konkretna konfiguracja jest reprezentowana jako stan_{(uwaga: Dlatego każda komórka na taśmie jest}_{przestrzenią Hilberta}_.) $\mathcal{H}$ $Q\times\Sigma^*\times \mathrm{Z}$ $C=(q,T,i)$

| C ⟩ = | q ⟩ | T ⟩ | i ⟩ .

$|C\rangle = |q\rangle |T\rangle |i\rangle.$ _$\Gamma$

QTM jest inicjowany do stanu , gdzie jest konkatenacją wejścia z w razie potrzeby wiele „pustych miejsc” (tutaj jest subtelność określająca maksymalną długość, ale ja ją ignoruję). $|\psi(0)\rangle = |q_0\rangle |T_0\rangle |1\rangle$ $T_0\in \Gamma^*$ $x\in\Sigma^*$

Na każdym etapie czasowym stan QTM ewoluuje zgodnie z pewnym jednolitym $U$

| ψ (i + 1) ⟩ = U | ψ (i) ⟩

$|\psi(i+1)\rangle = U|\psi(i)\rangle$

Zauważ, że stan w dowolnym momencie jest określony przez . może być dowolną jednostką, która „zmienia” taśmę tylko tam, gdzie znajduje się głowa i przesuwa ją o jeden krok w prawo lub w lewo. Oznacza to, że wynosi zero, chyba że i różni się od tylko w pozycji . $n$ $|\psi(n)\rangle = U^n|\psi(0)\rangle$ $U$ $\langle q',T',i'|U|q,T,i\rangle$ $i'= i \pm 1$ $T'$ $T$ $i$

Na końcu obliczeń (gdy QTM osiąga stan ) taśma jest mierzona (przy użyciu, powiedzmy, podstawy obliczeniowej). $q_f$

Interesującą rzeczą do zauważenia jest to, że każdy „krok” stan QTM jest superpozycją możliwych konfiguracji, co daje QTM przewagę „kwantową”.

Odpowiedź oparta jest na Masanao Ozawie, O problemie zatrzymania dla kwantowych maszyn Turinga . Zobacz także David Deutsch, teoria kwantowa, zasada Turinga i uniwersalny komputer kwantowy .

— Ran G.
źródło

7

Nie jestem pewien, czy oryginalna definicja Davida Deutscha wszystko zgadza się ... to był pierwszy raz, gdy ktoś próbował to zdefiniować, i dopracowanie poprawnej matematycznej definicji wymagało dopracowania.

— Peter Shor

7

Jak wskazują uwagi, sposobem zdefiniowania QTM jest zdefiniowanie funkcji przejścia jako jednolitej transformacji stanu i litery. Na każdym etapie wyobrażasz sobie mnożenie wektora (stanu, litery) przez transformację, aby uzyskać nowy (stan, literę). Nie jest to szczególnie wygodne, ale można je zdefiniować.

— Suresh
źródło