Obliczenia kwantowe i maszyny Turinga: czy maszyny Turinga nadal są dokładnym miernikiem?

W zeszłym tygodniu na zajęciach mój profesor skomentował i powiedział, że maszyny Turinga są używane jako standardowa miara / model tego, co można obliczyć i są pomocną podstawą do dyskusji na ten temat. Powiedziała również, że wszystkie warianty maszyn Turinga są równoważne obliczeniowo - czytaj, tak samo potężne - jak siebie nawzajem. W.

Skomentowałem i powiedziałem wczoraj, że jeśli chodzi o moc obliczeniową, zauważyłem, że niektóre maszyny Turinga mogą obliczać coś bardzo prostego bardzo długo, podczas gdy maszyna Turinga z większą liczbą taśm może obliczyć coś o niższej asymptotycznej złożoności w odniesieniu do liczby wymaganych kroków.

Powiedziała, że ​​w odniesieniu do dyskursu klasowego czas wykonywania określonego algorytmu na maszynie Turinga nie zmienia definicji obliczalności ani mocy, z jaką mierzymy obliczalność. „Niepokoi nas to, co można w tej chwili obliczyć, a nie to, co w tej chwili jest wydajne.” Tak więc nie ma znaczenia, czy maszyny Turinga mają coraz więcej taśm, a coraz więcej taśm implikuje, że można wykonać obliczenia w mniejszych krokach. Ok, rozumiem, że naprawdę skupiamy się na tym, co jest obliczalne IS, a nie na szybkości, z jaką możemy to obliczyć.

Coś mi w tym przeszkadza, ponieważ do tego momentu algorytmy o niezwykle dużej asymptotycznej złożoności czasu i przestrzeni naprawdę określają granice tego, co, może powinienem powiedzieć, praktycznie obliczalnego.

Mam więc kilka pytań:

1. Załóżmy, że mamy model kwantowej maszyny Turinga , musi to być odpowiednik „zwykłej” maszyny Turinga, prawda?

Tak więc odpowiedź na to pytanie, jak sądzę, naprawdę zmierza w kierunku mojego powodu napisania tego postu. Czy technologia obliczeń kwantowych przestaje odpowiadać klasycznym definicjom tego, co można obliczać za pomocą maszyny Turinga?

2. Czy to coś nad moją głową i czy powinienem usunąć ten post? Nie chcę być przedwczesny, po prostu nie widziałem pytania podobnego do mojego.

Jesteś mieszanie się teoria obliczalności (znany również jako teorii rekursji ) i teorii złożoności (lub złożoności obliczeniowej ). Teoria obliczalności jest obszernym przedmiotem matematycznym, który bada konsekwencje koncepcji obliczeń . Nie zajmuje się złożonością obliczeń. Jak wspomina profesor, wszystkie modele obliczeniowe (kompletne Turinga) są takie same z punktu widzenia teorii obliczalności. Jak wspominasz, teoria obliczeń, choć interesujący przedmiot matematyczny, nie jest dobrym modelem do obliczeń w świecie rzeczywistym.

$T(n)$$S(n)$$T(n)^c$$S(n)^c$$n$$c$$O(1)$$O(n\log n)$$\Omega(n^2)$lub poruszaj się nawet po sortowaniu liczb całkowitych. Dlatego w obszarze algorytmów inne modele, takie jak pamięć RAM, zastępują maszyny Turinga.

Wreszcie komputery kwantowe można modelować na kilka różnych sposobów, na przykład kwantową maszynę Turinga. Wszystko, co można obliczać za pomocą komputerów kwantowych, można również obliczać za pomocą komputerów klasycznych, a zatem z punktu widzenia teorii obliczalności maszyny kwantowe Turinga to tylko kolejny równoważny model. Jednak kwantowe maszyny Turinga są powszechnie przypuszczane, że nie są wielomianowo równoważne z klasycznymi maszynami Turinga: na przykład faktoring i logarytm dyskretny są „łatwe” dla kwantowych maszyn Turinga (możliwe do rozwiązania w czasie wielomianowym), podczas gdy przypuszcza się, że są „twarde” dla klasycznych maszyn Turinga (nie da się tego rozwiązać w czasie wielomianowym; choć niektórzy sądzą, że faktoring całkowity może być rozwiązany w czasie wielomianowym). Tak więc z punktu widzenia teorii złożoności kwantowe maszyny Turinga różni się od klasycznych maszyn Turinga.