Jaka jest różnica między kwantową TM a niedetermistyczną TM?

Rozmawiałem o tym, jak zdefiniować kwantowe maszyny Turinga? i czuję, że kwantowa TM i niedetermistyczna TM są jednym i tym samym. Odpowiedzi na inne pytanie nie dotyczą tego. Czy te dwa modele są takie same?

Jeśli nie,

1. Jakie są różnice między Quantum TM i NDTM?
2. Czy jest jakieś obliczenie, które NDTM wykonałby szybciej niż Quantum TM?
3. Jeśli tak jest, to kwantowa TM jest DTM, to dlaczego jest tak dużo szumu w tej technologii, mamy już tyle DTM. Po co ostatecznie projektować nowy DTM?

Zgodnie z ogólną preambułą QTM, TM i NTM to różne rzeczy (podejmowanie ogromnych swobód przy zachowaniu wielu niewypowiedzianych założeń).

Zakładam, że wiesz, co to jest maszyna Turinga.

1. NTM jest TM, w której w dowolnym stanie, z dowolnym symbolem, funkcja przejścia może mieć wiele wyborów akcji, która nie jest dokładnie , tj. 0 lub więcej niż 1 (deterministyczna TM musi mieć dokładnie jedną akcję dla każdy symbol w każdym stanie, choć przypadek 0 jest łatwy do rozwiązania). W sytuacji, gdy istnieje kilka możliwości przejścia, NTM dokona wyboru, który ostatecznie doprowadzi go do stanu akceptacji, jeśli taka opcja istnieje. W przeciwieństwie do tego QTM to model obliczeń kwantowych , jak szczegółowo opisano w łączonym wątku. To nie$1$ $0$$1$$0$
   
   niedeterministyczne, nie wszystkie. Prawdopodobnie kluczowymi różnicami wysokiego poziomu między QTM a TM jest to, że QTM ma w swoim stanie liniową kombinację stanów bazowych (znowu, to wszystko w tym drugim wątku) i że jest probabilistyczny, to znaczy, dokładność swojego wyjścia jest ograniczone przez pewne prawdopodobieństwo mniejsze niż (ogólnie). Aby być naprawdę jasnym w kwestii, która chwyta wielu ludzi, niedeterminizm nie jest przypadkiem, nie jest równoległością, to teoretyczna konstrukcja, która nie ma nic wspólnego z żadnym z nich. $1$
   
   
2. Pełna odpowiedź na to pytanie zależy od pewnych teoretycznych założeń złożoności. Biorąc pod uwagę szczególne stanowisko (że i N P ⊃ P ), odpowiedź brzmi „tak”. N P pełnoporcjowych problemy mogą być rozwiązane przez NTM w czasie wielomianowym, i wydaje się także, że N P -Complete ∩ B P P = ∅ , a więc nie może być rozwiązany przez QTM w czasie wielomianowym. Znowu wszystko zależy od tego, w jaki sposób wypadają karty z różnymi klasami złożoności. Jeśli okaże się, że Q M A = $QMA \supset BQP$$NP \supset P$$NP$$NP\text{-complete} \cap BQP = \emptyset$
   
   , na przykład odpowiedź brzmi „nie”. $QMA = BQP$
3. Pierwszą rzeczą do powiedzenia tutaj jest ostrożność przy myleniu baz TM (dowolnego rodzaju) i komputerów. TM nie jest komputerem, QTM nie jest komputerem kwantowym. Obliczenia modeli TM (dowolnego rodzaju). To, co może zrobić dany komputer, jest przez to regulowane, ale jest to zupełnie inne niż stwierdzenie, że to, co wpisuję, to TM.
   
   Powiedziawszy to, jeśli mówimy luźno i leniwie identyfikujemy QTM z komputerami kwantowymi i TM ze standardowymi komputerami, to (ponownie przy pewnych założeniach złożoności) wydaje się, że komputery kwantowe mogą szybko wykonać pewne zadania, które wydają się trudne dla standardowych komputerów (faktoring, dyskretne dzienniki , naprawdę szczególny rodzaj wyszukiwania i kilka innych). Jednak te problemy nie znane są trudne w $NP$-Complete sens albo wydaje komputery kwantowe oferują funkcje, które rozszerzają standardową komputera, ale w innym kierunku, co będzie potrzebne, aby rozwiązać -Complete problemy szybko. $NP$

Ponownie, żeby być naprawdę jasnym, przejrzałem tutaj dużo złożoności obliczeniowej, jeśli naprawdę chcesz zrozumieć, jak wszystko do siebie pasuje, musisz zacząć zagłębiać się w literaturę.

O znaczeniu niedeterminizmu

Istnieją tutaj dwa różne znaczenia „niedeterminizmu”. Mechanika kwantowa jest zwykle opisywana jako „niedeterministyczna”, ale słowo „niedeterministyczny” jest używane w specjalistyczny sposób w informatyce teoretycznej.

1. Jedno znaczenie, które dotyczy mechaniki kwantowej, jest po prostu „nie deterministyczne ”. Jest to zwykle rozsądny sposób interpretacji tego słowa, aw rzeczywistości ani kwantowe maszyny Turinga, ani nawet probabilistyczne maszyny Turinga nie są deterministyczne w sposobie rozwiązywania problemów decyzyjnych.

2. Jednak przy opisywaniu modeli obliczeniowych niedeterministyczny jest używany konkretnie w celu oznaczenia, że ​​maszyna może (w pewnym sensie) dokonywać wyborów, które nie są określone przez jej stan lub dane wejściowe, w celu osiągnięcia określonego celu. To znaczenie jest używane gdzie indziej w opisie modeli obliczeniowych, takich jak niedeterministyczne automaty skończone .

Zatem kwantowe maszyny Turinga są modelem obliczeniowym, który nie jest deterministyczny, ale różni się od „ niedeterministycznej maszyny Turinga ”.

Niedeterministyczne maszyny Turinga

Niedeterministyczna maszyna Turinga to maszyna, która może badać wiele możliwych przejść. Przejście, które dokonuje na danym etapie, zależy, ale nie jest określone, od stanu, w którym się znajduje, i od symbolu, który czyta. Są dwa sposoby, w jakie jest to powszechnie przedstawiane:

• Zwłaszcza w celu zdefiniowania klasy złożoności NP można opisać maszynę jako dokonującą wyborów (lub zgadnięć) na każdym etapie, aby spróbować osiągnąć stan akceptacji. Jeśli myślisz o tym, co robi niedeterministyczna maszyna, badając drzewo decyzyjne, szuka ścieżki akceptacji w drzewie. Chociaż nie opisano żadnego mechanizmu sugerującego, w jaki sposób należy znaleźć taką ścieżkę, wyobrażamy sobie, że znajdzie ścieżkę akceptującą, jeśli choćby jedna z nich istnieje.

• Często mówi się również, że niedeterministyczna maszyna bada równolegle wszystkie możliwe ścieżki w drzewie decyzyjnym i daje odpowiedź „tak”, jeśli którakolwiek z nich okaże się ścieżką akceptującą.

Bardziej nowoczesne metody leczenia niedeterminizmu uwzględniają nie tylko istnienie, ale także liczbę ścieżek akceptacji; i to dobrze pasuje do opisu eksploracji wszystkich ścieżek równolegle. Możemy nałożyć dodatkowe ograniczenia, na przykład, że wszystkie ścieżki obliczeniowe mają tę samą długość (że maszyna zawsze wykonuje tyle samo czasu na wykonanie obliczeń) i że każda ścieżka wykonuje przypuszczenie na każdym kroku lub co drugim kroku, nawet jeśli zgadywanie nie jest używane. Jeśli to zrobimy, możemy sformułować probabilistyczne modele obliczeń, takie jak losowe maszyny Turinga (motywujące klasy złożoności, takie jak BPP ), pod względem liczbyakceptowania ścieżek niedeterministycznej maszyny Turinga. Możemy również to odwrócić i opisać niedeterministyczne maszyny Turinga w kategoriach losowych komputerów, które mogą w jakiś sposób odróżnić wyniki o zerowym prawdopodobieństwie od tych, które mają niezerowe prawdopodobieństwo.

Maszyny kwantowe

Główna różnica między kwantową maszyną Turinga a niedeterministyczną polega na tym, że zamiast niedeterministycznego „wybierania” pojedynczego przejścia z dwóch lub więcej na każdym etapie, kwantowa maszyna Turinga przechodzi do superpozycji jednego lub więcej możliwych przejść. Pełny stan maszyny jest definiowany jako wektor jednostkowy w złożonej przestrzeni wektorowej, określony przez liniowe kombinacje stanów bazowych opisanych klasycznymi stanami taśmy, pozycją głowicy maszyny i „stanem wewnętrznym” głowicy maszyny . (Patrz np. Strona 9, definicja 3.2.2, teorii złożoności kwantowejpełny opis tego, w jaki sposób kwantowe maszyny Turinga dokonują przejść.) Warunek, w którym kwantowa maszyna Turinga przyjmuje dane wejściowe, jest również bardziej restrykcyjny i nieodłącznie wiąże się z prawdopodobieństwem, wymagającym znacznego prawdopodobieństwa zaobserwowania poprawnego wyniku w celu odniesienia sukcesu.

W rezultacie kwantowe maszyny Turinga różnią się od maszyn niedeterministycznych tym, że sposób ich przejścia nie jest całkowicie nieokreślony. Nawet jeśli przejście „wydaje się tajemnicze”, jest to również ten sam rodzaj ewolucji z czasem, który wskazuje nasza najlepsza teoria materii w prawdziwym świecie. Chociaż często opisuje się komputery kwantowe jako „eksplorację różnych ścieżek obliczeniowych równolegle”, nie jest to szczególnie przydatne: amplitudy na różnych ścieżkach oznaczają, że nie wszystkie mają takie samo znaczenie, a w przeciwieństwie do niedeterministycznych maszyn Turinga, nie wystarczy mieć niezerową amplitudę dla niektórych wyników; musi być możliwe uzyskanie bardzo dużego prawdopodobieństwa uzyskania poprawnego wyniku, takiego jak 2/3. (Klasa problemów BQPktóre kwantowa maszyna Turinga może skutecznie rozwiązać, wymaga luki prawdopodobieństwa tego samego rodzaju, co BPP w przypadku obliczeń losowych.) Ponadto, w przeciwieństwie do niedeterministycznych maszyn Turinga, kwantowa maszyna Turinga może przeszkadzać sobie nawzajem po ich podziale , co jest po prostu niemożliwe w typowym sformułowaniu niedeterministycznej maszyny Turinga (i sprawia, że ​​opis w kategoriach drzewa decyzyjnego jest mniej przydatny w pierwszej kolejności).

Porównanie dwóch modeli

Nie wiemy, czy jedna z tych maszyn jest mocniejsza od drugiej; różne sposoby, w jakie nie są deterministyczne, wydają się różne od siebie i trudne do porównania.

Jeśli chodzi o problemy, które każda maszyna może szybko zrobić, których druga nie może (o ile wiemy):

• Nie wiemy, w jaki sposób kwantowa maszyna Turinga mogłaby szybko rozwiązać problem ZADOWOLENIA . Niedeterministyczna maszyna Turinga może z łatwością.
• Prace Aaronsona i Archipova ( The Computational Complexity of Linear Optics ) sugerują, że niedeterministyczne maszyny Turinga nie są w stanie skutecznie symulować niektórych eksperymentów optyki liniowej, które mogłyby być symulowane przez kwantową maszynę Turinga.

Ale nawet jeśli ktoś pokaże, jak powiązać ze sobą dwa rodzaje maszyn - a nawet w bardzo mało prawdopodobnym scenariuszu, w którym ktoś pokazuje, że BQP  =  NP (problemy, które kwantowa maszyna Turinga i niedeterministyczna maszyna Turinga, mogą odpowiednio szybko rozwiązać ) - dwie maszyny, które definiują te modele obliczeń, różnią się od siebie.