Вступ

У цьому першому уроці курсу ми сформулюємо просту алгоритмічну схему — відому як модель запитів — і дослідимо переваги, які квантові комп'ютери пропонують у рамках цієї схеми.

Модель обчислень на основі запитів — це наче чашка Петрі для квантових алгоритмічних ідей. Вона є жорсткою та штучною в тому сенсі, що не відображає точно ті обчислювальні задачі, які нас зазвичай цікавлять на практиці, проте вона виявилася надзвичайно корисним інструментом для розробки квантових алгоритмічних технік. Це стосується і тих, на яких ґрунтуються найвідоміші квантові алгоритми, наприклад алгоритм Шора для факторизації цілих чисел. Модель запитів також є дуже зручною схемою для пояснення квантових алгоритмічних технік.

Після введення самої моделі запитів ми розглянемо перший відкритий квантовий алгоритм — алгоритм Дойча — а також його розширення, відоме як алгоритм Дойча–Йожі. Ці алгоритми демонструють кількісно вимірювані переваги квантових комп'ютерів над класичними в контексті моделі запитів. Потім ми обговоримо квантовий алгоритм, відомий як алгоритм Саймона, що дає більш надійну (стійку) і переконливу перевагу квантових обчислень над класичними з причин, які будуть пояснені, коли ми до нього дійдемо.

Відео уроку

У наступному відео Джон Уотрус крок за кроком пояснює зміст цього уроку про квантові алгоритми на основі запитів. Також можна відкрити відео на YouTube в окремому вікні. Завантажити слайди до цього уроку.