Гібридний підхід «розділяй і володарюй» для алгоритмів пошуку дерева

Гібридний підхід «розділяй і володарюй» для алгоритмів пошуку дерева

Мітка часу: 23 березня 2023 р., 9:57
Вихідний вузол: 2029300

Матіс Реннела1, Себастьян Бранд2, Альфонс Лаарман2, і Ведран Дунько2

1Laboratoire de Physique de l'Ecole Normale Supérieure, Inria, CNRS, ENS-PSL, Mines-Paristech, Sorbonne Université, PSL Research University, Париж, Франція
2LIACS, Лейденський університет, Лейден, Нідерланди

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

абстрактний

Однією з проблем квантових комп’ютерів у найближчій та середньостроковій перспективі є обмежена кількість кубітів, які ми можемо використовувати для обчислень. Пошук методів, які досягають корисних квантових покращень за обмежень розміру, таким чином, є ключовим питанням у цій галузі. У цьому ключі нещодавно було показано, що гібридний класично-квантовий метод може допомогти забезпечити поліноміальне прискорення класичних алгоритмів «розділяй і володарюй», навіть якщо отримати доступ до квантового комп’ютера, набагато меншого за саму проблему. У цій роботі ми вивчаємо гібридний метод «розділяй і володарюй» у контексті алгоритмів пошуку по дереву та розширюємо його шляхом включення квантового відстеження, що дає кращі результати, ніж попередні методи на основі Гровера. Крім того, ми надаємо загальні критерії для поліноміального прискорення в контексті пошуку дерева та надаємо низку прикладів, коли поліноміальне прискорення може бути отримано за допомогою як завгодно менших квантових комп’ютерів. Ми надаємо умови для прискорень для добре відомого алгоритму DPLL і підтверджуємо безпорогові прискорення для алгоритму PPSZ (ядро найшвидшого точного розв’язувача булевої виконуваності) для класів формул, що добре поводяться. Ми також надаємо простий приклад, коли прискорення можна отримати незалежним від алгоритму способом, за певних добре вивчених теоретичних припущень складності. Нарешті, ми коротко обговоримо фундаментальні обмеження гібридних методів у забезпеченні прискорення для більших проблем.

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

У короткостроковій та середній перспективі, коли квантові комп’ютери мають обмежену кількість кубітів, певні екземпляри проблем можуть бути занадто великими, щоб їх можна було вирішити на квантовому комп’ютері. У цій ситуації природно дивитися на стратегії «розділяй і володарюй»: класично розділити проблему на частини, які достатньо малі, щоб їх можна було вирішити на квантовому комп’ютері, а потім об’єднати результати. Це називається квантово-класичним гібридним алгоритмом.

Алгоритми пошуку за деревом особливо підходять для цього гібридного підходу. Коли простір пошуку є повним бінарним деревом, легко розділити проблему на частини, достатньо малі для даного квантового комп’ютера, і все одно залишити (менше) квантове прискорення початкової проблеми. Однак у більшості класичних алгоритмів пошуку дерева гілки обрізаються під час пошуку, і залишається розріджене дерево. У цьому налаштуванні стає менш очевидним, чи все ще можна отримати невелике поліноміальне прискорення за допомогою гібридного алгоритму.

У цій статті ми вивчаємо цей гібридний метод «розділяй і володарюй» у контексті алгоритмів пошуку дерева, таких як алгоритми, розроблені для булевої виконуваності. Наш головний внесок полягає в тому, що ми забезпечуємо достатні умови для квантового прискорення та застосовуємо їх до двох добре відомих булевих алгоритмів виконання.

► Дані BibTeX

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

[1] Ведран Дунько, Імін Ге та Ігнасіо Сірак. «Прискорення обчислень за допомогою малих квантових пристроїв». Фізичні оглядові листи 121, 250501 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.121.250501

[2] Їмін Ге та Ведран Дунько. «Склад гібридного алгоритму для малих квантових комп’ютерів із застосуванням до пошуку гамільтонових циклів». Журнал математичної фізики 61, 012201 (2020).
https: / / doi.org/ 10.1063 / 1.5119235

[3] Ешлі Монтанаро. “Прискорення квантового блукання алгоритмів зворотного відстеження”. Теорія обчислень 14, 1–24 (2018).
https://​/​doi.org/​10.4086/​toc.2018.v014a015

[4] Мартін Девіс, Джордж Логеман і Дональд Лавленд. “Машина програма для доведення теорем”. Нью-Йоркський університет, Інститут математичних наук. (1961).
https: / / doi.org/ 10.1145 / 368273.368557

[5] Рамамохан Патурі, Павел Пудлак, Майкл Е. Сакс і Френсіс Зейн. «Покращений алгоритм експоненціального часу для k-SAT». Журнал ACM (JACM) 52, 337–364 (2005).
https: / / doi.org/ 10.1145 / 1066100.1066101

[6] Ерл Кемпбелл, Анкур Хурана та Ешлі Монтанаро. “Застосування квантових алгоритмів до проблем задоволення обмежень”. Квант 3, 167 (2019).
https:/​/​doi.org/​10.22331/​q-2019-07-18-167

[7] Симон Мартіель і Максим Ремо. “Практична реалізація квантового алгоритму зворотного відстеження”. У міжнародній конференції «Сучасні тенденції теорії та практики інформатики». Сторінки 597–606. Springer (2020).
https:/​/​doi.org/​10.1007/​978-3-030-38919-2_49

[8] Томас Дуехольм Гансен, Хаїм Каплан, Ор Замір та Урі Цвік. «Швидші алгоритми k-sat з використанням biased-ppsz». У матеріалах 51-го щорічного симпозіуму ACM SIGACT з теорії обчислень. Сторінки 578–589. STOC 2019Нью-Йорк, Нью-Йорк, США (2019). ACM.
https: / / doi.org/ 10.1145 / 3313276.3316359

[9] Армін Бір, Марійн Хойле та Ганс ван Маарен. «Довідник задовільності». Том 185. IOS press. (2009).

[10] Марк Мезард, Марк Мезард і Андреа Монтанарі. «Інформація, фізика та обчислення». Oxford University Press. (2009).
https: / / doi.org/ 10.1063 / 1.3397047

[11] Мартін Девіс і Гіларі Патнем. “Обчислювальна процедура для теорії кількісного визначення”. J. ACM 7, 201–215 (1960).
https: / / doi.org/ 10.1145 / 321033.321034

[12] Marijn JH Heule, Matti Juhani Järvisalo, Martin Suda та ін. «Опис розв’язувача та тестів». У матеріалах конкурсу SAT 2018. Департамент комп’ютерних наук Гельсінського університету (2018). url: http://​/​hdl.handle.net/​10138/​237063.
http://​/​hdl.handle.net/​10138/​237063

[13] Роберт Ньювенхейс, Альберт Оліверас і Чезаре Тінеллі. «Абстрактний DPLL і абстрактні теорії DPLL за модулем». У Міжнародній конференції з логіки для програмування штучного інтелекту та міркування. Сторінки 36–50. Springer (2005).
https:/​/​doi.org/​10.1007/​978-3-540-32275-7_3

[14] Жасмін Крістіан Бланшетт, Саша Бьоме та Лоуренс Полсон. «Розширення Sledgehammer за допомогою вирішувачів SMT». Журнал автоматизованих міркувань 51, 109–128 (2013).
https:/​/​doi.org/​10.1007/​s10817-013-9278-5

[15] Даніель Рольф. “Дерандомізація PPSZ для unique-k-SAT”. На міжнародній конференції з теорії та застосування тестування задовільності. Сторінки 216–225. Springer (2005).
https://​/​doi.org/​10.1007/​11499107_16

[16] Домінік Шедер і Джон П. Штайнбергер. “PPSZ для загального k-SAT-роблення аналізу Гертлі спрощеним і 3-SAT швидшим”. На 32-й Конференції з обчислювальної складності (CCC 2017). Том 79, сторінки 9:1–9:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017).
https://​/​doi.org/​10.4230/​LIPIcs.CCC.2017.9

[17] Даніель Рольф. «Покращена межа для алгоритму PPSZ/​schoning для 3-SAT». Journal on Satisfiability, Boolean Modeling and Computation 1, 111–122 (2006).
https://​/​doi.org/​10.3233/​SAT190005

[18] Тімон Гертлі. «3-SAT швидше та простіше — унікальні межі SAT для PPSZ загалом зберігаються». SIAM Journal on Computing 43, 718–729 (2014).
https: / / doi.org/ 10.1137 / 120868177

[19] Тімон Гертлі. «Подолання бар’єру PPSZ для унікального 3-SAT». З автоматів, мов і програмування: 41-й міжнародний колоквіум, ICALP 2014, Копенгаген, Данія, 8-11 липня 2014 р., Матеріали, частина I 41. Сторінки 600–611. Springer (2014).
https:/​/​doi.org/​10.1007/​978-3-662-43948-7_50

[20] Домінік Шедер. «PPSZ кращий, ніж ви думаєте». У 2021 році 62-й щорічний симпозіум IEEE з основ комп’ютерних наук (FOCS). Сторінки 205–216. (2022).
https://​/​doi.org/​10.1109/​FOCS52979.2021.00028

[21] Лов К. Гровер. «Швидкий квантово-механічний алгоритм для пошуку в базі даних». У матеріалах двадцять восьмого щорічного симпозіуму ACM з теорії обчислень. Сторінки 212–219. (1996).
https: / / doi.org/ 10.1145 / 237814.237866

[22] Андріс Амбайніс. “Алгоритми квантового пошуку”. ACM SIGACT News 35, 22–35 (2004).
https: / / doi.org/ 10.1145 / 992287.992296

[23] Андріс Амбайніс і Мартінс Кокайніс. «Квантовий алгоритм для оцінки розміру дерева, із застосуваннями для зворотного відстеження та ігор для двох гравців». У матеріалах 2-го щорічного симпозіуму ACM SIGACT з теорії обчислень. Сторінки 49–989. (1002).
https: / / doi.org/ 10.1145 / 3055399.3055444

[24] Майкл Джаррет і Кіанна Ван. «Покращені алгоритми квантового відстеження з використанням ефективних оцінок опору». Physical Review A 97, 022337 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.022337

[25] Домінік Дж. Мойлетт, Ноа Лінден і Ешлі Монтанаро. “Квантове прискорення проблеми комівояжера для графів з обмеженим ступенем”. фіз. Rev. A 95, 032323 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.032323

[26] Ніл Д. Джонс і Вільям Т. Лазер. “Повні задачі для детермінованого поліноміального часу”. Теоретична інформатика 3, 105 – 117 (1976).
https:/​/​doi.org/​10.1016/​0304-3975(76)90068-2

[27] Реймонд Грінлоу, Х. Джеймс Гувер, Уолтер Л. Руццо та ін. “Обмеження паралельних обчислень: теорія P-повноти”. Oxford University Press on Demand. (1995).

[28] Томас Ленгауер і Роберт Тар'ян. «Асимптотично жорсткі межі компромісів між часом і простором у грі з камінчиками». Журнал ACM (JACM) 29, 1087–1130 (1982).
https: / / doi.org/ 10.1145 / 322344.322354

[29] Чарльз Х. Беннетт. «Компроміси час/простір для оборотних обчислень». SIAM Journal on Computing 18, 766–776 (1989).
https: / / doi.org/ 10.1137 / 0218053

[30] Т. Альтман та Ю. Ігарасі. «Приблизне сортування: послідовний і паралельний підхід». Ж. Інф. процес. 12, 154–158 (1989). url: http://​/​id.nii.ac.jp/​1001/​00059782/​.
http://​/​id.nii.ac.jp/​1001/​00059782/​

[31] Хун-Ю Лян і Цзін Хе. «Задовільність із залежністю від індексу». Journal of Computer Science and Technology 27, 668–677 (2012).
https:/​/​doi.org/​10.1007/​978-3-642-17517-6_7

[32] Марчелло Бенедетті, Джон Реальпе-Гомес і Алехандро Пердомо-Ортіс. «Машини Гельмгольца з квантовою підтримкою: квантово-класична структура глибокого навчання для промислових наборів даних у пристроях короткострокового розвитку». Квантова наука та технологія 3, 034007 (2018).
https://​/​doi.org/​10.1088/​2058-9565/​aabd98

[33] Арам В. Харроу. «Малі квантові комп’ютери та великі класичні набори даних» (2020) arXiv:2004.00026.
arXiv: 2004.00026

[34] Майкл Нільсен та Ісаак Чуанг. «Квантові обчислення та квантова інформація». Американська асоціація вчителів фізики. (2002).
https://​/​doi.org/​10.1017/​CBO9780511976667

[35] Роберт Б. Гріффітс і Чі-Шен Ніу. “Напівкласичне перетворення Фур’є для квантових обчислень”. фіз. Преподобний Летт. 76, 3228–3231 (1996).
https: / / doi.org/ 10.1103 / PhysRevLett.76.3228

[36] Роберт Рауссендорф і Ганс Дж. Брігель. «Односторонній квантовий комп’ютер». фіз. Преподобний Летт. 86, 5188–5191 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[37] Томас Е. О'Браєн, Браян Тарасінскі та Барбара М. Терхал. “Оцінка квантової фази множинних власних значень для маломасштабних (зашумлених) експериментів”. Новий журнал фізики 21, 023022 (2019).
https://​/​doi.org/​10.1088/​1367-2630/​aafb8e

[38] Акшай Аджагекар, Тревіс Хамбл і Фенгкі Ю. «Стратегії гібридного рішення на основі квантових обчислень для великомасштабних задач дискретно-неперервної оптимізації». Комп’ютери та хімічна інженерія 132, 106630 (2020).
https://​/​doi.org/​10.1016/​j.compchemeng.2019.106630

[39] Тяньї Пен, Арам В. Харроу, Маріс Озолс і Сяоді Ву. «Моделювання великих квантових схем на малому квантовому комп’ютері». Фізичні оглядові листи 125, 150504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.150504

[40] Сергій Бравий, Грем Сміт і Джон А. Смолін. «Торгівля класичними та квантовими обчислювальними ресурсами». Physical Review X 6 (2016).
https: / / doi.org/ 10.1103 / physrevx.6.021043

[41] Мартейн Свенне. «Вирішення SAT на шумних квантових комп’ютерах». https://​/​theses.liacs.nl/​1725 (2019). Бакалаврська робота.
https://​/​theses.liacs.nl/​1725

[42] Теодор Дж. Йодер, Гуан Хао Лоу та Ісаак Л. Чуанг. «Квантовий пошук з фіксованою точкою з оптимальною кількістю запитів». Фізичні оглядові листи 113 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.210501

[43] Алессандро Косентіно, Робін Котарі та Адам Петнік. «Деквантування одноразових квантових формул». На 8-й конференції з теорії квантових обчислень, комунікації та криптографії (TQC 2013). Том 22 Leibniz International Proceedings in Informatics (LIPIcs), сторінки 80–92. Дагштуль, Німеччина (2013). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https://​/​doi.org/​10.4230/​LIPIcs.TQC.2013.80

[44] Девід А. Баррінгтон. «Програми розгалуження розміру полінома обмеженої ширини розпізнають саме ті мови в NC1». Journal of Computer and System Sciences 38, 150–164 (1989).
https:/​/​doi.org/​10.1016/​0022-0000(89)90037-8

Цитується

[1] Каспер Гюрік, Кріс Кейд і Ведран Дунько, «До квантової переваги через топологічний аналіз даних», arXiv: 2005.02607, (2020).

[2] Кайл Е. К. Бут, Браян О'Горман, Джеффрі Маршалл, Стюарт Гедфілд та Елеанор Ріффель, «Квантове прискорене програмування обмежень», Квант 5, 550 (2021).

[3] Каспер Гюрік, Кріс Кейд і Ведран Дунько, «До квантової переваги через топологічний аналіз даних», Квант 6, 855 (2022).

Вищезазначені цитати від SAO / NASA ADS (останнє оновлення успішно 2023-03-25 02:02:00). Список може бути неповним, оскільки не всі видавці надають відповідні та повні дані про цитування.

On Служба, на яку посилається Crossref даних про цитування робіт не знайдено (остання спроба 2023-03-25 02:01:59).

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

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

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