Вступ
Квантові алгоритми забезпечують доведені переваги над класичними алгоритмами в моделі обчислень із запитами. Але як щодо більш стандартної моделі обчислень, де вхідні дані задачі подаються явно, а не у вигляді оракула чи чорного ящика? Це виявляється значно складнішим питанням, і щоб його вирішити, нам спочатку потрібно закласти міцне підґрунтя для дослідження. Саме цьому присвячений цей урок.
Ми розпочнемо з обговорення обчислювальної вартості — як для класичних, так і для квантових обчислень — та способів її вимірювання. Це загальне поняття, яке можна застосувати до широкого спектра обчислювальних задач, але для простоти ми розглянемо його здебільшого крізь призму обчислювальної теорії чисел, що охоплює задачі, які, ймовірно, знайомі більшості читачів: базову арифметику, обчислення найбільших спільних дільників та факторизацію цілих чисел. Хоча обчислювальна теорія чисел є вузькою прикладною областю, ці задачі добре ілюструють базові питання (і до того ж дуже актуальні для наступного уроку).
Ми зосередимося на алгоритмах, а не на постійно вдосконалюваному апаратному забезпеченні, на якому вони виконуються. Відповідно, нас більше цікавитиме, як зростає вартість виконання алгоритму зі збільшенням розміру задачі, ніж те, скільки секунд, хвилин чи годин займає конкретне обчислення. Ми зосереджуємося на цьому аспекті обчислювальної вартості, визнаючи фундаментальну важливість алгоритмів: вони природним чином застосовуватимуться до дедалі більших задач на швидшому та надійнішому апаратному забезпеченні в міру розвитку технологій.
Насамкінець ми звернемося до критично важливого завдання — виконання класичних обчислень на квантових комп'ютерах. Це завдання важливе не тому, що ми сподіваємося замінити класичні комп'ютери квантовими — що найближчим часом, якщо взагалі колись, навряд чи станеться, — а тому, що воно відкриває багато цікавих можливостей для квантових алгоритмів. Зокрема, класичні обчислення, що виконуються на квантових комп'ютерах, стають доступними як підпрограми, що фактично дає змогу задіяти десятиліття досліджень і розробок у галузі класичних алгоритмів у пошуку квантових обчислювальних переваг.
Відео до уроку
У наступному відео Джон Вотрус проведе тебе через зміст цього уроку про основи квантових алгоритмів. Також можна відкрити відео на YouTube в окремому вікні. Завантаж слайди до цього уроку.