Математичний результат засвідчує: навіть нескінченно швидший класичний комп’ютер не міг би зрівнятися з квантовим.
Два математики виявили проблему, яку не в силі розв’язати класичний комп’ютер, навіть значно потужніший, ніж сучасний. Однак ця проблема цілком під силу квантовому комп’ютерові. Так учені продемонстрували, що квантовий комп’ютер не лише потужніший, а й кращий у всіх планах.
Ран Рац (Ran Raz) з Науково-дослідного інституту імені Вейцмана (Ізраїль) та Авішей Тал (Avishay Tal) зі Стенфордського університету (США) повідомили: на питання, чи дві послідовності здавалося б випадкових чисел мають приховану спільність, можна відповісти з допомогою квантових алгоритмів. Натомість класичний комп’ютер не зміг би навіть перевірити отриману відповідь. Згідно з описаними даними, квантовий комп’ютер – це насправді щось зовсім нове.
З ранніх 90-их років ХХ століття експерти ламають собі голову над цим питанням: чи справді квантовий комп’ютер відрізняється від класичного. Передумовою для пошуків відповіді є класи складності: PH [в теорії складності обчислень об'єднання всіх класів складності певної поліномиальної ієрархії], що охоплює класи Р [поліномічні: множина задач, час роботи яких поліноміально залежить від розміру вхідних даних] та NP [невизначено поліномічні: множина задач, розв'язання яких є можливим за наявності деяких додаткових відомостей], які міг би розв’язати гіпотетичний безкінечно потужніший класичний комп’ютер, і клас BQP [bounded error quantum polynomial time, квантовий аналог BPP, що шукають відповідь задачі з певною ймовірністю, що залежить від часу обчислення], який вже під силу реальному квантовому комп’ютерові.
Але чи є проблеми, що існують у BQP, проте не у PH? Рац і Тал сказали «так». Їхня нова публікація містить доказ, що проблема числової послідовності недоступна класичним методам, тож навіть на безкінечно потужному класичному комп’ютері її розв’язок тривав би вічно. Той факт, що для розв’язання проблеми вже існує квантовий алгоритм, простіше довести, позаяк це вже давно відомо.
З огляду на те, що час обрахунку, необхідний для розв’язання проблеми, теоретично визначити дуже складно, обидва вчених вдалися до хитрості й перевели час в іншу величину – необхідну додаткову інформацію.
Цей метод, який називається «методом оракула», вимірює кількість підказок, які потрібні комп’ютерові для того, щоб розв’язати проблему. Кількість цих підказок – міра необхідного часу обрахунків. Відповідно до отриманих даних класичний комп’ютер не зможе розв’язати завдання навіть з нескінченною кількістю підказок – натомість квантові алгоритми потребують лише одну.
Якщо результати підтвердяться, квантові комп'ютери будуть кращими, навіть якщо класичним комп'ютерам стануть під силу раніше недоступні проблеми, зокрема «задача комівояжера» або проблема факторизації цілих чисел у поширених алгоритмах шифрування.
Зображення: archy13/shutterstock.
Lars Fischer
Quantencomputer sind grundsätzlich anders
spektrum.de, 26.06.2018
Ran Raz, Avishay Tal
Oracle Separation of BQP and PH
Electronic Colloquium on Computational Complexity, Report No. 107 (2018)
Зреферувала С. К.
03.08.2018