Покращена складність квантового запиту на легших вхідних даних

Покращена складність квантового запиту на легших вхідних даних

Мітка часу: 8 квітня 2024 р., 11:29

Ноель Т. Андерсон1, Джей-У Чунг1, Шелбі Кіммел1, Да-Йон Ко2і Сяохан Є1,3

1Коледж Міддлбері, Міддлбері, Верхня Торонта, США
2Williams College, Williamstown, MA, США
3Університет Брауна, Провіденс, Род-Айленд, США

Вам цей документ цікавий чи ви хочете обговорити? Скайте або залиште коментар на SciRate.

абстрактний

Алгоритми програми Quantum span для оцінки функції іноді зменшують складність запиту, коли обіцяють, що вхідні дані мають певну структуру. Ми розробляємо модифікований алгоритм програми діапазону, щоб показати, що ці покращення зберігаються навіть без завчасної обіцянки, і ми поширюємо цей підхід на більш загальну проблему перетворення стану. Як додаток ми доводимо експоненціальні та суперполіноміальні квантові переваги в середній складності запиту для кількох проблем пошуку, узагальнюючи пошук Монтанаро з порадою [Montanaro, TQC 2010].

Покращена складність квантового запиту на спрощених вхідних даних PlatoBlockchain Data Intelligence. Вертикальний пошук. Ai.

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

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

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

► Дані BibTeX

► Список літератури

[1] Андріс Амбайніс і Рональд де Вольф. Усереднена складність квантового запиту. Journal of Physics 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] Доріт Ааронов. Квантові обчислення. Annual Reviews of Computational Physics 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., Providence, RI, 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] Олександр Бєлов і Бен В. Райхардт. Програми діапазону та квантові алгоритми для 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] Ар'ян Корнеліссен, Стейсі Джеффрі, Маріс Озолс і Альваро П'єдрафіта. Спанові програми та квантова часова складність. На 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-Connectivity. На 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 Квантова інформація, 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: quant-ph / 9511026

[21] Трой Лі, Раджат Міттал, Бен В. Райхардт, Роберт Шпалек і Маріо Сегеді. Складність квантового запиту перетворення стану. У 2011 році на 52-му щорічному симпозіумі IEEE з основ інформатики, сторінки 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).

Вищезазначені цитати від SAO / NASA ADS (останнє оновлення успішно 2024-04-11 15:45:18). Список може бути неповним, оскільки не всі видавці надають відповідні та повні дані про цитування.

On Служба, на яку посилається Crossref даних про цитування робіт не знайдено (остання спроба 2024-04-11 15:45:17).

Ця стаття опублікована в Quantum під Creative Commons Attribution 4.0 International (CC на 4.0) ліцензія. Авторське право залишається за оригінальними власниками авторських прав, такими як автори або їх установи.

Часова мітка:

Більше від Квантовий журнал