Повышенная сложность квантовых запросов при более простых входных данных

Повышенная сложность квантовых запросов при более простых входных данных

Отметка времени: 8 апреля 2024 г., 11:29

Ноэль Т. Андерсон1, Джей-Ю Чунг1, Шелби Киммел1, Да-Ён Ко2и Сяохань Е1,3

1Колледж Миддлбери, Миддлбери, Вирджиния, США
2Колледж Уильямс, Уильямстаун, Массачусетс, США
3Университет Брауна, Провиденс, Род-Айленд, США

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

Абстрактные

Алгоритмы квантовых программ для оценки функций иногда снижают сложность запроса, когда обещают, что входные данные имеют определенную структуру. Мы разрабатываем модифицированный алгоритм промежуточной программы, чтобы показать, что эти улучшения сохраняются даже без каких-либо предварительных обещаний, и мы распространяем этот подход на более общую проблему преобразования состояний. В качестве приложения мы доказываем экспоненциальные и суперполиномиальные квантовые преимущества в средней сложности запроса для нескольких задач поиска, обобщая «Поиск с советами» Монтанаро [Montanaro, TQC 2010].

Повышенная сложность квантовых запросов при более простых входных данных. Анализ данных PlatoBlockchain. Вертикальный поиск. Ай.

Рекомендованное изображение: дерево решений, использованное для создания одного из наших алгоритмов.

Популярное резюме

Мы ожидаем, что квантовые алгоритмы, как и классические алгоритмы, будут работать быстрее на более простых входных данных. Например, если вы ищете элемент в неупорядоченном списке, и существует много копий этого элемента, мы ожидаем, что в этой ситуации квантовый алгоритм должен работать быстрее по сравнению с ситуацией, когда есть только один отмеченный элемент, даже не зная, количество целевых элементов заранее. Действительно, для задачи поиска известно, как получить такое преимущество на более простых входах. Однако обобщение этой идеи на проблемы, выходящие за рамки поиска, является сложной задачей, поскольку нет очевидного способа отметить, что вычисление выполняется достаточно долго. Мы модифицируем несколько популярных алгоритмических фреймворков в модели запроса, чтобы создать флаги, которые предупреждают нас о том, достаточно ли долго выполняются вычисления, что позволяет нам завершить алгоритм раньше при более простых входных данных, не зная заранее, является ли экземпляр простым или сложным. В качестве приложения, учитывая распределение как простых, так и сложных входных данных для решения проблемы, мы можем проанализировать среднюю сложность запроса. Мы показываем, что определенные распределения входных данных для задач поиска дают большие средние преимущества квантовых запросов по сравнению с классическими алгоритмами.

► Данные BibTeX

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

[1] Андрис Амбайнис и Рональд де Вольф. Среднестатистическая сложность квантового запроса. Журнал физики A: Mathematical and General, 34(35):6741, 2001. doi:10.1088/0305-4470/34/35/302.
https:/​/​doi.org/​10.1088/​0305-4470/​34/​35/​302

[2] Дорит Ахаронов. Квантовые вычисления. Ежегодные обзоры вычислительной физики VI, страницы 259–346, 1999. doi:10.1142/​9789812815569_0007.
https: / / doi.org/ 10.1142 / 9789812815569_0007

[3] Мишель Бойер, Жиль Брассар, Питер Хойер и Ален Тапп. Жесткие границы квантового поиска. Fortschritte der Physik, 46(4-5):493–505, 1998. doi:10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2 -П.
<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

[4] Александр Белов. Программы Span для функций с 1-сертификатами постоянного размера: Расширенное резюме. В материалах сорок четвертого ежегодного симпозиума ACM по теории вычислений, STOC '12, страницы 77–84, 2012. doi:10.1145/​2213977.2213985.
https: / / doi.org/ 10.1145 / 2213977.2213985

[5] Жиль Брассар, Питер Хойер, Мишель Моска и Ален Тапп. Квантовое амплитудное усиление и оценка. В книге «Квантовые вычисления и информация», том 305 журнала Contemp. Математика, страницы 53–74. амер. Математика. Soc., Провиденс, Род-Айленд, 2002. doi:10.1090/conm/305/05215.
HTTPS: / / doi.org/ 10.1090 / conm / 305/05215

[6] Жиль Брассар, Питер Хойер и Ален Тапп. Квантовый счет. В книге «Автоматы, языки и программирование», страницы 820–831, 1998. doi:10.1007/​BFb0055105.
https: / / doi.org/ 10.1007 / BFb0055105

[7] Александр Белов и Бен В. Райхардт. Программы Span и квантовые алгоритмы для обнаружения st-связности и когтей. Конспект лекций по информатике, 7501 LNCS: 193–204, 2012. doi: 10.1007/978-3-642-33090-2_18.
https:/​/​doi.org/​10.1007/​978-3-642-33090-2_18

[8] Александр Белов и Ансис Росманис. Точная квантовая нижняя граница для приближенного счета с квантовыми состояниями. 2020. arXiv:2002.06879.
Arxiv: 2002.06879

[9] Салман Бейги и Лейла Тагави. Квантовое ускорение на основе классических деревьев решений. Quantum, 4:241, 2020. doi:10.22331/​q-2020-03-02-241.
https:/​/​doi.org/​10.22331/​q-2020-03-02-241

[10] Александр Белов и Дуял Ёлку. Билет в один конец в Лас-Вегас и квантового противника. 2023. arXiv:2301.02003.
Arxiv: 2301.02003

[11] Ричард. Клив, Артур. Экерт, Кьяра Маккиавелло и Микеле Моска. Возвращение к квантовым алгоритмам. Труды Лондонского королевского общества. Серия A: Математические, физические и технические науки, 454 (1969): 339–354, 1998. doi: 10.1098/​rspa.1998.0164.
https: / / doi.org/ 10.1098 / rspa.1998.0164

[12] Арьян Корнелиссен, Стейси Джеффри, Марис Озолс и Альваро Пьедрафита. Span-программы и квантовая временная сложность. На 45-м Международном симпозиуме по математическим основам информатики (MFCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. doi:10.4230/​LIPIcs.MFCS.2020.26.
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2020.26

[13] Крис Кейд, Эшли Монтанаро и Александр Беловс. Квантовые алгоритмы, эффективные по времени и пространству, для обнаружения циклов и проверки двудольности. Квантовая информация и вычисления, 18(1-2):18–50, 2018.

[14] Кай ДеЛоренцо, Шелби Киммел и Р. Тил Уиттер. Приложения квантового алгоритма для st-связности. На 14-й конференции по теории квантовых вычислений, связи и криптографии (TQC 2019), страницы 6: 1–6: 14, 2019. doi: 10.4230/​LIPIcs.TQC.2019.6.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2019.6

[15] Дмитрий Гринько, Жюльен Гакон, Криста Зуфаль и Стефан Вернер. Итеративная оценка квантовой амплитуды. npj Quantum Information, 7(1):52, март 2021 г. doi:10.1038/​s41534-021-00379-1.
https:/​/​doi.org/​10.1038/​s41534-021-00379-1

[16] Лов К. Гровер. Квантовая механика помогает найти иголку в стоге сена. Physical Review Letters, 79(2):325–328, 1997. doi:10.1103/​PhysRevLett.79.325.
https: / / doi.org/ 10.1103 / PhysRevLett.79.325

[17] Василий Хеффдинг. Вероятностные неравенства для сумм ограниченных случайных величин. Журнал Американской статистической ассоциации, 58(301):13–30, 1963. doi:10.1080/​01621459.1963.10500830.
https: / / doi.org/ 10.1080 / 01621459.1963.10500830

[18] Цуёси Ито и Стейси Джеффри. Приблизительные программы интервала. Algorithmica, 81(6):2158–2195, 2019. doi:10.1007/s00453-018-0527-1.
https:/​/​doi.org/​10.1007/​s00453-018-0527-1

[19] Майкл Джаррет, Стейси Джеффри, Шелби Киммел и Альваро Пьедрафита. Квантовые алгоритмы для решения связности и связанных с ними проблем. На 26-м ежегодном европейском симпозиуме по алгоритмам (ESA 2018), страницы 49: 1–49: 13, 2018. doi: 10.4230/​LIPIcs.ESA.2018.49.
https: / / doi.org/ 10.4230 / LIPIcs.ESA.2018.49

[20] Алексей Юрьевич Китаев. Квантовые измерения и проблема абелева стабилизатора. 1995. arXiv:quant-ph/9511026.
Arxiv: колич-фот / 9511026

[21] Трой Ли, Раджат Миттал, Бен В. Райхардт, Роберт Шпалек и Марио Сегеди. Сложность квантового запроса преобразования состояния. На 2011-м ежегодном симпозиуме IEEE по основам информатики в 52 г., страницы 344–353, 2011. doi:10.1109/​FOCS.2011.75.
https: / / doi.org/ 10.1109 / FOCS.2011.75

[22] Фредерик Манье, Эшвин Наяк, Жереми Роланд и Миклош Санта. Поиск через Quantum Walk. SIAM Journal on Computing, 40(1):142–164, 2011. doi:10.1137/​090745854.
https: / / doi.org/ 10.1137 / 090745854

[23] Эшли Монтанаро. Квантовый поиск с советами. На конференции по квантовым вычислениям, коммуникации и криптографии, страницы 77–93. Springer, 2010. doi:10.1007/​978-3-642-18073-6_7.
https:/​/​doi.org/​10.1007/​978-3-642-18073-6_7

[24] Бен В. Райхардт. Программы Span и сложность квантовых запросов: общая граница противника почти точна для каждой логической функции. 50-й ежегодный симпозиум IEEE по основам информатики, страницы 544–551, 2009 г. doi:10.1109/​FOCS.2009.55.
https: / / doi.org/ 10.1109 / FOCS.2009.55

[25] Бен В. Райхардт. Размышления об алгоритмах квантовых запросов. В материалах ежегодного симпозиума ACM-SIAM по дискретным алгоритмам 2011 года, материалы, страницы 560–569. 2011. doi:10.1137/1.9781611973082.44.
https: / / doi.org/ 10.1137 / 1.9781611973082.44

[26] Лейла Тагави. Упрощенный квантовый алгоритм решения задачи идентификации оракула. Квантово-машинный интеллект, 4(2):19, 2022. doi:10.1007/​s42484-022-00080-2.
https:/​/​doi.org/​10.1007/​s42484-022-00080-2

Цитируется

[1] Стейси Джеффри, Шелби Киммел и Альваро Пьедрафита, «Квантовый алгоритм выборки по краям пути», Arxiv: 2303.03319, (2023).

[2] Майкл Чекански, Шелби Киммел и Р. Тил Уиттер, «Надежные и экономичные алгоритмы квантовых запросов с двойным противником», Arxiv: 2306.15040, (2023).

Приведенные цитаты из САО / НАСА ADS (последнее обновление успешно 2024-04-11 15:45:18). Список может быть неполным, поскольку не все издатели предоставляют подходящие и полные данные о цитировании.

On Цитируемый сервис Crossref Данные о цитировании работ не найдены (последняя попытка 2024-04-11 15:45:17).

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

Отметка времени:

Больше от Квантовый журнал