га: будь-яка функція, яка може бути обчислена фізичним пристроєм, може бути обчислена машиною Тьюринга. Проблеми, які є нерозв'язними, що не розв'язні за поліноміальний час на сучасних комп'ютерах і залишаться нерозв'язними на всіх майбутніх класичних комп'ютерах. До прикладів таких проблем відносяться факторизація, оптимізація подорожі комівояжера, задача про приховані підгрупах і т.д.
Алгоритм Deutsch-Josza
квантовий комп'ютер кубіт алгоритм
У 1992р. D. Deutsch і R. Jozsa запропонували гіпотетичну проблему, а також алгоритм її вирішення, який показує, чт?? комп'ютер, який використовує квантові стани для обчислень міг би не підкорятися обмеженню, накладеному тезою Черча-Тьюринга [Deutsch і Jozsa, 1992]. Проблема - визначення природи невідомої функції питаннями оракула, який оцінює функцію для даного входу. Функція діє на число n- бітове і, як відомо, результат або постійний, тобто 0 (або 1) для всіх можливих входів, або врівноважений, тобто повертається 0 для точно половини всіх можливих входів і 1 для всіх інших. Класичний комп'ютер, в гіршому випадку, мав би оцінити функцію 2 в ступені (n - 1) + 1 раз, в той час як квантовий комп'ютер повинен буде оцінити функцію тільки одного разу, щоб визначити з упевненістю результат буде урівноважений або постійний. Це зроблено однією оцінкою значення функції, якщо стан на вході являє собою суперпозицію всіх можливих 2 в ступені n станів, одержуваних застосуванням оператора Адамара. Якщо на виході результат показує амплітуди і для 0, і для 1, то функція урівноважена (збалансована), в іншому випадку - постійна. Цей алгоритм передбачає, що квантовий комп'ютер міг би бути нескінченно швидше, ніж будь-який можливий класичний комп'ютер для певних класів проблем, які дуже важкі для класичних комп'ютерів.
