Перегляд вихідного коду сторінки Квантовий алгоритм

У [[Квантові обчислення|квантових обчисленнях]] '''квантовий алгоритм'''&nbsp;— це [[алгоритм]], який працює на основі реалістичної моделі квантового обчислення, причому найчастіше використовують модель обчислення [[Квантова схема|квантової схеми]]<ref>{{Cite book
|title=Quantum Computation and Quantum Information
|url=https://archive.org/details/quantumcomputati0000niel
|last=Nielsen
|first=Michael A.
|authorlink1=Майкл Нільсен
|last2=Chuang
|first2=Isaac L.
|authorlink2=Айзек Чуанг
|year=2000
|publisher=[[Cambridge University Press]]
|isbn=978-0-521-63503-5
}}</ref><ref>{{Cite arXiv |arxiv=0808.0369 |class=quant-ph |first=M. |last=Mosca |author-link=Мікеле Моска |title=Quantum Algorithms |date=2008}}</ref>. Класичний (або неквантовий) алгоритм&nbsp;— це скінченна послідовність інструкцій або покрокова процедура розв'язання задачі, де кожен крок або інструкцію можна виконати на класичному [[комп'ютер]]і. Подібно, квантовий алгоритм&nbsp;— це покрокова процедура, де кожен із кроків можна виконати на [[Квантовий комп'ютер|квантовому комп'ютері]]. Хоча всі класичні алгоритми також можна виконувати на квантовому комп'ютері<ref>{{Cite book
|url=https://books.google.com/books?id=-wkJIuw0YRsC&q=quantum%2520computer%2520equivalent%2520classical%2520computer&pg=PA23
|title=Quantum Computer Science
|last=Lanzagorta
|first=Marco
|last2=Uhlmann
|first2=Jeffrey K.
|date=2009-01-01
|publisher=Morgan & Claypool Publishers
|isbn=9781598297324
}}</ref>{{Rp|126}}, термін квантовий алгоритм, як правило, застосовують до алгоритмів, які за своєю суттю є квантовими або використовують деякі істотні властивості квантового обчислення, такі як [[Принцип суперпозиції (квантова механіка)|квантова суперпозиція]] або [[Сплутані квантові стани|квантова сплутаність]].

Задачі, які [[Алгоритмічно нерозв'язна задача|неможливо розв'язати]] за допомогою класичних комп'ютерів, залишаються нерозв'язними за допомогою квантових комп'ютерів.<ref name="nielchuan">{{Cite book
|url=https://books.google.com/books?id=-s4DEy7o-a0C
|title=Quantum Computation and Quantum Information
|last=Nielsen
|first=Michael A.
|authorlink1=Майкл Нільсен
|last2=Chuang
|first2=Isaac L.
|authorlink2=Айзек Чуанг
|year=2010
|publisher=Cambridge University Press
|edition=2nd
|location=Cambridge
|isbn=978-1-107-00217-3
}}</ref>{{Rp|127}} Цікавими квантові алгоритми робить те, що вони можуть розв'язувати деякі задачі швидше, ніж класичні алгоритми, оскільки квантову суперпозицію та квантову сплутаність, які, як правило, використовують квантові алгоритми, неможливо ефективно змоделювати на класичних комп'ютерах (див. [[Квантова перевага]]).

Найвідомішими алгоритмами є [[алгоритм Шора]] для [[Факторизація|факторизації]] та [[алгоритм Ґровера]] для пошуку в неструктурованій базі даних або невпорядкованому списку. Алгоритм Шора працює набагато (майже експоненціально) швидше, ніж найвідоміший класичний алгоритм розкладання на множники&nbsp;— [[решето числового поля]]<ref>{{Cite web|url=https://quantum-computing.ibm.com/docs/iqx/guide/shors-algorithm|title=Shor's algorithm|access-date=2024-08-26|archive-date=2023-01-12|archive-url=https://web.archive.org/web/20230112064753/https://quantum-computing.ibm.com/docs/iqx/guide/shors-algorithm|url-status=dead}}</ref>. Алгоритм Гровера працює квадратично швидше, ніж найкращий можливий класичний алгоритм для цієї задачі<ref>{{Cite web|url=https://quantum-computing.ibm.com/composer/docs/iqx/guide/grovers-algorithm|title=IBM quantum composer user guide: Grover's algorithm|website=quantum-computing.ibm.com|access-date=7 червня 2022}}</ref>&nbsp;— [[лінійний пошук]].

== Огляд ==
Квантові алгоритми зазвичай описують у загальновживаній схемній моделі квантового обчислення за допомогою [[Квантова схема|квантової схеми]], яка діє на деякі вхідні [[кубіт]]и та завершується [[вимірювання]]м. Квантова схема складається з простих [[Квантовий вентиль|квантових вентилів]], кожен з яких діє на деяку скінченну кількість кубітів. Квантові алгоритми також можна викласти в інших моделях квантових обчислень, таких як модель гамільтонового оракула<ref name="Hamiltonian_NAND_Tree">{{Cite journal|last=Farhi|first=Edward|last2=Goldstone|first2=Jeffrey|last3=Gutmann|first3=Sam|date=2008|title=A Quantum Algorithm for the Hamiltonian NAND Tree|journal=Theory of Computing|volume=4|pages=169–190|arxiv=quant-ph/0702144|doi=10.4086/toc.2008.v004a008|doi-access=free}}</ref>.

Квантові алгоритми можна класифікувати за основними техніками, задіяними в алгоритмі. Деякі методи/ідеї, які зазвичай використовують у квантових алгоритмах: фазовий відкіт, {{Нп|Алгоритм оцінення квантової фази|оцінення фази|en|Quantum phase estimation algorithm}}, квантове {{Нп|Квантове перетворення Фур’є|перетворення Фур’є|en|Quantum Fourier transform}}, {{Нп|квантове блукання|квантові блукання|en|Quantum walk}}, {{Нп|посилення амплітуди|3=en|4=Amplitude amplification}} та {{Нп|топологічна квантова теорія поля|3=en|4=Topological quantum field theory}}. Квантові алгоритми також можна згрупувати за типом розв'язуваної задачі (див., наприклад, огляд квантових алгоритмів для алгебричних задач)<ref>{{Cite journal|last=Childs|first=Andrew M.|author-link=Ендрю Чайлдс|last2=van Dam|first2=W.|year=2010|title=Quantum algorithms for algebraic problems|journal=[[Reviews of Modern Physics]]|volume=82|issue=1|pages=1–52|arxiv=0812.0380|bibcode=2010RvMP...82....1C|doi=10.1103/RevModPhys.82.1}}</ref>.

== Алгоритми на основі квантового перетворення Фур'є ==
{{Нп|Квантове перетворення Фур’є|3=en|4=Quantum Fourier transform}} є квантовим аналогом [[Дискретне перетворення Фур'є|дискретного перетворення Фур'є]] та використовується в кількох квантових алгоритмах. [[Перетворення Адамара]] є прикладом квантового перетворення Фур'є над n-вимірним векторним простором над полем {{Нп|GF(2)|F<sub>2</sub>|en}}. Квантове перетворення Фур'є можна ефективно реалізувати на квантовому комп'ютері, використовуючи лише поліноміальну кількість [[Квантовий вентиль|квантових вентилів]]{{Джерело}}.

=== Алгоритм Дойча&nbsp;— Йожи ===
{{Main|Алгоритм Дойча — Йожи}}
[[Файл:Deutsch-Jozsa-algorithm-quantum-circuit.png|міні|Алгоритм Дойча&nbsp;— Йожи]]
Алгоритм Дойча&nbsp;— Йожи розв'язує задачу [[Чорний ящик|чорної скриньки]], яка вимагає експоненціальної кількості запитів до чорної скриньки для будь-якого детермінованого класичного комп'ютера, але може бути розв'язана за допомогою одного запиту квантовим комп'ютером. Однак при порівнянні класичних із обмеженою помилкою і квантових алгоритмів прискорення не відбувається, оскільки класичний імовірнісний алгоритм може розв'язати задачу з постійною кількістю запитів із малою ймовірністю помилки. Алгоритм визначає, чи є функція ''f'' сталою (0 для всіх входів або 1 для всіх входів), чи збалансованою (повертає 1 для половини вхідної області та 0 для іншої половини).

=== Алгоритм Бернштейна&nbsp;— Вазірані ===
{{Main|Бернштейна — Вазірані}}
Алгоритм Бернштейна&nbsp;— Вазірані є першим квантовим алгоритмом, який розв'язує задачу ефективніше, ніж найвідоміший класичний алгоритм. Його розробили, щоб створити оракул поділу між {{Нп|Клас складності BQP|BQP|en|BQP}} і [[Клас складності BPP|BPP]].

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

=== Алгоритм оцінки квантової фази ===
{{Main|Алгоритм оцінки квантової фази}}
{{Нп|Алгоритм оцінки квантової фази|3=en|4=Quantum phase estimation algorithm}} використовують для визначення власної фази [[Власні вектори та власні значення|власного вектора]] унітарного вентиля, враховуючи квантовий стан, пропорційний власному вектору, і доступ до вентиля. Алгоритм часто використовують як підпрограму в інших алгоритмах.

=== Алгоритм Шора ===
{{Main|Алгоритм Шора}}
Алгоритм Шора розв'язує задачу [[Дискретний логарифм|дискретного логарифмування]] та задачу [[Факторизація цілих чисел|розкладання на множники]] за поліноміальний час<ref>
{{Cite journal|last=Shor|first=P. W.|year=1997|title=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer|journal=[[SIAM Journal on Scientific and Statistical Computing]]|volume=26|issue=5|pages=1484–1509|arxiv=quant-ph/9508027|bibcode=1995quant.ph..8027S|doi=10.1137/s0097539795293172}}</ref>, тоді як найвідоміші класичні алгоритми потребують суперполіноміального часу. Відомо, що ці задачі не є [[Клас складності P|P]] або [[NP-повна задача|NP-повними]]. Це також один із небагатьох квантових алгоритмів, який розв'язує за поліноміальний час задачу, відмінну від задачі чорної скриньки, де найвідоміші класичні алгоритми виконуються за суперполіноміальний час.

=== Задача прихованої підгрупи ===
Задача [[Абелева група|абелевої]] [[Задача прихованої підгрупи|прихованої підгрупи]] є узагальненням багатьох задач, які можна розв'язати квантовим комп'ютером, таких як задача Саймона, розв'язування [[рівняння Пелля]], перевірка [[Головний ідеал|головного ідеалу]] [[Кільце (алгебра)|кільця]] R і [[Факторизація цілих чисел|розкладання на множники]]. Для задачі існують ефективні квантові алгоритми<ref>{{cite conference
 |last1=Boneh |first1=D.
 |last2=Lipton |first2=R. J.
 |year=1995
 |title=Quantum cryptoanalysis of hidden linear functions
 |editor-last=Coppersmith |editor-first=D.
 |book-title=Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology
 |pages=424–437
 |publisher=[[Springer-Verlag]]
 |isbn=3-540-60221-6
}}</ref>. Загальніша [[задача прихованої підгрупи]], де група не обов'язково є абелевою, є узагальненням згаданих раніше задач, а також [[Ізоморфізм графів|ізоморфізму графів]] і певних [[Задачі теорії ґраток|задач теорії ґраток]]. Для деяких неабелевих груп відомі ефективні квантові алгоритми. Однак не відомі ефективні алгоритми для [[Симетрична група|симетричної групи]], які б дали ефективний алгоритм для ізоморфізму графа<ref>{{Cite arXiv |arxiv=quant-ph/0501056 |first=C. |last=Moore |first2=A. |last2=Russell |author-link=Кріс Мур |title=The Symmetric Group Defies Strong Fourier Sampling: Part I}}</ref>, та [[Діедрична група|діедричної групи]], які б розв'язали деякі задачі теорії ґраток<ref>{{Cite arXiv |arxiv=cs/0304005 |first=O. |last=Regev |title=Quantum Computation and Lattice Problems |date=2003}}</ref>.

=== Оцінювання сум Гаусса ===
[[Сума Гаусса]]&nbsp;— різновид [[Суми Вейля|експоненційної суми]]. Найвідоміший класичний алгоритм для оцінення цих сум вимагає експоненційного часу. Оскільки задача обчислення дискретного логарифму зводиться до оцінення суми Гаусса, ефективний класичний алгоритм для оцінення суми Гаусса означатиме ефективний класичний алгоритм для обчислення дискретних логарифмів, що вважається малоймовірним. Однак квантові комп'ютери можуть оцінювати суми Гауса з поліноміальною точністю за поліноміальний час<ref>
{{Cite arXiv |arxiv=quant-ph/0207131 |first=W. |last=van Dam |first2=G. |last2=Seroussi |title=Efficient Quantum Algorithms for Estimating Gauss Sums}}</ref>.

=== Фур'є-лов і перевірка Фур'є ===
Розглянемо [[Пророча машина|пророчу машину]], що складається з ''n'' випадкових булевих функцій, які відображають ''n''-розрядні рядки в логічне значення, з метою пошуку n ''n''-бітових рядків ''z''<sub>1</sub>,…,''z <sub>n</sub>'' так, що для перетворення Адамара&nbsp;— Фур'є принаймні 3/4 рядків задовольняють

: <math>| \tilde{f}(z_i)| \geqslant 1</math>

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

: <math>| \tilde{f}(z_i) | \geqslant 2.</math>

Це можна зробити за {{Нп|Клас складності BQP|квантовий поліноміальний час із обмеженою помилкою|en|BQP}} (BQP)<ref>
{{Cite arXiv |arxiv=0910.4698 |class=quant-ph |first=S. |last=Aaronson |title=BQP and the Polynomial Hierarchy}}</ref>.

== Алгоритми на основі посилення амплітуди ==
{{Нп|Посилення амплітуди|3=en|4=Amplitude amplification}}&nbsp;— це техніка, яка дозволяє посилювати вибраний підпростір квантового стану. Застосування посилення амплітуди зазвичай приводить до квадратичного прискорення порівняно з відповідними класичними алгоритмами. Його можна розглядати як узагальнення алгоритму Ґровера{{Джерело?}}.

=== Алгоритм Ґровера ===
{{Main|Алгоритм Ґровера}}[[Алгоритм Ґровера]] шукає позначений запис у неструктурованій базі даних (або невпорядкованому списку) з N записів, використовуючи лише <math>O(\sqrt{N})</math> запитів замість класично необхідних <math>O({N})</math> запитів<ref>
{{Cite arXiv |arxiv=quant-ph/9605043 |first=Lov K. |last=Grover |author-link=Лов Гровер |title=A fast quantum mechanical algorithm for database search |date=1996}}</ref>. Класично, потрібно <math>O({N})</math> запитів, навіть якщо допускаються ймовірнісні алгоритми з обмеженою помилкою.

Теоретики розглядали гіпотетичне узагальнення стандартного квантового комп'ютера, який міг би отримати доступ до історії прихованих змінних у [[Теорія де Бройля — Бома|механіці Бома]]. (Такий комп'ютер є повністю гіпотетичним і ''не'' був би стандартним квантовим комп'ютером або навіть можливим за стандартною теорією квантової механіки.) Такий гіпотетичний комп'ютер міг би здійснювати пошук у базі даних з N елементів щонайбільше за <math>O(\sqrt[3]{N})</math> кроків. Це трохи швидше, ніж <math>O(\sqrt{N})</math> кроків, які дає алгоритм Ґровера. Однак жоден метод пошуку не дозволить жодній моделі квантового комп'ютера розв'язувати [[NP-повна задача|NP-повні]] задачі за поліноміальний час<ref>{{Cite web|url=https://www.scottaaronson.com/papers/qchvpra.pdf|title=Quantum Computing and Hidden Variables|last=Aaronson|first=Scott}}</ref>.

=== Квантовий підрахунок ===
{{Нп|Алгоритм квантового підрахунку|Квантовий підрахунок|en|Quantum counting algorithm}} розв'язує узагальнення задачі пошуку&nbsp;— підрахунок кількості позначених записів у невпорядкованому списку, замість того, щоб просто визначити, чи такі існують. Зокрема, він підраховує кількість позначених записів у списку з <math>N</math> елементів із похибкою щонайбільше <math>\varepsilon</math> після тільки <math>\Theta\left(\varepsilon^{-1} \sqrt{N/k}\right)</math> запитів, де <math>k</math>&nbsp;— кількість позначених елементів у списку<ref>
{{Cite book
|title=Automata, Languages and Programming
|last=Brassard
|first=G.
|last2=Hoyer
|first2=P.
|last3=Tapp
|first3=A.
|date=1998
|series=Lecture Notes in Computer Science
|volume=1443
|pages=820–831
|chapter=Quantum counting
|arxiv=quant-ph/9805082
|doi=10.1007/BFb0055105
|isbn=978-3-540-64781-2
}}</ref><ref>
{{Cite book
|title=Quantum Computation and Quantum Information
|last=Brassard
|first=G.
|last2=Hoyer
|first2=P.
|last3=Mosca
|first3=M.
|last4=Tapp
|first4=A.
|year=2002
|editor-last=Samuel J. Lomonaco, Jr.
|series=AMS Contemporary Mathematics
|volume=305
|pages=53–74
|chapter=Quantum Amplitude Amplification and Estimation
|arxiv=quant-ph/0005055
|bibcode=2000quant.ph..5055B
|doi=10.1090/conm/305/05215
|isbn=9780821821404
}}</ref>. Точніше, алгоритм видає оцінку <math>k'</math> для <math>k</math>, кількості позначених записів, з точністю <math>|k-k'| \leq \varepsilon k</math>.

== Алгоритми на основі квантових блукань ==
{{Main|Квантове блукання}}
Квантове блукання&nbsp;— це квантовий аналог класичного [[Випадкове блукання|випадкового блукання]]. Класичне випадкове блукання можна описати [[Розподіл імовірностей|розподілом імовірностей]] за деякими станами, тоді як квантове блукання можна описати [[Принцип суперпозиції (квантова механіка)|квантовою суперпозицією]] за станами. Відомо, що квантові блукання дають для деяких задач чорної скриньки експоненційне прискорення<ref>{{cite conference
 |last1=Childs |first1=A. M.
 |last2=Cleve |first2=R.
 |last3=Deotto |first3=E.
 |last4=Farhi |first4=E.
 |last5=Gutmann |first5=S.
 |last6=Spielman |first6=D. A.
 |year=2003
 |title=Exponential algorithmic speedup by quantum walk
 |book-title=Proceedings of the 35th Symposium on Theory of Computing
 |pages=59–68
 |publisher=[[Association for Computing Machinery]]
 |arxiv=quant-ph/0209131
 |doi=10.1145/780542.780552
 |isbn=1-58113-674-9
}}</ref><ref>{{cite conference
 |last1=Childs |first1=A. M.
 |last2=Schulman |first2=L. J.
 |last3=Vazirani |first3=U. V.
 |year=2007
 |title=Quantum Algorithms for Hidden Nonlinear Structures
 |book-title=Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science
 |pages=395–404
 |publisher=[[IEEE]]
 |arxiv=0705.2784
 |doi=10.1109/FOCS.2007.18
 |isbn=978-0-7695-3010-9
}}</ref>. Вони також забезпечують поліноміальне прискорення для багатьох задач. Існує універсальний [[програмний каркас]] для створення алгоритмів квантового блукання<ref name="Search_via_quantum_walk">{{cite conference
 |last1=Magniez |first1=F.
 |last2=Nayak |first2=A.
 |last3=Roland |first3=J.
 |last4=Santha |first4=M.
 |year=2007
 |title=Search via quantum walk
 |book-title=Proceedings of the 39th Annual ACM Symposium on Theory of Computing
 |publisher=[[Association for Computing Machinery]]
 |pages=575–584
 |doi=10.1145/1250790.1250874
 |isbn=978-1-59593-631-8
|arxiv=quant-ph/0608026}}</ref>.

=== Задача вибірки бозона ===
{{Див. також|Бозонний семплінг}}
Задача вибірки бозонів в експериментальній конфігурації припускає<ref>{{Cite journal|last=Ralph|first=T.C.|date=July 2013|title=Figure 1: The boson-sampling problem|url=http://www.nature.com/nphoton/journal/v7/n7/fig_tab/nphoton.2013.175_F1.html|journal=Nature Photonics|publisher=Nature|volume=7|issue=7|pages=514–515|doi=10.1038/nphoton.2013.175|access-date=12 вересня 2014}}</ref> введення помірної кількості [[бозон]]ів (наприклад, фотонів), які випадковим чином розкидані у великій кількості вихідних мод, обмежених визначеною [[Унітарність (фізика)|унітарністю]]. За використання окремих фотонів, задача ізоморфна багатофотонному квантовому блуканню<ref>{{Cite journal|last=Peruzzo|first=Alberto|last2=Lobino|first2=Mirko|last3=Matthews|first3=Jonathan C. F.|last4=Matsuda|first4=Nobuyuki|last5=Politi|first5=Alberto|last6=Poulios|first6=Konstantinos|last7=Zhou|first7=Xiao-Qi|last8=Lahini|first8=Yoav|last9=Ismail|first9=Nur|date=2010-09-17|title=Quantum Walks of Correlated Photons|url=https://www.science.org/doi/10.1126/science.1193515|journal=Science|language=en|volume=329|issue=5998|pages=1500–1503|arxiv=1006.4764|bibcode=2010Sci...329.1500P|doi=10.1126/science.1193515|issn=0036-8075|pmid=20847264}}</ref>. Тоді вона полягає в тому, щоб створити досить добру вибірку [[Розподіл імовірностей|розподілу ймовірностей]] результату, який залежить від вхідного розташування бозонів і унітарності<ref>{{Cite journal|last=Lund|first=A.P.|last2=Laing|first2=A.|last3=Rahimi-Keshari|first3=S.|last4=Rudolph|first4=T.|last5=O'Brien|first5=J.L.|last6=Ralph|first6=T.C.|date=5 вересня 2014|title=Boson Sampling from Gaussian States|journal=Phys. Rev. Lett.|volume=113|issue=10|page=100502|arxiv=1305.4346|bibcode=2014PhRvL.113j0502L|doi=10.1103/PhysRevLett.113.100502|pmid=25238340}}</ref>. Розв'язання цієї задачі за допомогою класичного комп'ютерного алгоритму вимагає обчислення [[перманент]]а унітарної матриці перетворення, що може зайняти надзвичайно багато часу або бути абсолютно неможливим. 2014 року запропоновано<ref>{{Cite web|url=http://phys.org/news/2014-09-quantum-revolution-closer.html|title=The quantum revolution is a step closer|website=Phys.org|publisher=Omicron Technology Limited|access-date=12 вересня 2014}}</ref>, що існуючу технологію та стандартні ймовірнісні методи генерування однофотонних станів можна використати як вхідні дані у відповідну квантово обчислювану [[Лінійний оптичний квантовий комп'ютер|лінійну оптичну мережу]], і що квантові алгоритми дадуть явно кращу дискретизацію розподілу вихідної ймовірності. 2015 року дослідження передбачило<ref>{{Cite journal|last=Seshadreesan|first=Kaushik P.|last2=Olson|first2=Jonathan P.|last3=Motes|first3=Keith R.|last4=Rohde|first4=Peter P.|last5=Dowling|first5=Jonathan P.|year=2015|title=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|journal=Physical Review A|volume=91|issue=2|page=022334|arxiv=1402.0531|bibcode=2015PhRvA..91b2334S|doi=10.1103/PhysRevA.91.022334}}</ref>, що задача вибірки мала подібну складність для вхідних даних, крім фотонів [[Стан Фока|у стані Фока,]] і виявила перехід {{Нп|Квантова теорія складності|обчислювальної складності|en|Quantum complexity theory}} від класично модельованої до такої ж складної, як задача бозонної вибірки, залежно від розміру когерентних амплітудних входів.

=== Задача відмінності елементів ===
Задача відмінності елементів полягає у визначенні, чи всі елементи списку є різними. Класично, для списку розміру <math>N</math> потрібні <math>\Omega(N)</math> запитів; однак на квантовому комп'ютері її можна розв'язати за <math>\Theta(N^{2/3})</math> запитів. Оптимальний алгоритм запропонував [[Андріс Амбайніс]]<ref>
{{Cite journal|last=Ambainis|first=A.|year=2007|title=Quantum Walk Algorithm for Element Distinctness|journal={{li|SIAM Journal on Computing|Q=Q7390263}}|volume=37|issue=1|pages=210–239|arxiv=quant-ph/0311001|doi=10.1137/S0097539705447311}}</ref>, а Яоюнь Ши вперше довів жорстку нижню межу, коли розмір діапазону достатньо великий<ref>
{{cite conference
 | last1=Shi | first1=Y.
 | title=The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.
 | year=2002
 | chapter=Quantum lower bounds for the collision and the element distinctness problems
 | conference = Proceedings of the 43rd [[Symposium on Foundations of Computer Science]]
 | pages=513–519
 | arxiv = quant-ph/0112086
 | doi=10.1109/SFCS.2002.1181975| isbn=0-7695-1822-2
 }}</ref>. Амбайніс<ref>
{{Cite journal|last=Ambainis|first=A.|year=2005|title=Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range|journal=[[Theory of Computing]]|volume=1|issue=1|pages=37–46|doi=10.4086/toc.2005.v001a003|doi-access=free}}</ref> і Кутін<ref>
{{Cite journal|last=Kutin|first=S.|year=2005|title=Quantum Lower Bound for the Collision Problem with Small Range|journal=[[Theory of Computing]]|volume=1|issue=1|pages=29–36|doi=10.4086/toc.2005.v001a002|doi-access=free}}</ref>, незалежно один від одного (і за допомогою різних доведень), розширили цю роботу, щоб отримати нижню межу для всіх функцій.

=== Задача знаходження трикутника ===
Задача знаходження трикутника полягає у визначенні, чи містить даний [[Граф (математика)|граф]] трикутник ([[Кліка (теорія графів)|кліку]] розміром 3). Найвідомішою нижньою межею для квантових алгоритмів є <math>\Omega(N)</math>, але найкращий відомий алгоритм потребує O(''N''<sup>1,297</sup>) запитів,<ref>{{Cite arXiv |arxiv=1105.4024 |class=quant-ph |author=Aleksandrs Belovs |title=Span Programs for Functions with Constant-Sized 1-certificates}}</ref> що краще, порівняно з попередніми найкращими O(''N''<sup>1,3</sup>) запитами<ref name="Search_via_quantum_walk"/><ref>
{{Cite journal|last=Magniez|first=F.|last2=Santha|first2=M.|last3=Szegedy|first3=M.|year=2007|title=Quantum Algorithms for the Triangle Problem|journal=[[SIAM Journal on Computing]]|volume=37|issue=2|pages=413–424|arxiv=quant-ph/0310134|doi=10.1137/050643684}}</ref>.

=== Оцінення формул ===
Формула&nbsp;— це [[Дерево (структура даних)|дерево]] з вентилем у кожному [[Дерево (структура даних)#Використовувана термінологія|внутрішньому вузлі]] та вхідним бітом у кожному [[Дерево (структура даних)#Використовувана термінологія|листовому вузлі]]. Задача полягає в тому, щоб оцінити формулу, яка є виходом кореневого вузла, отримавши доступ [[Пророча машина|оракула]] до вхідних даних.

Добре вивченою формулою є збалансоване бінарне дерево лише з вентилями [[Штрих Шефера|NAND]]<ref>
{{Cite web|url=http://scottaaronson.com/blog/?p=207|title=NAND now for something completely different|last=Aaronson|first=S.|date=3 лютого 2007|website=Shtetl-Optimized|access-date=2009-12-17}}</ref>. Цей тип формули вимагає <math>\Theta(N^c)</math> запитів з використанням випадковості,<ref>
{{cite conference
 |last1=Saks |first1=M.E.
 |last2=Wigderson |first2=A.
 |year=1986
 |title=Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees
 |url=http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SW86/SW86.pdf
 |book-title=Proceedings of the 27th Annual Symposium on Foundations of Computer Science
 |pages=29–38
 |publisher=[[IEEE]]
 |doi=10.1109/SFCS.1986.44
 |isbn=0-8186-0740-8
}}</ref> де <math>c = \log_2(1+\sqrt{33})/4 \approx 0.754</math>. Однак, за допомогою квантового алгоритму це можна розв'язати за <math>\Theta(N^{1/2})</math> запитів. Кращого квантового алгоритму для цього випадку не було відомо, поки його не було знайдено для нетрадиційної моделі гамільтонівського оракула<ref name="Hamiltonian_NAND_Tree"/>. Невдовзі з'явився такий самий результат для стандартного налаштування<ref>
{{Cite arXiv |arxiv=0704.3628 |class=quant-ph |first=A. |last=Ambainis |title=A nearly optimal discrete query quantum algorithm for evaluating NAND formulas}}</ref>.

Відомі також швидкі квантові алгоритми для складніших формул<ref>
{{cite conference
 |last1=Reichardt |first1=B. W.
 |last2=Spalek |first2=R.
 |year=2008
 |title=Span-program-based quantum algorithm for evaluating formulas
 |book-title=Proceedings of the 40th Annual ACM symposium on Theory of Computing
 |publisher=[[Association for Computing Machinery]]
 |pages=103–112
 |isbn=978-1-60558-047-0
 |doi=10.1145/1374376.1374394
|arxiv=0710.2630}}</ref>.

=== Комутативність групи ===
{{Докладніше|Абелева група}}
Проблема полягає в тому, щоб визначити, чи є [[група чорної скриньки]], задана ''k'' генераторами, [[Комутативність|комутативною]]. Група чорної скриньки&nbsp;— це група з функцією оракула, яка повинна використовуватися для виконання групових операцій (множення, інверсії та порівняння з тотожністю). Цікавість у цьому контексті полягає в складності запиту, яка дорівнює кількості викликів оракула, необхідних для розв'язання задачі. Складність детермінованих і рандомізованих запитів <math>\Theta(k^2)</math> і <math>\Theta(k)</math> відповідно<ref>
{{Cite journal|last=Pak|first=Igor|year=2012|title=Testing commutativity of a group and the power of randomization|journal=[[LMS Journal of Computation and Mathematics]]|volume=15|pages=38–43|doi=10.1112/S1461157012000046|doi-access=free}}</ref>. Квантовий алгоритм потребує <math>\Omega(k^{2/3})</math> запитів, тоді як найвідоміший класичний алгоритм використовує <math>O(k^{2/3} \log k)</math> запитів<ref>
{{Cite journal|last=Magniez|first=F.|last2=Nayak|first2=A.|year=2007|title=Quantum Complexity of Testing Group Commutativity|journal=[[Algorithmica]]|volume=48|issue=3|pages=221–232|arxiv=quant-ph/0506265|doi=10.1007/s00453-007-0057-8}}</ref>.

== BQP-повні задачі ==
[[Клас складності]] {{Нп|Клас складності BQP|BQP|en|BQP}} (квантовий поліноміальний час з обмеженою помилкою)&nbsp;— це набір [[Задача вибору|задач прийняття рішення]], які [[квантовий комп'ютер]] розв'язує за [[Часова складність|поліноміальний час]] з імовірністю помилки не більше 1/3 для всіх випадків.<ref name="Chuang2000">Michael Nielsen and Isaac Chuang (2000). ''Quantum Computation and Quantum Information''. Cambridge: Cambridge University Press. {{ISBN|0-521-63503-9}}.</ref> Це квантовий аналог класичного класу складності '''[[Клас складності BPP|BPP]].'''.

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

=== Обчислення інваріантів вузла ===
Віттен показав, що {{Нп|топологічна квантова теорія поля|топологічну квантову теорію поля|en|Topological quantum field theory}} {{Нп|Теорія Черна — Саймонса|Черна&nbsp;— Саймонса|en|Chern–Simons theory}} (ТКТП) можна розв'язати в термінах [[Многочлен Джонса|многочленів Джонса]]. Квантовий комп'ютер може симулювати ТКТП і, завдяки цьому, апроксимувати многочлен Джонса,<ref>
{{Cite conference
 | last1 = Aharonov | first1 = D.
 | last2 = Jones | first2 = V.
 | last3 = Landau | first3 = Z.
 | year = 2006
 | title = A polynomial quantum algorithm for approximating the Jones polynomial
 | book-title=Proceedings of the 38th Annual ACM symposium on Theory of Computing
 | pages = 427–436
 | publisher=[[Association for Computing Machinery]]
 | doi = 10.1145/1132516.1132579
| arxiv = quant-ph/0511096| isbn = 1595931341
 }}</ref> який, наскільки відомо, у найгіршому випадку складно обчислити класичним способом.{{Джерело}}

=== Квантова симуляція ===
{{Main|Гамільтонова симуляція}}
Ідея про те, що квантові комп'ютери можуть бути потужнішими за класичні комп'ютери, виникла в спостереженні [[Річард Філіпс Фейнман|Річарда Фейнмана]] про те, що класичним комп'ютерам, схоже, потрібен [[експоненційний час]] для моделювання багаточастинкових квантових систем, але квантові системи багатьох тіл здатні «розв'язувати самі себе».<ref>
{{Cite journal|last=Feynman|first=R. P.|year=1982|title=Simulating physics with computers|journal=[[International Journal of Theoretical Physics]]|volume=21|issue=6–7|pages=467–488|bibcode=1982IJTP...21..467F|citeseerx=10.1.1.45.9310|doi=10.1007/BF02650179}}</ref> Відтоді ідею про те, що квантові комп'ютери можуть симулювати квантові фізичні процеси експоненційно швидше, ніж класичні комп'ютери, значно конкретизовано та розроблено. Використовуючи лише кілька сотень кубітів, розроблено ефективні (тобто з поліноміальним часом) квантові алгоритми для моделювання як бозонних, так і ферміонних систем,<ref>
{{Cite journal|last=Abrams|first=D. S.|last2=Lloyd|first2=S.|year=1997|title=Simulation of many-body Fermi systems on a universal quantum computer|journal=[[Physical Review Letters]]|volume=79|issue=13|pages=2586–2589|arxiv=quant-ph/9703054|bibcode=1997PhRvL..79.2586A|doi=10.1103/PhysRevLett.79.2586}}</ref> а також для моделювання хімічних реакцій, що виходить за межі можливостей сучасних класичних суперкомп'ютерів.<ref>
{{Cite journal|last=Kassal|first=I.|last2=Jordan|first2=S. P.|last3=Love|first3=P. J.|last4=Mohseni|first4=M.|last5=Aspuru-Guzik|first5=A.|year=2008|title=Polynomial-time quantum algorithm for the simulation of chemical dynamics|journal=[[Proceedings of the National Academy of Sciences of the United States of America]]|volume=105|issue=48|pages=18681–86|arxiv=0801.2986|bibcode=2008PNAS..10518681K|doi=10.1073/pnas.0808245105|pmc=2596249|pmid=19033207|doi-access=free}}</ref> Квантові комп'ютери також можуть ефективно симулювати [[Топологічна квантова теорія поля|топологічні квантові теорії поля]].<ref>
{{Cite journal|last=Freedman|first=M.|last2=Kitaev|first2=A.|last3=Wang|first3=Z.|year=2002|title=Simulation of Topological Field Theories by Quantum Computers|journal=[[Communications in Mathematical Physics]]|volume=227|issue=3|pages=587–603|arxiv=quant-ph/0001071|bibcode=2002CMaPh.227..587F|doi=10.1007/s002200200635}}</ref> Окрім внутрішнього інтересу, цей результат призвів до ефективних квантових алгоритмів для оцінення [[Квантовий інваріант|квантових топологічних інваріантів]], таких як [[Многочлен Джонса|многочлени Джонса]]<ref>
{{Cite journal|last=Aharonov|first=D.|last2=Jones|first2=V.|last3=Landau|first3=Z.|year=2009|title=A polynomial quantum algorithm for approximating the Jones polynomial|journal=[[Algorithmica]]|volume=55|issue=3|pages=395–421|arxiv=quant-ph/0511096|doi=10.1007/s00453-008-9168-0}}</ref> і [[Многочлен HOMFLY|HOMFLY]]<ref>
{{Cite journal|last=Wocjan|first=P.|last2=Yard|first2=J.|year=2008|title=The Jones polynomial: quantum algorithms and applications in quantum complexity theory|journal=[[Quantum Information and Computation]]|volume=8|issue=1|pages=147–180|arxiv=quant-ph/0603069|bibcode=2006quant.ph..3069W|doi=10.26421/QIC8.1-2-10}}</ref> та [[інваріант Тураєва — Віро]] тривимірних многовидів.<ref>
{{Cite journal|last=Alagic|first=G.|last2=Jordan|first2=S.P.|last3=König|first3=R.|last4=Reichardt|first4=B. W.|year=2010|title=Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation|journal=[[Physical Review A]]|volume=82|issue=4|pages=040302|arxiv=1003.0923|bibcode=2010PhRvA..82d0302A|doi=10.1103/PhysRevA.82.040302}}</ref>

=== Розв'язування систем лінійних рівнянь ===
2009 року {{Нп|Арам Гарроу|3=en|4=Aram Harrow}}, Авінатан Хасідім і [[Сет Ллойд]] сформулювали квантовий алгоритм для розв'язання [[Система лінійних алгебраїчних рівнянь|систем лінійних рівнянь]]. {{Нп|Алгоритм HHL|Алгоритм|en|HHL algorithm}} оцінює результат скалярного вимірювання вектора розв'язку заданої лінійної системи рівнянь.<ref name="Quantum algorithm for solving linear systems of equations by Harrow et al.">{{Cite journal|last=Harrow|first=Aram W|last2=Hassidim|first2=Avinatan|last3=Lloyd|first3=Seth|year=2008|title=Quantum algorithm for solving linear systems of equations|journal=Physical Review Letters|volume=103|issue=15|pages=150502|arxiv=0811.3171|bibcode=2009PhRvL.103o0502H|doi=10.1103/PhysRevLett.103.150502|pmid=19905613}}</ref>

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

== Гібридні квантові/класичні алгоритми ==
Гібридні квантові/класичні алгоритми поєднують підготовку квантового стану та вимірювання з класичною оптимізацією.<ref>{{Cite journal|last=Moll|first=Nikolaj|last2=Barkoutsos|first2=Panagiotis|last3=Bishop|first3=Lev S.|last4=Chow|first4=Jerry M.|last5=Cross|first5=Andrew|last6=Egger|first6=Daniel J.|last7=Filipp|first7=Stefan|last8=Fuhrer|first8=Andreas|last9=Gambetta|first9=Jay M.|date=2018|title=Quantum optimization using variational algorithms on near-term quantum devices|journal=Quantum Science and Technology|volume=3|issue=3|pages=030503|arxiv=1710.01022|bibcode=2018QS&T....3c0503M|doi=10.1088/2058-9565/aab822}}</ref> Ці алгоритми зазвичай спрямовані на визначення власного вектора основного стану та власного значення [[Ермітів оператор|ермітового оператора]].

=== QAOA ===
[[Алгоритми квантової оптимізації|Алгоритм квантової наближеної оптимізації]] нагадує [[квантовий відпал]], виконуючи дискретизоване наближення квантового відпалу за допомогою квантової схеми. Його можна використовувати для розв'язування задач із теорії графів.<ref>{{Cite arXiv |arxiv=1411.4028 |class=quant-ph |first=Edward |last=Farhi |first2=Jeffrey |last2=Goldstone |title=A Quantum Approximate Optimization Algorithm |date=2014-11-14}}</ref> Для максимізації «цільової функції» алгоритм використовує класичну оптимізацію квантових операцій.

=== Варіаційний квантовий власний розв'язувач ===
Алгоритм {{Нп|варіаційний квантовий власний розв’язувач|варіаційного квантового власного розв’язувача|en|Variational quantum eigensolver}} (VQE) застосовує класичну оптимізацію, щоб мінімізувати очікуване енергетичне значення [[Анзац|анзац-стану,]] щоб знайти основний стан [[Ермітів оператор|ермітового оператора]], наприклад [[гамільтоніан]]а молекули.<ref>{{Cite journal|last=Peruzzo|first=Alberto|last2=McClean|first2=Jarrod|last3=Shadbolt|first3=Peter|last4=Yung|first4=Man-Hong|last5=Zhou|first5=Xiao-Qi|last6=Love|first6=Peter J.|last7=Aspuru-Guzik|first7=Alán|last8=O’Brien|first8=Jeremy L.|date=2014-07-23|title=A variational eigenvalue solver on a photonic quantum processor|journal=Nature Communications|language=En|volume=5|issue=1|pages=4213|arxiv=1304.3061|bibcode=2014NatCo...5.4213P|doi=10.1038/ncomms5213|issn=2041-1723|pmc=4124861|pmid=25055053}}</ref> Його також можна розширити, щоб знайти збуджені енергії молекулярних гамільтоніанів.<ref>{{Cite journal|last=Higgott|first=Oscar|last2=Wang|first2=Daochen|last3=Brierley|first3=Stephen|year=2019|title=Variational Quantum Computation of Excited States|journal=Quantum|volume=3|pages=156|arxiv=1805.08138|bibcode=2019Quant...3..156H|doi=10.22331/q-2019-07-01-156}}</ref>

=== Скорочений квантовий власний розв'язувач ===
Алгоритм скороченого квантового власного розв'язувача (CQE) мінімізує залишок скорочення (або проєкції) [[рівняння Шредінгера]] на простір двох (або більше) електронів, щоб знайти енергію основного або збудженого стану та двоелектронну зменшену [[Матриця густини|матрицю густини]] молекули.<ref>{{Cite journal|last=Smart|first=Scott|last2=Mazziotti|first2=David|date=2021-02-18|title=Quantum Solver of Contracted Eigenvalue Equations for Scalable Molecular Simulations on Quantum Computing Devices|journal=Phys. Rev. Lett.|language=En|volume=125|issue=7|pages=070504|arxiv=2004.11416|bibcode=2021PhRvL.126g0504S|doi=10.1103/PhysRevLett.126.070504|pmid=33666467}}</ref> Він заснований на класичних методах розв'язування енергій і двоелектронних зменшених матриць густини безпосередньо з антиермітового скороченого рівняння Шредінгера.<ref>{{Cite journal|last=Mazziotti|first=David|date=2006-10-06|title=Anti-Hermitian Contracted Schrödinger Equation: Direct Determination of the Two-Electron Reduced Density Matrices of Many-Electron Molecules|journal=Phys. Rev. Lett.|language=En|volume=97|issue=14|pages=143002|bibcode=2006PhRvL..97n3002M|doi=10.1103/PhysRevLett.97.143002|pmid=17155245}}</ref>

== Див. також ==
* [[Квантове машинне навчання]]
* [[Алгоритми квантової оптимізації]]
* [[Квантове сортування]]
* [[Тест простоти]]

== Примітки ==
{{примітки|2}}

== Посилання ==
* [https://quantumalgorithmzoo.org Зоопарк квантових алгоритмів]: вичерпний список квантових алгоритмів, які забезпечують прискорення порівняно з найшвидшими відомими класичними алгоритмами. {{Ref-en}}
* [https://www.cs.umd.edu/~amchilds/qa/ Конспекти лекцій Ендрю Чайлдса про квантові алгоритми] {{Ref-en}}
* [https://bastion.center/the-quantum-search-algorithm/ Алгоритм квантового пошуку&nbsp;— груба сила] {{Webarchive|url=https://web.archive.org/web/20180901034619/https://bastion.center/the-quantum-search-algorithm/|date=1 вересня 2018}}.

=== Огляди ===
* {{Cite arXiv |arxiv=2310.03011 |class=quant-ph |first=Alexander M. |last=Dalzell |first2=Sam |last2=McArdle |title=Quantum algorithms: A survey of applications and end-to-end complexities |date=2023}}
* {{Cite book
|title=Handbook of Natural Computing
|last=Smith
|first=J.
|last2=Mosca
|first2=M.
|year=2012
|pages=1451–1492
|chapter=Algorithms for Quantum Computers
|arxiv=1001.0767
|doi=10.1007/978-3-540-92910-9_43
|isbn=978-3-540-92909-3
}}
* {{Cite journal|last=Childs|first=A. M.|last2=Van Dam|first2=W.|year=2010|title=Quantum algorithms for algebraic problems|journal=Reviews of Modern Physics|volume=82|issue=1|pages=1–52|arxiv=0812.0380|bibcode=2010RvMP...82....1C|doi=10.1103/RevModPhys.82.1}}
{{Квантовий комп'ютер}}
{{Перспективні технології|квантові=так}}

[[Категорія:Квантові алгоритми]]
[[Категорія:Теоретична інформатика]]
[[Категорія:Квантові обчислення]]