Основні квантові підпрограми: пошук кількох позначених елементів і підсумовування чисел

Основні квантові підпрограми: пошук кількох позначених елементів і підсумовування чисел

Мітка часу: 14 березня 2024 р., 9:40
Basic quantum subroutines: finding multiple marked elements and summing numbers PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Йоран ван Апелдорн1, Сандер Гріблінг2 та Гарольд Ньюбоер3

1IViR і QuSoft, Амстердамський університет, Нідерланди
2Кафедра економетрики та дослідження операцій Тілбурзького університету, Тілбург, Нідерланди
3Інститут математики Кортевега–де Фріза та QuSoft Амстердамського університету, Нідерланди та факультет комп’ютерних наук Рурського університету Бохума, Німеччина та факультет математичних наук Копенгагенського університету, Данія

Вам цей документ цікавий чи ви хочете обговорити? Скайте або залиште коментар на 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/дельта$ і $log(1/rho)$ порівняно з простим застосуванням оцінки амплітуди. Щоб отримати покращену залежність $log(1/rho)$, ми використовуємо перший результат.

► Дані BibTeX

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

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

[2] Хосе А. Адель і П. Ходра. Точні колмогоровські та повні варіаційні відстані між деякими знайомими дискретними розподілами. Journal of Inequalities and Applications, 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: quant-ph / 9605034

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

[7] Жиль Брассар, Пітер Хоєр, Мікеле Моска та Ален Тапп. Підсилення та оцінка квантової амплітуди. Квантові обчислення та квантова інформація: Том тисячоліття, том 305 журналу Contemporary Mathematics, сторінки 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. Cambridge University Press, 2010.

[9] Ран Канетті, Гай Евен і Одед Голдрайх. Нижні межі для алгоритмів вибірки для оцінки середнього. Information Processing Letters, 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] П. Діаконіс і Д. Фрідман. Скінченні замінні послідовності. The Annals of Probability, 8(4):745–764, 1980. URL: https://​/​www.jstor.org/​stable/​2242823.
https://​/​www.jstor.org/​stable/​2242823

[13] Крістоф Дюрр і Петер Хоєр. Квантовий алгоритм для знаходження мінімуму, 1996. doi:10.48550/​arXiv.quant-ph/​9607014.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9607014
arXiv: quant-ph / 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: quant-ph / 9605043

[20] Лов К. Гровер. Квантові телеобчислення, 1997. Технічний меморандум Bell Labs ITD97-31630F. doi:10.48550/​arXiv.quant-ph/​9704012.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9704012
arXiv: quant-ph / 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: quant-ph / 9711043

[22] Ясін Хамуді. Квантова оцінка субгаусового середнього. У 29-му щорічному Європейському симпозіумі з алгоритмів (ESA 2021), том 204 Leibniz International Proceedings in Informatics (LIPIcs), сторінки 50:1–50:17, 2021. doi:10.4230/​LIPIcs.ESA.2021.50.
https://​/​doi.org/​10.4230/​LIPIcs.ESA.2021.50

[23] Сванте Янсон. Кінцеві межі для сум геометричних і експоненційних змінних. Statistics & Probability Letters, 135:1–6, 2018. doi:10.1016/​j.spl.2017.11.017.
https://​/​doi.org/​10.1016/​j.spl.2017.11.017

[24] Дональд Ервін Кнут. Мистецтво програмування, том III. Addison-Wesley, 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] Майкл А. Нільсен та Ісаак Л. Чуанг. Квантові обчислення та квантова інформація. Cambridge University Press, 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: quant-ph / 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 на 4.0) ліцензія. Авторське право залишається за оригінальними власниками авторських прав, такими як автори або їх установи.

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

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