Powszechnie panuje błędne przekonanie, że komputery kwantowe pod względem osiąganej złożoności są równoważne niedeterministycznym maszynom Turinga. Jednak do tej pory nie są znane metody rozwiązywania problemów NP-zupełnych na komputerach kwantowych w czasie wielomianowym. Na przykład kwantowy algorytm faktoryzacji Shora pozwala rozwiązać problem faktoryzacji całkowitej w czasie wielomianowym, jednak nie ma dowodów na to, że faktoryzacja jest NP-zupełna. A więc nie wynika z tego, że komputery kwantowe mogą w ogólności rozwiązywać problemy NP w czasie wielomianowym.
Zobacz też Maszyna Turinga z wyrocznią Maszyna Turinga
Przypisy
Bibliografia
Kategoria:Teoria obliczeń