Базовые квантовые подпрограммы: поиск нескольких отмеченных элементов и суммирование чисел

Переиздано Платоном

Читают: 0

Базовые квантовые подпрограммы: поиск нескольких отмеченных элементов и суммирование чисел PlatoBlockchain Data Intelligence. Вертикальный поиск. Ай.

Джоран ван Апелдорн¹, Сандер Гриблинг²и Гарольд Ньюбоер³

¹IViR и QuSoft, Амстердамский университет, Нидерланды
²Кафедра эконометрики и исследования операций, Тилбургский университет, Тилбург, Нидерланды
³Институт математики Кортевега-де Фриза и QuSoft, Амстердамский университет, Нидерланды и факультет компьютерных наук Рурского университета в Бохуме, Германия и факультет математических наук Копенгагенского университета, Дания

Находите эту статью интересной или хотите обсудить? Scite или оставить комментарий на SciRate.

Абстрактные

Мы покажем, как найти все отмеченные $k$ элементы в списке размера $N$, используя оптимальное количество $O(sqrt{N k})$ квантовых запросов и только полилогарифмические накладные расходы на сложность вентиля в ситуации, когда у человека небольшая квантовая память. Предыдущие алгоритмы либо приводили к увеличению сложности вентиля в $k$, либо к сложности запроса в $log(k)$.
Затем мы рассматриваем задачу поиска мультипликативной $delta$-аппроксимации $s = sum_{i=1}^N v_i$, где $v=(v_i) в [0,1]^N$, с учетом доступа квантового запроса к двоичное описание $v$. Мы даем алгоритм, который делает это с вероятностью не менее $1-rho$, используя $O(sqrt{N log(1/rho) / delta})$ квантовые запросы (при мягких предположениях о $rho$). Это квадратично улучшает зависимость от $1/delta$ и $log(1/rho)$ по сравнению с простым применением оценки амплитуды. Чтобы получить улучшенную зависимость $log(1/rho)$, мы используем первый результат.

► Данные BibTeX

@article{vanApeldoorn2024basicquantum, дои = {10.22331/q-2024-03-14-1284}, URL = {https://doi.org/10.22331/q-2024-03-14-1284}, title = {Основные квантовые процедуры: поиск нескольких отмеченных элементов и суммирование чисел}, автор = {ван Апелдорн, Йоран и Гриблинг, Сандер и Ньюбоер, Гарольд}, журнал = {{Квант}}, иссн = {2521-327X}, издатель = {{Verein zur F{"{o}}rderung des Open Access Publizierens в Quantenwissenschaften}}, объем = {8}, страницы = {1284}, месяц = март, год = {2024} }

► Рекомендации

[1] Шринивасан Аруначалам и Рональд де Вольф. Оптимизация количества гейтов в квантовом поиске. Квантовая информация. Comput., 17(3-4):251–261, 2017. doi:10.26421/qic17.3-4.
https: / / doi.org/ 10.26421 / qic17.3-4

[2] Хосе А. Аделл и П. Йодра. Точные Колмогоровские и полные вариационные расстояния между некоторыми знакомыми дискретными распределениями. Журнал неравенств и приложений, 2006(1):1–8, 2006. doi:10.1155/JIA/2006/64307.
https://doi.org/10.1155/JIA/2006/64307

[3] Йоран ван Апелдорн, Сандер Гриблинг, Инан Ли, Гарольд Ньюбоер, Майкл Уолтер и Рональд де Вольф. Квантовые алгоритмы масштабирования матриц и балансировки матриц. В материалах 48-го Международного коллоквиума по автоматам, языкам и программированию (ICALP'21), том 198, страницы 110:1–110:17, 2021. arXiv:2011.12823, doi:10.4230/LIPIcs.ICALP.2021.110.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.110
Arxiv: 2011.12823

[4] Скотт Ааронсон и Патрик Ралл. Квантовый приближенный счет, упрощенный. На симпозиуме по простоте алгоритмов, страницы 24–32, 2020 г. doi:10.1137/1.9781611976014.5.
https: / / doi.org/ 10.1137 / 1.9781611976014.5

[5] Мишель Бойер, Жиль Брассар, Питер Хойер и Ален Тапп. Жесткие границы квантового поиска. Fortschritte der Physik, 46(4–5):493–505, 1998. Более ранняя версия в Physcomp'96. arXiv:quant-ph/9605034.
Arxiv: колич-фот / 9605034

[6] Гарри Бурман, Ричард Клив, Рональд де Вольф и Кристоф Залка. Границы для квантовых алгоритмов с малой и нулевой ошибкой. На 40-м ежегодном симпозиуме по основам информатики (FOCS'99), страницы 358–368. Компьютерное общество IEEE, 1999.

[7] Жиль Брассар, Питер Хойер, Мишель Моска и Ален Тапп. Квантовое амплитудное усиление и оценка. В «Квантовых вычислениях и квантовой информации: том тысячелетия», том 305 журнала «Современная математика», страницы 53–74. Американское математическое общество, 2002. doi:10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P.
<a href="https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P”>https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P

[8] Ричард Брент и Пол Циммерманн. Современная компьютерная арифметика, том 18. Издательство Кембриджского университета, 2010.

[9] Ран Канетти, Гай Эвен и Одед Голдрейх. Нижние границы алгоритмов выборки для оценки среднего значения. Письма об обработке информации, 53(1):17–25, январь 1995 г. doi:10.1016/0020-0190(94)00171-T.
https://doi.org/10.1016/0020-0190(94)00171-T

[10] Карло Силиберто, Марк Хербстер, Алессандро Давиде Ялонго, Массимилиано Понтил, Андреа Роккетто, Симоне Северини и Леонард Воссниг. Квантовое машинное обучение: классическая перспектива. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, январь 2018 г. doi:10.1098/rspa.2017.0551.
https: / / doi.org/ 10.1098 / rspa.2017.0551

[11] Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест и Клиффорд Штайн. Введение в алгоритмы. MIT Press, 4-е издание, 2022 г.

[12] П. Диаконис и Д. Фридман. Конечные перезаменяемые последовательности. Анналы вероятности, 8(4):745–764, 1980. URL: https://www.jstor.org/stable/2242823.
HTTPS: / / www.jstor.org/ стабильный / 2242823

[13] Кристоф Дюрр и Питер Хойер. Квантовый алгоритм поиска минимума, 1996. doi:10.48550/arXiv.quant-ph/9607014.
https:///doi.org/10.48550/arXiv.quant-ph/9607014
Arxiv: колич-фот / 9607014

[14] Кристоф Дюрр, Марк Хейлигман, Питер Хойер и Мехди Мхалла. Сложность квантовых запросов некоторых задач на графах. SIAM Journal on Computing, 35(6):1310–1328, январь 2006 г. doi:10.1137/050644719.
https: / / doi.org/ 10.1137 / 050644719

[15] Пол Дагам, Ричард Карп, Майкл Луби и Шелдон Росс. Оптимальный алгоритм оценки методом Монте-Карло. SIAM Journal on Computing, 29(5):1484–1496, январь 2000 г. doi:10.1137/S0097539797315306.
https: / / doi.org/ 10.1137 / S0097539797315306

[16] Витторио Джованнетти, Сет Ллойд и Лоренцо Макконе. Квантовая оперативная память. Physical Review Letters, 100(16), апрель 2008 г. doi:10.1103/physrevlett.100.160501.
https: / / doi.org/ 10.1103 / physrevlett.100.160501

[17] Сандер Гриблинг и Гарольд Ньюбоер. Улучшены квантовые нижняя и верхняя границы масштабирования матрицы. В материалах 39-го Международного симпозиума по теоретическим аспектам информатики (STACS'22), том 219, страницы 35: 1–35: 23, 2022. arXiv: 2109.15282, doi: 10.4230/LIPIcs.STACS.2022.35.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2022.35
Arxiv: 2109.15282

[18] Март де Грааф и Рональд де Вольф. О квантовых версиях принципа Яо. На 19-м симпозиуме по теоретическим аспектам информатики (STACS'02), том 2285 конспектов лекций по информатике, страницы 347–358, Берлин, Гейдельберг, 2002. Springer. doi:10.1007/3-540-45841-7_28.
https://doi.org/10.1007/3-540-45841-7_28

[19] Лов К. Гровер. Быстрый квантовомеханический алгоритм поиска в базе данных. В материалах 38-го ежегодного симпозиума ACM по теории вычислений (STOC'96), страницы 212–219, 1996. arXiv:quant-ph/9605043, doi:10.1145/237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866
Arxiv: колич-фот / 9605043

[20] Лов К. Гровер. Квантовые телевычисления, 1997. Технический меморандум Bell Labs ITD97-31630F. doi:10.48550/arXiv.quant-ph/9704012.
https:///doi.org/10.48550/arXiv.quant-ph/9704012
Arxiv: колич-фот / 9704012

[21] Лов К. Гровер. Основа для быстрых квантово-механических алгоритмов. В материалах тридцатого ежегодного симпозиума ACM по теории вычислений (STOC'98), страницы 53–62, 1998. arXiv:quant-ph/9711043, doi:10.1145/276698.276712.
https: / / doi.org/ 10.1145 / 276698.276712
Arxiv: колич-фот / 9711043

[22] Ясин Хамуди. Квантовая оценка субгауссова среднего. На 29-м ежегодном европейском симпозиуме по алгоритмам (ESA 2021), том 204 Международных трудов Лейбница по информатике (LIPIcs), страницы 50: 1–50: 17, 2021. doi: 10.4230/LIPIcs.ESA.2021.50.
https: / / doi.org/ 10.4230 / LIPIcs.ESA.2021.50

[23] Сванте Янсон. Хвостовые оценки сумм геометрических и экспоненциальных переменных. Письма о статистике и вероятности, 135:1–6, 2018. doi:10.1016/j.spl.2017.11.017.
https://doi.org/10.1016/j.spl.2017.11.017

[24] Дональд Эрвин Кнут. Искусство компьютерного программирования, том III. Аддисон-Уэсли, 2-е издание, 1998 г. URL: https://www.worldcat.org/oclc/312994415.
https://www.worldcat.org/oclc/312994415

[25] Робин Котари и Райан О'Доннелл. Средняя оценка при наличии исходного кода; или квантовые методы Монте-Карло. В материалах ежегодного симпозиума ACM-SIAM по дискретным алгоритмам 2023 г. (SODA'23), страницы 1186–1215, 2023. doi:10.1137/1.9781611977554.ch44.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

[26] Майкл А. Нильсен и Исаак Л. Чуанг. Квантовые вычисления и квантовая информация. Издательство Кембриджского университета, 2002.

[27] Эшвин Наяк и Феликс Ву. Сложность квантового запроса аппроксимации медианы и связанной с ней статистики. В материалах 31-го ежегодного симпозиума ACM SIGACT по теории вычислений (STOC'99), страницы 384–393, 1999. arXiv:quant-ph/9804066, doi:10.1145/301250.301349.
https: / / doi.org/ 10.1145 / 301250.301349
Arxiv: колич-фот / 9804066

[28] Б. Роос. Биномиальная аппроксимация биномиального распределения Пуассона: разложение Кравчука. Теория вероятностей и ее приложения, 45(2):258–272, 2001. doi:10.1137/S0040585X9797821X.
https:///doi.org/10.1137/S0040585X9797821X

[29] Роберт М. Янг. 75.9 Константа Эйлера. The Mathematical Gazette, 75(472):187–190, 1991. doi:10.2307/3620251.
https: / / doi.org/ 10.2307 / 3620251

Цитируется

Эта статья опубликована в Quantum под Creative Commons Attribution 4.0 International (CC BY 4.0) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.