Прискорення квантових алгоритмів із попереднім обчисленням

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

читають: 0

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

Вільям Дж. Хаггінс і Джаррод Р. МакКлін

Google Quantum AI, Венеція, Каліфорнія, США

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

абстрактний

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

► Дані BibTeX

@article{Huggins2024acceleratingquantum, doi = {10.22331/q-2024-02-22-1264}, url = {https://doi.org/10.22331/q-2024-02-22-1264}, title = {Прискорення { Q}квантові {A}алгоритми з {P}повторним обчисленням}, автор = {Huggins, William J. and McClean, Jarrod R.}, journal = {{Quantum}}, issn = {2521-327X}, видавець = {{ Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, том = {8}, сторінки = {1264}, місяць = лютий, рік = {2024} }

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

[1] С Ааронсон. Обмеження квантових порад і одностороннього спілкування. У працях. 19-та щорічна конференція IEEE з обчислювальної складності, 2004 р., сторінки 320–332. IEEE, 2004. ISBN 9780769521206. 10.1109/ccc.2004.1313854.
https:///doi.org/10.1109/ccc.2004.1313854

[2] Скотт Ааронсон і Андріс Амбайніс. Зв'язок. У матеріалах сорок сьомого щорічного симпозіуму ACM з теорії обчислень, STOC '15, сторінки 307–316, Нью-Йорк, Нью-Йорк, США, 14 червня 2015 р. ACM. ISBN 9781450335362. 10.1145/2746539.2746547.
https: / / doi.org/ 10.1145 / 2746539.2746547

[3] Скотт Ааронсон і Гай Н. Ротблюм. Делікатне вимірювання квантових станів і диференціальної конфіденційності. 18 квітня 2019 р. URL-адреса http:///arxiv.org/abs/1904.08747.
arXiv: 1904.08747

[4] Раян Беббуш, Джаррод Р. Макклін, Майкл Ньюман, Крейг Гідні, Серхіо Бойшо та Хартмут Невен. Зосередьтеся не тільки на квадратичному прискоренні, щоб отримати квантову перевагу з виправленням помилок. PRX quantum, 2 (1): 010103, 29 березня 2021 р. ISSN 2691-3399. 10.1103/prxquantum.2.010103.
https: / / doi.org/ 10.1103 / prxquantum.2.010103

[5] Деніел Джей Бернштейн і Таня Ланге. Нерівномірні тріщини в бетоні: потужність вільного попереднього обчислення. У Advances in Cryptology – ASIACRYPT 2013, конспекти лекцій з інформатики, сторінки 321–340. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. ISBN 9783642420443,9783642420450. 10.1007/978-3-642-42045-0_17.
https://doi.org/10.1007/978-3-642-42045-0_17

[6] Домінік Беррі, Крейг Гідні, Маріо Мотта, Джаррод Р. Макклін і Раян Беббуш. Кубітизація довільної базисної квантової хімії з використанням розрідженості та факторизації низького рангу. 6 лютого 2019 р. URL-адреса https:///doi.org/10.22331/q-2019-12-02-208.
https://doi.org/10.22331/q-2019-12-02-208

[7] Якоб Біамонте, Пітер Віттек, Нікола Панкотті, Патрік Ребентрост, Натан Вібе та Сет Ллойд. Квантове машинне навчання. Nature, 549 (7671): 195–202, вересень 2017 р. ISSN 0028-0836,1476-4687. 10.1038/nature23474.
https: / / doi.org/ 10.1038 / nature23474

[8] Сергій Бравий та Олексій Китаєв. Універсальне квантове обчислення з ідеальними гейтами Кліффорда та шумними анцилами. фіз. Rev. A, 71 (2): 022316, 22 лютого 2005 р. ISSN 1050-2947,1094-1622. 10.1103/physreva.71.022316.
https:///doi.org/10.1103/physreva.71.022316

[9] Сергій Бравий і Дмитро Маслов. Схеми без Адамара розкривають структуру групи Кліффорда. IEEE Trans. Інф. Теорія, 67 (7): 4546–4563, липень 2021 р. ISSN 0018-9448,1557-9654. 10.1109/тит.2021.3081415.
https:///doi.org/10.1109/tit.2021.3081415

[10] Ерл Т Кемпбелл і Джо О'Горман. Ефективний підхід магічного стану до поворотів на малий кут. 14 березня 2016. URL https:///doi.org/10.1088/2058-9565/1/1/015007.
https://doi.org/10.1088/2058-9565/1/1/015007

[11] Сітан Чен, Джордан Котлер, Сінь-Юань Хуан і Джеррі Лі. Експоненціальне розмежування між навчанням із квантовою пам’яттю та без неї. У 2021 році 62-й щорічний симпозіум IEEE з основ комп’ютерних наук (FOCS). IEEE, лютий 2022 р. 10.1109/focs52979.2021.00063.
https:///doi.org/10.1109/focs52979.2021.00063

[12] Ендрю Чайлдс, Робін Котарі та Роландо Д Сомма. Квантовий алгоритм для систем лінійних рівнянь з експоненціально покращеною залежністю від точності. SIAM J. Comput., 46 (6): 1920–1950, 1 січня 2017 р. ISSN 0097-5397. 10.1137/16M1087072.
https:///doi.org/10.1137/16M1087072

[13] Н. Коді Джонс, Джеймс Д. Вітфілд, Пітер Л. Макмехон, Ман-Хонг Юнг, Родні Ван Метер, Алан Аспуру-Гузік та Йосіхіса Ямамото. Швидше моделювання квантової хімії на відмовостійких квантових комп’ютерах. New J. Phys., 14 (11): 115023, 27 листопада 2012 р. ISSN 1367-2630. 10.1088/1367-2630/14/11/115023.
https://doi.org/10.1088/1367-2630/14/11/115023

[14] Педро К. С. Коста, Донг Ан, Ювал Р. Сандерс, Юань Су, Раян Беббуш і Домінік В. Беррі. Розв’язувач квантових лінійних систем оптимального масштабування за допомогою дискретної адіабатичної теореми. PRX quantum, 3 (4): 040303, 7 жовтня 2022 р. ISSN 2691-3399. 10.1103/prxquantum.3.040303.
https: / / doi.org/ 10.1103 / prxquantum.3.040303

[15] Джордан Котлер, Синь-Юань Хуанг і Джаррод МакКлін. Перегляд деквантування та квантової переваги в навчальних завданнях. 1 грудня 2021 р. URL-адреса http:///arxiv.org/abs/2112.00811.
arXiv: 2112.00811

[16] Шон Х Куї, Даніель Готтесман і Аніруд Крішна. Діагональні ворота в ієрархії Кліффорда. фіз. Rev. A, 95 (1), 26 січня 2017 р. ISSN 2469-9926,2469-9934. 10.1103/physreva.95.012329.
https:///doi.org/10.1103/physreva.95.012329

[17] Едвард Фархі, Джеффрі Голдстоун і Сем Гутман. Алгоритм квантової наближеної оптимізації. 14 листопада 2014 р. URL-адреса http:///arxiv.org/abs/1411.4028.
arXiv: 1411.4028

[18] Остін Дж. Фаулер. Оптимальне за часом квантове обчислення. 17 жовтня 2012 р. URL-адреса http:///arxiv.org/abs/1210.4626.
arXiv: 1210.4626

[19] Севаг Гарібян і Франсуа Ле Гал. Деквантування квантового перетворення сингулярного значення: жорсткість і застосування до квантової хімії та квантової гіпотези PCP. У матеріалах 54-го щорічного симпозіуму ACM SIGACT з теорії обчислень, STOC 2022, сторінки 19–32, Нью-Йорк, штат Нью-Йорк, США, 9 червня 2022 р. ACM. ISBN 9781450392648. 10.1145/3519935.3519991.
https: / / doi.org/ 10.1145 / 3519935.3519991

[20] Крейг Гідні та Мартін Екеро. Як розкласти 2048 біт цілих чисел RSA за 8 годин, використовуючи 20 мільйонів зашумлених кубітів. Quantum, 5 (433): 433, 15 квітня 2021 р. ISSN 2521-327X. 10.22331/q-2021-04-15-433.
https://doi.org/10.22331/q-2021-04-15-433

[21] Крейг Гідні та Остін Дж. Фаулер. Гнучка структура обчислень поверхневого коду з використанням станів AutoCCZ. 21 травня 2019 р. URL-адреса http:///arxiv.org/abs/1905.08916.
arXiv: 1905.08916

[22] Андраш Гільєн та Александр Поремба. Покращено квантові алгоритми для оцінки точності. 29 березня 2022 р. URL-адреса http:///arxiv.org/abs/2203.15993.
arXiv: 2203.15993

[23] Даніель Готтесман та Ісаак Л Чуанг. Квантова телепортація є універсальним обчислювальним примітивом. 2 серпня 1999 р. URL https:///doi.org/10.1038/46503.
https: / / doi.org/ 10.1038 / 46503

[24] Лео Грейді та Алі Кемаль Сіноп. Швидка наближена випадкова сегментація з використанням попереднього обчислення власного вектора. У 2008 році на конференції IEEE з комп’ютерного зору та розпізнавання образів, сторінки 1–8. IEEE, червень 2008 р. ISBN 9781424422425. 10.1109/cvpr.2008.4587487.
https:///doi.org/10.1109/cvpr.2008.4587487

[25] Лов К. Гровер. Швидкий квантово-механічний алгоритм для пошуку в базі даних. У матеріалах двадцять восьмого щорічного симпозіуму ACM з теорії обчислень – STOC '96, STOC '96, сторінки 212–219, Нью-Йорк, Нью-Йорк, США, 1996. ACM Press. ISBN 9780897917858. 10.1145/237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866

[26] Арам В. Харроу, Авінатан Хасидім і Сет Ллойд. Квантовий алгоритм для лінійних систем рівнянь. фіз. Rev. Lett., 103 (15): 150502, 9 жовтня 2009 р. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502

[27] Сінь-Юань Хуанг, Майкл Бротон, Джордан Котлер, Сітан Чен, Джеррі Лі, Масуд Мохсені, Хартмут Невен, Раян Беббуш, Річард Куенг, Джон Прескілл та Джаррод МакКлін. Квантова перевага в навчанні з експериментів. Наука, 376 (6598): 1182–1186, 10 червня 2022 р. ISSN 0036-8075,1095-9203. 10.1126/science.abn7293.
https:///doi.org/10.1126/science.abn7293

[28] Коді Джонс. Протоколи дистиляції для станів Фур'є в квантових обчисленнях. 12 березня 2013 р. URL-адреса http:///arxiv.org/abs/1303.3066.
arXiv: 1303.3066

[29] Джон Каллагер. Квантова перевага для проблеми природного потоку. У 2021 році на 62-му щорічному симпозіумі IEEE з основ комп’ютерних наук (FOCS), сторінки 897–908. IEEE, лютий 2022 р. 10.1109/focs52979.2021.00091.
https:///doi.org/10.1109/focs52979.2021.00091

[30] Річард Карп і Річард Ліптон. Деякі зв'язки між нерівномірними та рівномірними класами складності. У матеріалах дванадцятого щорічного симпозіуму ACM з теорії обчислень – STOC '80, STOC '80, сторінки 302–309, Нью-Йорк, Нью-Йорк, США, 28 квітня 1980 р. ACM Press. ISBN 9780897910170. 10.1145/800141.804678.
https: / / doi.org/ 10.1145 / 800141.804678

[31] Шелбі Кіммел, Седрік Йен-Ю Лін, Гуан Хао Лоу, Маріс Озолс і Теодор Дж. Йодер. Гамільтоніанське моделювання з оптимальною складністю вибірки. Npj Quantum Inf., 3 (1): 1–7, 30 березня 2017 р. ISSN 2056-6387,2056-6387. 10.1038/s41534-017-0013-7.
https://doi.org/10.1038/s41534-017-0013-7

[32] Франсуа Ле Галль. Експоненціальне поділ складності квантового та класичного онлайн-простору. У матеріалах вісімнадцятого щорічного симпозіуму ACM з паралелізму в алгоритмах і архітектурах, SPAA '06, сторінки 67–73, Нью-Йорк, Нью-Йорк, США, 30 липня 2006 р. ACM. ISBN 9781595934529. 10.1145/1148109.1148119.
https: / / doi.org/ 10.1145 / 1148109.1148119

[33] Лін Лін і Юй Тун. Оптимальна поліноміальна квантова фільтрація власних станів із застосуванням до вирішення квантових лінійних систем. Quantum, 4 (361): 361, 11 листопада 2020 р. ISSN 2521-327X. 10.22331/q-2020-11-11-361.
https://doi.org/10.22331/q-2020-11-11-361

[34] Даніель Літінскі. Чарівна дистиляція: не так дорого, як ви думаєте. Quantum, 3 (205): 205, 2 грудня 2019a. ISSN 2521-327X. 10.22331/q-2019-12-02-205.
https://doi.org/10.22331/q-2019-12-02-205

[35] Даніель Літінскі. Гра поверхневих кодів: великомасштабні квантові обчислення з ґратковою хірургією. Quantum, 3 (128): 128, 5 березня 2019b. ISSN 2521-327X. 10.22331/q-2019-03-05-128.
https://doi.org/10.22331/q-2019-03-05-128

[36] Сет Ллойд, Масуд Мохсені та Патрік Ребентрост. Квантовий аналіз головних компонент. Нац. Phys., 10 (9): 631–633, 27 вересня 2014 р. ISSN 1745-2473,1745-2481. 10.1038/nphys3029.
https:///doi.org/10.1038/nphys3029

[37] Джон М. Мартін, Зейн М. Россі, Ендрю К. Тан і Ісаак Л. Чуанг. Грандіозна уніфікація квантових алгоритмів. PRX quantum, 2 (4): 040203, 3 грудня 2021 р. ISSN 2691-3399. 10.1103/prxquantum.2.040203.
https: / / doi.org/ 10.1103 / prxquantum.2.040203

[38] Іман Марвіан і Сет Ллойд. Універсальний квантовий емулятор. 8 червня 2016 р. URL-адреса http:///arxiv.org/abs/1606.02734.
arXiv: 1606.02734

[39] Ф. Моцой, М. П. Кайхер і Ф. К. Вільгельм. Лінійні та логарифмічні часові композиції квантових багатотільних операторів. фіз. Rev. Lett., 119 (16): 160503, 20 жовтня 2017 р. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.119.160503.
https: / / doi.org/ 10.1103 / PhysRevLett.119.160503

[40] Майкл Нільсен. Оптичні квантові обчислення з використанням кластерних станів. фіз. Rev. Lett., 93 (4): 040503, 23 липня 2004 р. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.93.040503.
https: / / doi.org/ 10.1103 / PhysRevLett.93.040503

[41] Браян О'Горман, Вільям Дж. Хаггінс, Елеанор Г. Ріффель і К. Біргітта Вейлі. Узагальнені мережі обміну для короткострокових квантових обчислень. 13 травня 2019 р. URL-адреса http:///arxiv.org/abs/1905.05118.
arXiv: 1905.05118

[42] Пол Фам і Кріста М Свор. Двовимірна квантова архітектура найближчого сусіда для розкладання полілогарифмічної глибини. 2 липня 27 р. URL-адреса http:///arxiv.org/abs/2012.
arXiv: 1207.6655

[43] Р. Рауссендорф і Г. Дж. Брігель. Односторонній квантовий комп'ютер. фіз. Rev. Lett., 86 (22): 5188–5191, 28 травня 2001 р. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.86.5188.
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[44] Ювал Р. Сандерс, Домінік В. Беррі, Педро К. С. Коста, Луї В. Тесслер, Натан Вібе, Крейг Гідні, Хартмут Невен і Раян Беббуш. Компіляція відмовостійких квантових евристик для комбінаторної оптимізації. PRX quantum, 1 (2): 020312, 9 листопада 2020 р. ISSN 2691-3399. 10.1103/prxquantum.1.020312.
https: / / doi.org/ 10.1103 / prxquantum.1.020312

[45] Ден Шеперд і Майкл Бремнер. Тимчасово неструктуроване квантове обчислення. Proc. математика фіз. інж. Sci., 465 (2105): 1413–1439, 8 травня 2009 р. ISSN 1364-5021,1471-2946. 10.1098/rspa.2008.0443.
https: / / doi.org/ 10.1098 / rspa.2008.0443

[46] Пітер-Пайк Слоун, Ян Кауц і Джон Снайдер. Попередньо обчислена передача сяйва для візуалізації в реальному часі в динамічному низькочастотному освітленні. У матеріалах 29-ї щорічної конференції з комп'ютерної графіки та інтерактивних технологій, SIGGRAPH '02, сторінки 527–536, Нью-Йорк, штат Нью-Йорк, США, 1 липня 2002 р. ACM. ISBN 9781581135213. 10.1145/566570.566612.
https: / / doi.org/ 10.1145 / 566570.566612

[47] Джеймс Е Сміт. Дослідження стратегій прогнозування гілок. За 25 років міжнародних симпозіумів з архітектури комп’ютера (вибрані статті), ISCA '98, сторінки 202–215, Нью-Йорк, Нью-Йорк, США, 1 серпня 1998 р. ACM. ISBN 9781581130584. 10.1145/285930.285980.
https: / / doi.org/ 10.1145 / 285930.285980

[48] Роландо Д Сомма та Їгіт Субаші. Складність перевірки квантового стану в задачі квантових лінійних систем. PRX quantum, 2 (1): 010315, 27 січня 2021 р. ISSN 2691-3399. 10.1103/prxquantum.2.010315.
https: / / doi.org/ 10.1103 / prxquantum.2.010315

[49] Барбара М Терхал. Квантова корекція помилок для квантової пам'яті. Rev. Mod. Phys., 87 (2): 307–346, 7 квітня 2015 р. ISSN 0034-6861,1539-0756. 10.1103/revmodphys.87.307.
https: / / doi.org/ 10.1103 / revmodphys.87.307

[50] Сіньлан Чжоу, Деббі В Люн та Ісаак Л Чуан. Методологія побудови квантових логічних воріт. фіз. Rev. A, 62 (5), 18 жовтня 2000 р. ISSN 1050-2947,1094-1622. 10.1103/physreva.62.052316.
https:///doi.org/10.1103/physreva.62.052316

Цитується

[1] Дар Гілбоа та Джаррод Р. Макклін, «Експоненціальна квантова комунікаційна перевага в розподіленому навчанні», arXiv: 2310.07136, (2023).

[2] Пабло Родрігес-Граса, Рубен Ібаррондо, Хав’єр Гонсалес-Конде, Юе Бан, Патрік Ребентрост і Мікель Санс, «Квантове наближене підведення до степеня матриці густини за допомогою клонування», arXiv: 2311.11751, (2023).

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

Не вдалося отримати Перехресне посилання, наведене за даними під час останньої спроби 2024-02-22 13:13:06: Не вдалося отримати цитовані дані для 10.22331/q-2024-02-22-1264 з Crossref. Це нормально, якщо DOI був зареєстрований нещодавно.

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

Розповсюдження контенту та PR на основі SEO. Отримайте посилення сьогодні.
PlatoData.Network Vertical Generative Ai. Додайте собі сили. Доступ тут.
PlatoAiStream. Web3 Intelligence. Розширення знань. Доступ тут.
ПлатонЕСГ. вуглець, CleanTech, Енергія, Навколишнє середовище, Сонячна, Поводження з відходами. Доступ тут.
PlatoHealth. Розвідка про біотехнології та клінічні випробування. Доступ тут.
джерело: https://quantum-journal.org/papers/q-2024-02-22-1264/

Часова мітка: 22 Лютого, 2024

Часова мітка: Червень 1, 2023

Прискорення квантових алгоритмів із попереднім обчисленням

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

абстрактний

► Дані BibTeX

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

Цитується

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

Perceval: програмна платформа для дискретних змінних фотонних квантових обчислень

Універсальні квантові схеми для квантової хімії

Ефективна проти теорії Флоке для параметричного осцилятора Керра

Схеми просторово-часових квантових каналів

Теорема збереження енергії та флуктуаційна теорема несумісні для квантової роботи

Оптимальне кодування осциляторів на кілька осциляторів

Дискримінація та сертифікація невідомих квантових вимірювань

Вибірка важливості для стохастичного квантового моделювання

Квантовий алгоритм передачі повідомлень для оптимального та ефективного декодування

Масштабована та гнучка класична тіньова томографія з тензорними мережами

Про нас

Вертикальний пошук & Ai

платформа

Залишайтеся на зв'язку

рахунки