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

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

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

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

Огляд

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

QAOA

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

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

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

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

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

Див. також

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

Примітки

1. Nielsen, Michael A.; Chuang, Isaac L. (2000). Quantum Computation and Quantum Information. Cambridge University Press. ISBN 978-0-521-63503-5.
2. Mosca, M. (2008). Quantum Algorithms. arXiv:0808.0369 [quant-ph].
3. Lanzagorta, Marco; Uhlmann, Jeffrey K. (1 січня 2009). Quantum Computer Science. Morgan & Claypool Publishers. ISBN 9781598297324.
4. Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantum Computation and Quantum Information (вид. 2nd). Cambridge: Cambridge University Press. ISBN 978-1-107-00217-3.
5. Shor's algorithm. Архів оригіналу за 12 січня 2023. Процитовано 26 серпня 2024.
6. IBM quantum composer user guide: Grover's algorithm. quantum-computing.ibm.com. Процитовано 7 червня 2022.
7. Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (2008). A Quantum Algorithm for the Hamiltonian NAND Tree. Theory of Computing. 4: 169—190. arXiv:quant-ph/0702144. doi:10.4086/toc.2008.v004a008.
8. Childs, Andrew 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.
9. Shor, P. W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Scientific and Statistical Computing. 26 (5): 1484—1509. arXiv:quant-ph/9508027. Bibcode:1995quant.ph..8027S. doi:10.1137/s0097539795293172.
10. Boneh, D.; Lipton, R. J. (1995). Quantum cryptoanalysis of hidden linear functions. У Coppersmith, D. (ред.). Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology. Springer-Verlag. с. 424—437. ISBN 3-540-60221-6.
11. Moore, C.; Russell, A. The Symmetric Group Defies Strong Fourier Sampling: Part I. arXiv:quant-ph/0501056.
12. Regev, O. (2003). Quantum Computation and Lattice Problems. arXiv:cs/0304005.
13. van Dam, W.; Seroussi, G. Efficient Quantum Algorithms for Estimating Gauss Sums. arXiv:quant-ph/0207131.
14. Aaronson, S. BQP and the Polynomial Hierarchy. arXiv:0910.4698 [quant-ph].
15. Grover, Lov K. (1996). A fast quantum mechanical algorithm for database search. arXiv:quant-ph/9605043.
16. Aaronson, Scott. Quantum Computing and Hidden Variables (PDF).
17. Brassard, G.; Hoyer, P.; Tapp, A. (1998). Quantum counting. Automata, Languages and Programming. Lecture Notes in Computer Science. Т. 1443. с. 820—831. arXiv:quant-ph/9805082. doi:10.1007/BFb0055105. ISBN 978-3-540-64781-2.
18. Brassard, G.; Hoyer, P.; Mosca, M.; Tapp, A. (2002). Quantum Amplitude Amplification and Estimation. У Samuel J. Lomonaco, Jr. (ред.). Quantum Computation and Quantum Information. AMS Contemporary Mathematics. Т. 305. с. 53—74. arXiv:quant-ph/0005055. Bibcode:2000quant.ph..5055B. doi:10.1090/conm/305/05215. ISBN 9780821821404.
19. Childs, A. M.; Cleve, R.; Deotto, E.; Farhi, E.; Gutmann, S.; Spielman, D. A. (2003). Exponential algorithmic speedup by quantum walk. Proceedings of the 35th Symposium on Theory of Computing. Association for Computing Machinery. с. 59—68. arXiv:quant-ph/0209131. doi:10.1145/780542.780552. ISBN 1-58113-674-9.
20. Childs, A. M.; Schulman, L. J.; Vazirani, U. V. (2007). Quantum Algorithms for Hidden Nonlinear Structures. Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science. IEEE. с. 395—404. arXiv:0705.2784. doi:10.1109/FOCS.2007.18. ISBN 978-0-7695-3010-9.
21. Magniez, F.; Nayak, A.; Roland, J.; Santha, M. (2007). Search via quantum walk. Proceedings of the 39th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery. с. 575—584. arXiv:quant-ph/0608026. doi:10.1145/1250790.1250874. ISBN 978-1-59593-631-8.
22. Ralph, T.C. (July 2013). Figure 1: The boson-sampling problem. Nature Photonics. Nature. 7 (7): 514—515. doi:10.1038/nphoton.2013.175. Процитовано 12 вересня 2014.
23. Peruzzo, Alberto; Lobino, Mirko; Matthews, Jonathan C. F.; Matsuda, Nobuyuki; Politi, Alberto; Poulios, Konstantinos; Zhou, Xiao-Qi; Lahini, Yoav; Ismail, Nur (17 вересня 2010). Quantum Walks of Correlated Photons. Science (англ.). 329 (5998): 1500—1503. arXiv:1006.4764. Bibcode:2010Sci...329.1500P. doi:10.1126/science.1193515. ISSN 0036-8075. PMID 20847264.
24. Lund, A.P.; Laing, A.; Rahimi-Keshari, S.; Rudolph, T.; O'Brien, J.L.; Ralph, T.C. (5 вересня 2014). Boson Sampling from Gaussian States. Phys. Rev. Lett. 113 (10): 100502. arXiv:1305.4346. Bibcode:2014PhRvL.113j0502L. doi:10.1103/PhysRevLett.113.100502. PMID 25238340.
25. The quantum revolution is a step closer. Phys.org. Omicron Technology Limited. Процитовано 12 вересня 2014.
26. Seshadreesan, Kaushik P.; Olson, Jonathan P.; Motes, Keith R.; Rohde, Peter P.; Dowling, Jonathan P. (2015). Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states: The quantum-classical divide and computational-complexity transitions in linear optics. Physical Review A. 91 (2): 022334. arXiv:1402.0531. Bibcode:2015PhRvA..91b2334S. doi:10.1103/PhysRevA.91.022334.
27. Ambainis, A. (2007). Quantum Walk Algorithm for Element Distinctness. SIAM Journal on Computing(інші мови). 37 (1): 210—239. arXiv:quant-ph/0311001. doi:10.1137/S0097539705447311.
28. Shi, Y. (2002). Quantum lower bounds for the collision and the element distinctness problems. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. Proceedings of the 43rd Symposium on Foundations of Computer Science. с. 513—519. arXiv:quant-ph/0112086. doi:10.1109/SFCS.2002.1181975. ISBN 0-7695-1822-2.
29. Ambainis, A. (2005). Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range. Theory of Computing. 1 (1): 37—46. doi:10.4086/toc.2005.v001a003.
30. Kutin, S. (2005). Quantum Lower Bound for the Collision Problem with Small Range. Theory of Computing. 1 (1): 29—36. doi:10.4086/toc.2005.v001a002.
31. Aleksandrs Belovs. Span Programs for Functions with Constant-Sized 1-certificates. arXiv:1105.4024 [quant-ph].
32. Magniez, F.; Santha, M.; Szegedy, M. (2007). Quantum Algorithms for the Triangle Problem. SIAM Journal on Computing. 37 (2): 413—424. arXiv:quant-ph/0310134. doi:10.1137/050643684.
33. Aaronson, S. (3 лютого 2007). NAND now for something completely different. Shtetl-Optimized. Процитовано 17 грудня 2009.
34. Saks, M.E.; Wigderson, A. (1986). Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees (PDF). Proceedings of the 27th Annual Symposium on Foundations of Computer Science. IEEE. с. 29—38. doi:10.1109/SFCS.1986.44. ISBN 0-8186-0740-8.
35. Ambainis, A. A nearly optimal discrete query quantum algorithm for evaluating NAND formulas. arXiv:0704.3628 [quant-ph].
36. Reichardt, B. W.; Spalek, R. (2008). Span-program-based quantum algorithm for evaluating formulas. Proceedings of the 40th Annual ACM symposium on Theory of Computing. Association for Computing Machinery. с. 103—112. arXiv:0710.2630. doi:10.1145/1374376.1374394. ISBN 978-1-60558-047-0.
37. Pak, Igor (2012). Testing commutativity of a group and the power of randomization. LMS Journal of Computation and Mathematics. 15: 38—43. doi:10.1112/S1461157012000046.
38. Magniez, F.; Nayak, A. (2007). Quantum Complexity of Testing Group Commutativity. Algorithmica. 48 (3): 221—232. arXiv:quant-ph/0506265. doi:10.1007/s00453-007-0057-8.
39. Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.
40. Aharonov, D.; Jones, V.; Landau, Z. (2006). A polynomial quantum algorithm for approximating the Jones polynomial. Proceedings of the 38th Annual ACM symposium on Theory of Computing. Association for Computing Machinery. с. 427—436. arXiv:quant-ph/0511096. doi:10.1145/1132516.1132579. ISBN 1595931341.
41. Feynman, R. P. (1982). Simulating physics with computers. International Journal of Theoretical Physics. 21 (6–7): 467—488. Bibcode:1982IJTP...21..467F. CiteSeerX 10.1.1.45.9310. doi:10.1007/BF02650179.
42. Abrams, D. S.; Lloyd, S. (1997). Simulation of many-body Fermi systems on a universal quantum computer. Physical Review Letters. 79 (13): 2586—2589. arXiv:quant-ph/9703054. Bibcode:1997PhRvL..79.2586A. doi:10.1103/PhysRevLett.79.2586.
43. Kassal, I.; Jordan, S. P.; Love, P. J.; Mohseni, M.; Aspuru-Guzik, A. (2008). Polynomial-time quantum algorithm for the simulation of chemical dynamics. Proceedings of the National Academy of Sciences of the United States of America. 105 (48): 18681—86. arXiv:0801.2986. Bibcode:2008PNAS..10518681K. doi:10.1073/pnas.0808245105. PMC 2596249. PMID 19033207.
44. Freedman, M.; Kitaev, A.; Wang, Z. (2002). Simulation of Topological Field Theories by Quantum Computers. Communications in Mathematical Physics. 227 (3): 587—603. arXiv:quant-ph/0001071. Bibcode:2002CMaPh.227..587F. doi:10.1007/s002200200635.
45. Aharonov, D.; Jones, V.; Landau, Z. (2009). A polynomial quantum algorithm for approximating the Jones polynomial. Algorithmica. 55 (3): 395—421. arXiv:quant-ph/0511096. doi:10.1007/s00453-008-9168-0.
46. Wocjan, P.; Yard, J. (2008). The Jones polynomial: quantum algorithms and applications in quantum complexity theory. Quantum Information and Computation. 8 (1): 147—180. arXiv:quant-ph/0603069. Bibcode:2006quant.ph..3069W. doi:10.26421/QIC8.1-2-10.
47. Alagic, G.; Jordan, S.P.; König, R.; Reichardt, B. W. (2010). Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation. Physical Review A. 82 (4): 040302. arXiv:1003.0923. Bibcode:2010PhRvA..82d0302A. doi:10.1103/PhysRevA.82.040302.
48. Harrow, Aram W; Hassidim, Avinatan; Lloyd, Seth (2008). Quantum algorithm for solving linear systems of equations. Physical Review Letters. 103 (15): 150502. arXiv:0811.3171. Bibcode:2009PhRvL.103o0502H. doi:10.1103/PhysRevLett.103.150502. PMID 19905613.
49. Moll, Nikolaj; Barkoutsos, Panagiotis; Bishop, Lev S.; Chow, Jerry M.; Cross, Andrew; Egger, Daniel J.; Filipp, Stefan; Fuhrer, Andreas; Gambetta, Jay M. (2018). Quantum optimization using variational algorithms on near-term quantum devices. Quantum Science and Technology. 3 (3): 030503. arXiv:1710.01022. Bibcode:2018QS&T....3c0503M. doi:10.1088/2058-9565/aab822.
50. Farhi, Edward; Goldstone, Jeffrey (14 листопада 2014). A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 [quant-ph].
51. Peruzzo, Alberto; McClean, Jarrod; Shadbolt, Peter; Yung, Man-Hong; Zhou, Xiao-Qi; Love, Peter J.; Aspuru-Guzik, Alán; O’Brien, Jeremy L. (23 липня 2014). A variational eigenvalue solver on a photonic quantum processor. Nature Communications (англ.). 5 (1): 4213. arXiv:1304.3061. Bibcode:2014NatCo...5.4213P. doi:10.1038/ncomms5213. ISSN 2041-1723. PMC 4124861. PMID 25055053.
52. Higgott, Oscar; Wang, Daochen; Brierley, Stephen (2019). Variational Quantum Computation of Excited States. Quantum. 3: 156. arXiv:1805.08138. Bibcode:2019Quant...3..156H. doi:10.22331/q-2019-07-01-156.
53. Smart, Scott; Mazziotti, David (18 лютого 2021). Quantum Solver of Contracted Eigenvalue Equations for Scalable Molecular Simulations on Quantum Computing Devices. Phys. Rev. Lett. (англ.). 125 (7): 070504. arXiv:2004.11416. Bibcode:2021PhRvL.126g0504S. doi:10.1103/PhysRevLett.126.070504. PMID 33666467.
54. Mazziotti, David (6 жовтня 2006). Anti-Hermitian Contracted Schrödinger Equation: Direct Determination of the Two-Electron Reduced Density Matrices of Many-Electron Molecules. Phys. Rev. Lett. (англ.). 97 (14): 143002. Bibcode:2006PhRvL..97n3002M. doi:10.1103/PhysRevLett.97.143002. PMID 17155245.

Посилання

• Зоопарк квантових алгоритмів: вичерпний список квантових алгоритмів, які забезпечують прискорення порівняно з найшвидшими відомими класичними алгоритмами. (англ.)
• Конспекти лекцій Ендрю Чайлдса про квантові алгоритми (англ.)
• Алгоритм квантового пошуку — груба сила [Архівовано 1 вересня 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.