У квантових обчисленнях квантовий алгоритм — це алгоритм, який працює на основі реалістичної моделі квантового обчислення, причому найчастіше використовують модель обчислення квантової схеми. Класичний (або неквантовий) алгоритм — це скінченна послідовність інструкцій або покрокова процедура розв'язання задачі, де кожен крок або інструкцію можна виконати на класичному комп'ютері. Подібно, квантовий алгоритм — це покрокова процедура, де кожен із кроків можна виконати на квантовому комп'ютері. Хоча всі класичні алгоритми також можна виконувати на квантовому комп'ютері, термін квантовий алгоритм, як правило, застосовують до алгоритмів, які за своєю суттю є квантовими або використовують деякі істотні властивості квантового обчислення, такі як квантова суперпозиція або квантова сплутаність.

Задачі, які неможливо розв'язати за допомогою класичних комп'ютерів, залишаються нерозв'язними за допомогою квантових комп'ютерів. Цікавими квантові алгоритми робить те, що вони можуть розв'язувати деякі задачі швидше, ніж класичні алгоритми, оскільки квантову суперпозицію та квантову сплутаність, які, як правило, використовують квантові алгоритми, неможливо ефективно змоделювати на класичних комп'ютерах (див. Квантова перевага).

Найвідомішими алгоритмами є алгоритм Шора для факторизації та алгоритм Ґровера для пошуку в неструктурованій базі даних або невпорядкованому списку. Алгоритм Шора працює набагато (майже експоненціально) швидше, ніж найвідоміший класичний алгоритм розкладання на множники — решето числового поля. Алгоритм Гровера працює квадратично швидше, ніж найкращий можливий класичний алгоритм для цієї задачі — лінійний пошук.

Огляд Квантові алгоритми зазвичай описують у загальновживаній схемній моделі квантового обчислення за допомогою квантової схеми, яка діє на деякі вхідні кубіти та завершується вимірюванням. Квантова схема складається з простих квантових вентилів, кожен з яких діє на деяку скінченну кількість кубітів. Квантові алгоритми також можна викласти в інших моделях квантових обчислень, таких як модель гамільтонового оракула.

Квантові алгоритми можна класифікувати за основними техніками, задіяними в алгоритмі. Деякі методи/ідеї, які зазвичай використовують у квантових алгоритмах: фазовий відкіт, , квантове , , та . Квантові алгоритми також можна згрупувати за типом розв'язуваної задачі (див., наприклад, огляд квантових алгоритмів для алгебричних задач).

Алгоритми на основі квантового перетворення Фур'є є квантовим аналогом дискретного перетворення Фур'є та використовується в кількох квантових алгоритмах. Перетворення Адамара є прикладом квантового перетворення Фур'є над n-вимірним векторним простором над полем . Квантове перетворення Фур'є можна ефективно реалізувати на квантовому комп'ютері, використовуючи лише поліноміальну кількість квантових вентилів.

Алгоритм Дойча — Йожи

Алгоритм Дойча — Йожи розв'язує задачу чорної скриньки, яка вимагає експоненціальної кількості запитів до чорної скриньки для будь-якого детермінованого класичного комп'ютера, але може бути розв'язана за допомогою одного запиту квантовим комп'ютером. Однак при порівнянні класичних із обмеженою помилкою і квантових алгоритмів прискорення не відбувається, оскільки класичний імовірнісний алгоритм може розв'язати задачу з постійною кількістю запитів із малою ймовірністю помилки. Алгоритм визначає, чи є функція f сталою (0 для всіх входів або 1 для всіх входів), чи збалансованою (повертає 1 для половини вхідної області та 0 для іншої половини).

Алгоритм Бернштейна — Вазірані

Алгоритм Бернштейна — Вазірані є першим квантовим алгоритмом, який розв'язує задачу ефективніше, ніж найвідоміший класичний алгоритм. Його розробили, щоб створити оракул поділу між і BPP.

Алгоритм Саймона Алгоритм Саймона вирішує проблему чорної скриньки експоненціально швидше, ніж будь-який класичний алгоритм, включно з імовірнісними алгоритмами з обмеженою помилкою. Цей алгоритм став мотивацією для алгоритму Шора для факторизації.

Алгоритм оцінки квантової фази

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

Алгоритм Шора

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

Задача прихованої підгрупи Задача абелевої прихованої підгрупи є узагальненням багатьох задач, які можна розв'язати квантовим комп'ютером, таких як задача Саймона, розв'язування рівняння Пелля, перевірка головного ідеалу кільця R і розкладання на множники. Для задачі існують ефективні квантові алгоритми. Загальніша задача прихованої підгрупи, де група не обов'язково є абелевою, є узагальненням згаданих раніше задач, а також ізоморфізму графів і певних задач теорії ґраток. Для деяких неабелевих груп відомі ефективні квантові алгоритми. Однак не відомі ефективні алгоритми для симетричної групи, які б дали ефективний алгоритм для ізоморфізму графа, та діедричної групи, які б розв'язали деякі задачі теорії ґраток.

Оцінювання сум Гаусса Сума Гаусса — різновид експоненційної суми. Найвідоміший класичний алгоритм для оцінення цих сум вимагає експоненційного часу. Оскільки задача обчислення дискретного логарифму зводиться до оцінення суми Гаусса, ефективний класичний алгоритм для оцінення суми Гаусса означатиме ефективний класичний алгоритм для обчислення дискретних логарифмів, що вважається малоймовірним. Однак квантові комп'ютери можуть оцінювати суми Гауса з поліноміальною точністю за поліноміальний час.

Фур'є-лов і перевірка Фур'є Розглянемо пророчу машину, що складається з n випадкових булевих функцій, які відображають n-розрядні рядки в логічне значення, з метою пошуку n n-бітових рядків z1,…,z n так, що для перетворення Адамара — Фур'є принаймні 3/4 рядків задовольняють

і принаймні 1/4 задовольняють

Це можна зробити за (BQP).

Алгоритми на основі посилення амплітуди  — це техніка, яка дозволяє посилювати вибраний підпростір квантового стану. Застосування посилення амплітуди зазвичай приводить до квадратичного прискорення порівняно з відповідними класичними алгоритмами. Його можна розглядати як узагальнення алгоритму Ґровера.

Алгоритм Ґровера Алгоритм Ґровера шукає позначений запис у неструктурованій базі даних (або невпорядкованому списку) з N записів, використовуючи лише запитів замість класично необхідних запитів. Класично, потрібно запитів, навіть якщо допускаються ймовірнісні алгоритми з обмеженою помилкою.

Теоретики розглядали гіпотетичне узагальнення стандартного квантового комп'ютера, який міг би отримати доступ до історії прихованих змінних у механіці Бома. (Такий комп'ютер є повністю гіпотетичним і не був би стандартним квантовим комп'ютером або навіть можливим за стандартною теорією квантової механіки.) Такий гіпотетичний комп'ютер міг би здійснювати пошук у базі даних з N елементів щонайбільше за кроків. Це трохи швидше, ніж кроків, які дає алгоритм Ґровера. Однак жоден метод пошуку не дозволить жодній моделі квантового комп'ютера розв'язувати NP-повні задачі за поліноміальний час.

Квантовий підрахунок розв'язує узагальнення задачі пошуку — підрахунок кількості позначених записів у невпорядкованому списку, замість того, щоб просто визначити, чи такі існують. Зокрема, він підраховує кількість позначених записів у списку з елементів із похибкою щонайбільше після тільки запитів, де  — кількість позначених елементів у списку. Точніше, алгоритм видає оцінку для , кількості позначених записів, з точністю .

Алгоритми на основі квантових блукань

Квантове блукання — це квантовий аналог класичного випадкового блукання. Класичне випадкове блукання можна описати розподілом імовірностей за деякими станами, тоді як квантове блукання можна описати квантовою суперпозицією за станами. Відомо, що квантові блукання дають для деяких задач чорної скриньки експоненційне прискорення. Вони також забезпечують поліноміальне прискорення для багатьох задач. Існує універсальний програмний каркас для створення алгоритмів квантового блукання.

Задача вибірки бозона

Задача вибірки бозонів в експериментальній конфігурації припускає введення помірної кількості бозонів (наприклад, фотонів), які випадковим чином розкидані у великій кількості вихідних мод, обмежених визначеною унітарністю. За використання окремих фотонів, задача ізоморфна багатофотонному квантовому блуканню. Тоді вона полягає в тому, щоб створити досить добру вибірку розподілу ймовірностей результату, який залежить від вхідного розташування бозонів і унітарності. Розв'язання цієї задачі за допомогою класичного комп'ютерного алгоритму вимагає обчислення перманента унітарної матриці перетворення, що може зайняти надзвичайно багато часу або бути абсолютно неможливим. 2014 року запропоновано, що існуючу технологію та стандартні ймовірнісні методи генерування однофотонних станів можна використати як вхідні дані у відповідну квантово обчислювану лінійну оптичну мережу, і що квантові алгоритми дадуть явно кращу дискретизацію розподілу вихідної ймовірності. 2015 року дослідження передбачило, що задача вибірки мала подібну складність для вхідних даних, крім фотонів у стані Фока, і виявила перехід від класично модельованої до такої ж складної, як задача бозонної вибірки, залежно від розміру когерентних амплітудних входів.

Задача відмінності елементів Задача відмінності елементів полягає у визначенні, чи всі елементи списку є різними. Класично, для списку розміру потрібні запитів; однак на квантовому комп'ютері її можна розв'язати за запитів. Оптимальний алгоритм запропонував Андріс Амбайніс, а Яоюнь Ши вперше довів жорстку нижню межу, коли розмір діапазону достатньо великий. Амбайніс і Кутін, незалежно один від одного (і за допомогою різних доведень), розширили цю роботу, щоб отримати нижню межу для всіх функцій.

Задача знаходження трикутника Задача знаходження трикутника полягає у визначенні, чи містить даний граф трикутник (кліку розміром 3). Найвідомішою нижньою межею для квантових алгоритмів є , але найкращий відомий алгоритм потребує O(N1,297) запитів, що краще, порівняно з попередніми найкращими O(N1,3) запитами.

Оцінення формул Формула — це дерево з вентилем у кожному внутрішньому вузлі та вхідним бітом у кожному листовому вузлі. Задача полягає в тому, щоб оцінити формулу, яка є виходом кореневого вузла, отримавши доступ оракула до вхідних даних.

Добре вивченою формулою є збалансоване бінарне дерево лише з вентилями NAND. Цей тип формули вимагає запитів з використанням випадковості, де . Однак, за допомогою квантового алгоритму це можна розв'язати за запитів. Кращого квантового алгоритму для цього випадку не було відомо, поки його не було знайдено для нетрадиційної моделі гамільтонівського оракула. Невдовзі з'явився такий самий результат для стандартного налаштування.

Відомі також швидкі квантові алгоритми для складніших формул.

Комутативність групи

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

BQP-повні задачі