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