Квантовий алгоритм

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

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

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

Огляд

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

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

Алгоритми на основі квантового перетворення Фур'є

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

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

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

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

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

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

Алгоритм Саймона

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

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

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

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

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

Задача прихованої підгрупи

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

Оцінювання сум Гаусса

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

Фур'є-лов і перевірка Фур'є

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

$|{\tilde {f}}(z_{i})|\geqslant 1$

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

$|{\tilde {f}}(z_{i})|\geqslant 2.$

Це можна зробити за квантовий поліноміальний час із обмеженою помилкою (BQP).

Алгоритми на основі посилення амплітуди

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

Алгоритм Ґровера

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

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

Квантовий підрахунок

Квантовий підрахунок розв'язує узагальнення задачі пошуку — підрахунок кількості позначених записів у невпорядкованому списку, замість того, щоб просто визначити, чи такі існують. Зокрема, він підраховує кількість позначених записів у списку з $N$ елементів із похибкою щонайбільше $\varepsilon$ після тільки $\Theta \left(\varepsilon ^{-1}{\sqrt {N/k}}\right)$ запитів, де $k$ — кількість позначених елементів у списку. Точніше, алгоритм видає оцінку $k'$ для $k$, кількості позначених записів, з точністю $|k-k'|\leq \varepsilon k$.

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

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

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

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

Задача відмінності елементів

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

Задача знаходження трикутника

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

Оцінення формул

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

Добре вивченою формулою є збалансоване бінарне дерево лише з вентилями NAND. Цей тип формули вимагає $\Theta (N^{c})$ запитів з використанням випадковості, де $c=\log _{2}(1+{\sqrt {33}})/4\approx 0.754$. Однак, за допомогою квантового алгоритму це можна розв'язати за $\Theta (N^{1/2})$ запитів. Кращого квантового алгоритму для цього випадку не було відомо, поки його не було знайдено для нетрадиційної моделі гамільтонівського оракула. Невдовзі з'явився такий самий результат для стандартного налаштування.

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

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

Проблема полягає в тому, щоб визначити, чи є група чорної скриньки, задана k генераторами, комутативною. Група чорної скриньки — це група з функцією оракула, яка повинна використовуватися для виконання групових операцій (множення, інверсії та порівняння з тотожністю). Цікавість у цьому контексті полягає в складності запиту, яка дорівнює кількості викликів оракула, необхідних для розв'язання задачі. Складність детермінованих і рандомізованих запитів $\Theta (k^{2})$ і $\Theta (k)$ відповідно. Квантовий алгоритм потребує $\Omega (k^{2/3})$ запитів, тоді як найвідоміший класичний алгоритм використовує $O(k^{2/3}\log k)$ запитів.

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

Клас складності BQP (квантовий поліноміальний час з обмеженою помилкою) — це набір задач прийняття рішення, які квантовий комп'ютер розв'язує за поліноміальний час з імовірністю помилки не більше 1/3 для всіх випадків. Це квантовий аналог класичного класу складності BPP. .

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

Обчислення інваріантів вузла

Віттен показав, що топологічну квантову теорію поля Черна — Саймонса (ТКТП) можна розв'язати в термінах многочленів Джонса. Квантовий комп'ютер може симулювати ТКТП і, завдяки цьому, апроксимувати многочлен Джонса, який, наскільки відомо, у найгіршому випадку складно обчислити класичним способом.^{[джерело?]}

Квантова симуляція

Ідея про те, що квантові комп'ютери можуть бути потужнішими за класичні комп'ютери, виникла в спостереженні Річарда Фейнмана про те, що класичним комп'ютерам, схоже, потрібен експоненційний час для моделювання багаточастинкових квантових систем, але квантові системи багатьох тіл здатні «розв'язувати самі себе». Відтоді ідею про те, що квантові комп'ютери можуть симулювати квантові фізичні процеси експоненційно швидше, ніж класичні комп'ютери, значно конкретизовано та розроблено. Використовуючи лише кілька сотень кубітів, розроблено ефективні (тобто з поліноміальним часом) квантові алгоритми для моделювання як бозонних, так і ферміонних систем, а також для моделювання хімічних реакцій, що виходить за межі можливостей сучасних класичних суперкомп'ютерів. Квантові комп'ютери також можуть ефективно симулювати топологічні квантові теорії поля. Окрім внутрішнього інтересу, цей результат призвів до ефективних квантових алгоритмів для оцінення квантових топологічних інваріантів, таких як многочлени Джонса і HOMFLY та інваріант Тураєва — Віро тривимірних многовидів.

Розв'язування систем лінійних рівнянь

2009 року Арам Гарроу, Авінатан Хасідім і Сет Ллойд сформулювали квантовий алгоритм для розв'язання систем лінійних рівнянь. Алгоритм оцінює результат скалярного вимірювання вектора розв'язку заданої лінійної системи рівнянь.

За умови, що лінійна система є розрідженою та має низьке число обумовленості $\kappa$ і що користувача цікавить результат скалярного вимірювання вектора розв'язку (замість значень самого вектора розв'язку), алгоритм має час виконання $O(\log(N)\kappa ^{2})$, де $N$ — кількість змінних у лінійній системі. Це забезпечує експоненційне прискорення порівняно з найшвидшим класичним алгоритмом, який виконується за $O(N\kappa )$ (або $O(N{\sqrt {\kappa }})$ для додатних напіввизначених матриць).

Гібридні квантові/класичні алгоритми

Гібридні квантові/класичні алгоритми поєднують підготовку квантового стану та вимірювання з класичною оптимізацією. Ці алгоритми зазвичай спрямовані на визначення власного вектора основного стану та власного значення ермітового оператора.

QAOA

Алгоритм квантової наближеної оптимізації нагадує квантовий відпал, виконуючи дискретизоване наближення квантового відпалу за допомогою квантової схеми. Його можна використовувати для розв'язування задач із теорії графів. Для максимізації «цільової функції» алгоритм використовує класичну оптимізацію квантових операцій.

Варіаційний квантовий власний розв'язувач

Алгоритм варіаційного квантового власного розв’язувача (VQE) застосовує класичну оптимізацію, щоб мінімізувати очікуване енергетичне значення анзац-стану, щоб знайти основний стан ермітового оператора, наприклад гамільтоніана молекули. Його також можна розширити, щоб знайти збуджені енергії молекулярних гамільтоніанів.

Скорочений квантовий власний розв'язувач

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

Див. також

• Квантове машинне навчання
• Алгоритми квантової оптимізації
• Квантове сортування
• Тест простоти

Посилання

• Зоопарк квантових алгоритмів: вичерпний список квантових алгоритмів, які забезпечують прискорення порівняно з найшвидшими відомими класичними алгоритмами. (англ.)
• Конспекти лекцій Ендрю Чайлдса про квантові алгоритми (англ.)
• Алгоритм квантового пошуку — груба сила [Архівовано 1 September 2018 у Wayback Machine.] .

Огляди

• Dalzell, Alexander M.; McArdle, Sam (2023). Quantum algorithms: A survey of applications and end-to-end complexities. arXiv:2310.03011 [quant-ph].
• Smith, J.; Mosca, M. (2012). Algorithms for Quantum Computers. Handbook of Natural Computing. с. 1451—1492. arXiv:1001.0767. doi:10.1007/978-3-540-92910-9_43. ISBN 978-3-540-92909-3.
• Childs, A. M.; Van Dam, W. (2010). Quantum algorithms for algebraic problems. Reviews of Modern Physics. 82 (1): 1—52. arXiv:0812.0380. Bibcode:2010RvMP...82....1C. doi:10.1103/RevModPhys.82.1.