Czy maszyna Turinga może symulować komputer kwantowy?

62

Wiem, że maszyna Turinga 1 może teoretycznie symulować „cokolwiek”, ale nie wiem, czy mogłaby symulować coś tak zasadniczo odmiennego jak komputer oparty na kwantach. Czy są jakieś próby tego, czy ktoś udowodnił, że jest to możliwe / niemożliwe?

Mam google, ale nie jestem ekspertem w tym temacie, więc nie jestem pewien, gdzie szukać. Znalazłem artykuł w Wikipedii na temat kwantowej maszyny Turinga , ale nie jestem pewien, jak dokładnie różni się ona od klasycznej TM. Znalazłem również artykuł Deutsch's Universal Quantum Turing Machine autorstwa W. Fouché i wsp., Ale dla mnie jest to raczej trudne do zrozumienia.


1. W przypadku, gdy nie jest jasne, przez maszynę Turinga rozumiem koncepcję teoretyczną, a nie maszynę fizyczną (tj. Wdrożenie koncepcji teoretycznej).

Riker
źródło

Odpowiedzi:

43

Tak , komputer kwantowy może być symulowany przez maszynę Turinga , chociaż nie należy tego sugerować, że rzeczywiste komputery kwantowe nie mogą cieszyć się przewagą kwantową , tj. Znaczącą przewagą implementacyjną nad klasycznymi komputerami w świecie rzeczywistym.

Zasadniczo, jeśli człowiek mógłby ręcznie opisać lub wyobrazić sobie, jak coś powinno działać, to wyobrażenie to można zaimplementować na maszynie Turinga. Komputery kwantowe należą do tej kategorii.

Obecnie dużą motywacją do obliczeń kwantowych jest to, że kubity mogą istnieć w superpozycjach , zasadniczo umożliwiający obliczenia masowo równoległe. Potem jest wyżarzanie kwantowe i inne małe sztuczki, które są w zasadzie taktykami obliczeń analogowych .

(1)|ψ=α|0+β|1,

Ale te korzyści dotyczą wydajności. W niektórych przypadkach ta wydajność wykracza poza astronomię, umożliwiając rzeczy, które nie byłyby praktyczne na klasycznym sprzęcie. To powoduje, że obliczenia kwantowe mają główne zastosowania w kryptografii i tym podobne.

Jednak obliczenia kwantowe nie są obecnie motywowane pragnieniem rzeczy, których zasadniczo nie mogliśmy zrobić wcześniej. Jeśli komputer kwantowy może wykonać operację, wówczas klasyczna maszyna Turinga może przeprowadzić symulację komputera kwantowego wykonującego tę operację.

Losowość nie stanowi problemu. Sądzę, że z dwóch ważnych powodów:

  1. Tak czy inaczej losowość można precyzyjniej uchwycić za pomocą matematyki dystrybucji .

  2. Losowość nie jest na początku prawdziwą „ rzeczą ”; to tylko ignorancja. I zawsze możemy wywołać ignorancję.

Nat
źródło
7

Aby zasymulować załamanie funkcji falowej, potrzebujesz źródła losowości. Potrzebujesz więc probabilistycznej maszyny Turinga .

Bjørn Kjos-Hanssen
źródło
6
Klasyczne urządzenia mogą wykorzystywać typowe generatory liczb losowych lub cokolwiek odpowiedniego do ich celów. Losowość nie jest podstawową cechą, którą należy czerpać z mechaniki kwantowej (co jest dość dużym nieporozumieniem koncepcyjnym, które ludzie często dostają na podstawie interpretacji kopenhaskiej , co być może najlepiej jest rozumiane jako uproszczenie).
Nat
3
Ogólnie rzecz biorąc, jeśli nie zależy Ci na wydajności, możesz po prostu wypróbować każdy element przestrzeni zamiast próbkować z niego, unikając potrzeby losowości.
Tavian Barnes,
2
Jeśli naprawdę chcesz stworzyć wszystkie istotne efekty kwantowe, musisz być w stanie naruszyć nierówność Bella, a zatem probabilistyczna maszyna Turinga jest niewystarczająca. Jeśli chcesz dopasować jedynie moc obliczeniową kwantowej maszyny Turinga, możemy użyć maszyny Turinga bez losowości. W każdym razie probabilistyczna maszyna Turinga nie będzie przydatna.
Dyskretna jaszczurka
4

Uzupełnijmy to, co powiedzieli inni: o ile wiemy (klasyczna) maszyna Turinga nie jest w stanie naprawdę symulować korelacji kwantowych . Zostało to wyraźnie stwierdzone w części Właściwości uniwersalnego komputera kwantowego w przełomowej pracy Davida Deutscha Teoria kwantowa, zasada Church-Turinga i uniwersalny komputer kwantowy (Proceedings of the Royal Society of London A 400, s. 97-117 (1985) )).

Szczegóły będą zależeć od implementacji lub dokładnych definicji maszyny Turinga, komputera kwantowego, a zwłaszcza symulacji (jeśli jesteś wystarczająco hojny, co oznacza symulacja , wszystko może symulować wszystko). Ogólnie rzecz biorąc, możliwe jest zaprojektowanie komputera kwantowego, który przy wielokrotnym uruchamianiu, rozpoczynając od dokładnie tego samego stanu początkowego (lub bitów wejściowych), w każdej operacji generuje losowe bity wyjściowe, które prezentują ze sobą pewne korelacje kwantowe.

O ile mi wiadomo, maszyna Turinga nie może tego zrobić.

agaitaarino
źródło
1
Warto dodać (być może bardziej przeformułowanie, ale myślę, że jest przydatne), że dodanie „generowania liczb losowych” do maszyny Turinga (np. Jako wyrocznia) nie pomaga w symulacji kwantowego Turinga maszyna, ponieważ nie może symulować bitów, które naruszają nierówność Bella, podczas gdy kwantowa maszyna Turinga może (jak stwierdzono w artykule Deutsch, jeśli poprawnie ją odczytam).
Dyskretna jaszczurka