Швидке квантове розрізання ланцюга за допомогою рандомізованих вимірювань

Швидке квантове розрізання ланцюга за допомогою рандомізованих вимірювань

Вихідний вузол: 1990460

Ангус Лоу1,2, Матія Медвідович1,3,4, Ентоні Хейс1, Лі Дж. О'Ріордан1, Томас Р. Бромлі1, Хуан Мігель Аррацола1і Натан Кіллоран1

1Ксанаду, Торонто, Онтаріо, M5G 2C8, Канада
2Центр теоретичної фізики, Массачусетський технологічний інститут, Кембридж, Массачусетс, 02139, США
3Центр обчислювальної квантової фізики, Інститут Флетайрон, Нью-Йорк, Нью-Йорк, 10010, США
4Факультет фізики, Колумбійський університет, Нью-Йорк, 10027, США

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

абстрактний

Ми пропонуємо новий метод збільшення розміру квантового обчислення за межі кількості фізичних кубітів, доступних на одному пристрої. Це досягається випадковим вставленням каналів вимірювання та підготовки, щоб виразити вихідний стан великої схеми як роздільний стан між окремими пристроями. У нашому методі використовуються рандомізовані вимірювання, в результаті чого вибірка накладних витрат становить $widetilde{O}(4^k / varepsilon ^2)$, де $varepsilon $ — точність обчислення, а $k$ — кількість паралельних проводів, які «вирізати», щоб отримати менші підсхеми. Ми також показуємо теоретико-інформаційну нижню межу $Omega(2^k / varepsilon ^2)$ для будь-якої порівнянної процедури. Ми використовуємо наші методи, щоб показати, що схеми в алгоритмі квантової наближеної оптимізації (QAOA) із шарами заплутування $p$ можуть бути змодельовані схемами на частці вихідної кількості кубітів із накладними витратами, які становлять приблизно $2^{O(pkappa) }$, де $kappa$ — розмір відомого збалансованого розділювача вершин графа, який кодує задачу оптимізації. Ми отримуємо числові докази практичного прискорення, використовуючи наш метод, застосований до QAOA, порівняно з попередньою роботою. Нарешті, ми досліджуємо практичну можливість застосування процедури розрізання ланцюга до великомасштабних задач QAOA на кластерних графах за допомогою симулятора $30$-кубітів для оцінки варіаційної енергії проблеми $129$-кубітів, а також для виконання $62$-кубітного симулятора. -кубітна оптимізація.

► Дані BibTeX

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

[1] https://​/​github.com/​XanaduAI/​randomized-measurements-circuit-cutting (2022).
https://​/​github.com/​XanaduAI/​randomized-measurements-circuit-cutting

[2] Скотт Ааронсон і Деніел Готтесман «Покращене моделювання схем стабілізатора» Phys. Rev. A 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

[3] J. Avron, Ofer Casper та Ilan Rozen, «Квантова перевага та зменшення шуму в розподілених квантових обчисленнях» Phys. Rev. A 104, 052404 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.104.052404

[4] Томас Айраль, Франсуа-Марі Ле Режан, Зейн Салім, Юрій Алексєєв та Мартін Сухара, «Квантовий розподіл і обчислення: демонстрація апаратного забезпечення та шумове моделювання» 2020 Щорічний симпозіум IEEE Computer Society з НВІС (ISVLSI) 138–140 (2020).
https://​/​doi.org/​10.1109/​ISVLSI49217.2020.00034

[5] Ф. Барратт, Джеймс Дборін, Матіас Бал, Від Стоєвіч, Френк Полманн та А. Г. Грін, «Паралельне квантове моделювання великих систем на малих комп’ютерах NISQ» npj Квантова інформація 7, 79 (2021).
https:/​/​doi.org/​10.1038/​s41534-021-00420-3

[6] Вілле Бергхольм, Джош Ізаак, Марія Шульд, Крістіан Гоголін, Шахнаваз Ахмед, Вішну Аджит, М. Сохайб Алам, Гільєрмо Алонсо-Лінахе, Б. Акаш Нараянан, Алі Асаді, Хуан Мігель Арразола, Уткарш Азад, Сем Баннінг, Карстен Бланк, Томас Р. Бромлі, Бенджамін А. Кордьє, Джек Сероні, Ален Дельгадо, Олівія Ді Маттео, Амінтор Дуско, Таня Гарг, Дієго Гуала, Ентоні Хейз, Райан Хілл, Аруса Іджаз, Теодор Ісакссон, Девід Ітта, Соран Джахангірі, Пратік Джейн, Едвард Цзян, Анкіт Ханделваль, Корбініан Коттманн, Роберт А. Ленг, Крістіна Лі, Томас Лоу, Ангус Лоу, Кері Маккірнан, Йоганнес Якоб Мейер, Х. А. Монтаньєс-Баррера, Ромен Мояр, Зейю Ніу, Лі Джеймс О'Ріордан, Стівен Уд, Ашіш Паніграхі, Че-Юн Парк, Даніель Полатайко, Ніколас Кесада, Чейс Робертс, Наум Са, Ісідор Шох, Борун Ши, Шулі Шу, Сукін Сім, Аршпріт Сінгх, Інгрід Страндберг, Джей Соні, Антал Сава, Сліман Табет, Родріго А. Варгас-Ернандес , Тревор Вінсент, Нікола Вітуччі, Моріс Вебер, Девід Віріхс, Роланд Вірсема, Моріц Вілманн, Вінсент Вонг, Шаомінг Чжан і Натан Кіллоран, «PennyLane: автоматична диференціація гібридних квантово-класичних обчислень» (2018).
https://​/​doi.org/​10.48550/​ARXIV.1811.04968
https://​/​arxiv.org/​abs/​1811.04968

[7] Sergey Bravyiand David Gosset «Покращене класичне моделювання квантових схем, домінуючих Кліффордом Гейтсом» Phys. Преподобний Летт. 116, 250501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.116.250501

[8] Сергій Бравий, Девід Госсет і Раміс Мовассаг, «Класичні алгоритми для квантових середніх значень» Nature Physics 17, 337–341 (2021).
https:/​/​doi.org/​10.1038/​s41567-020-01109-8

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

[10] Сергій Бравий, Олександр Кліш, Роберт Кеніг і Юджин Танг, «Перешкоди для варіаційної квантової оптимізації від захисту симетрії» Phys. Преподобний Летт. 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

[11] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard, “Моделювання квантових ланцюгів шляхом розкладу стабілізатора низького рангу” Quantum 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[12] Тханг Нгуєн Буі та Курт Джонс «Пошук хороших наближених вершин і реберних розділень є NP-складним» Information Processing Letters 42, 153–159 (1992).
https:/​/​doi.org/​10.1016/​0020-0190(92)90140-Q
https://​/​www.sciencedirect.com/​science/​article/​pii/​002001909290140Q

[13] Франческо Бушемі та Ніланджана Датта «Квантова ємність каналів із довільно корельованим шумом» IEEE Transactions on Information Theory 56, 1447–1460 (2010).
https://​/​doi.org/​10.1109/​TIT.2009.2039166

[14] Senrui Chen, Wenjun Yu, Pei Zeng і Steven T. Flammia, “Rubust Shadow Estimation” PRX Quantum 2, 030348 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.030348

[15] Ендрю М. Чайлдс, Юань Су, Мінь Ч. Чан, Натан Вібе та Шучен Чжу, «Теорія помилки Троттера з комутаторним масштабуванням», Фізичний огляд X 11 (2021).
https: / / doi.org/ 10.1103 / physrevx.11.011020

[16] Томас М. Ковер і Джой А. Томас «Елементи теорії інформації» Вайлі (2005).
https://​/​doi.org/​10.1002/​047174882x

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

[18] Андреас Ельбен, Стівен Т. Фламмія, Син-Юань Хуанг, Річард Куенг, Джон Прескілл, Бенуа Вермерш і Пітер Золлер, «Набір інструментів рандомізованого вимірювання» (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.11374
https://​/​arxiv.org/​abs/​2203.11374

[19] Лео Фанг, Андреас Хен, Харун Байрактар ​​і Сем Стенвік, «NVIDIA/​cuQuantum: cuQuantum v22.05.0» (2022).
https://​/​doi.org/​10.5281/​zenodo.6574510

[20] Роберт М. Фано «Передача інформації: статистична теорія комунікацій» MIT Press (1966).

[21] Едвард Фархі, Девід Гамарнік і Сем Гутманн, «Алгоритм квантової наближеної оптимізації потребує перегляду всього графіка: типовий випадок» (2020).
https://​/​doi.org/​10.48550/​ARXIV.2004.09002
https://​/​arxiv.org/​abs/​2004.09002

[22] Едвард Фархі, Девід Гамарнік і Сем Гутманн, «Алгоритм квантової наближеної оптимізації потребує перегляду всього графіка: найгірші приклади» (2020).
https://​/​doi.org/​10.48550/​ARXIV.2005.08747
https://​/​arxiv.org/​abs/​2005.08747

[23] Едвард Фархі, Джеффрі Голдстоун і Сем Гутманн, «Алгоритм квантової наближеної оптимізації» (2014).
https://​/​doi.org/​10.48550/​ARXIV.1411.4028
https://​/​arxiv.org/​abs/​1411.4028

[24] Едвард Фархі, Джеффрі Голдстоун і Сем Гутманн, «Алгоритм квантової наближеної оптимізації, застосований до проблеми обмеження виникнення» (2014).
https://​/​doi.org/​10.48550/​ARXIV.1412.6062
https://​/​arxiv.org/​abs/​1412.6062

[25] Едвард Фархіанд Арам В. Харроу «Квантова перевага через квантовий наближений алгоритм оптимізації» (2016).
https://​/​doi.org/​10.48550/​ARXIV.1602.07674
https://​/​arxiv.org/​abs/​1602.07674

[26] Uriel Feige, MohammadTaghi Hajiaghayi та James R. Lee, “Improved Approximation Algorithms for Minimum Weight Vertex Separators” SIAM Journal on Computing 38, 629–657 (2008).
https://​/​doi.org/​10.1137/​05064299X

[27] Джонні Грейанд Стефанос Куртіс «Гіпероптимізоване скорочення тензорної мережі» Квант 5, 410 (2021).
https:/​/​doi.org/​10.22331/​q-2021-03-15-410

[28] М. Гуца, Дж. Кан, Р. Куенг і Дж. А. Тропп, «Швидка томографія стану з оптимальними межами похибки» Журнал фізики A: Математичні та теоретичні 53, 204001 (2020).
https://​/​doi.org/​10.1088/​1751-8121/​ab8111

[29] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu та Nengkun Yu, “Sample-Optimal Tomography of Quantum States” IEEE Transactions on Information Theory 63, 5628–5641 (2017).
https://​/​doi.org/​10.1109/​TIT.2017.2719044

[30] Стюарт Гедфілд, Чжіхуй Ван, Брайан О’Горман, Елеанор Г. Ріффель, Давід Вентуреллі та Рупак Бісвас, «Від квантового алгоритму наближеної оптимізації до квантового змінного оператора Ansatz» Алгоритми 12 (2019).
https://​/​doi.org/​10.3390/​a12020034
https:/​/​www.mdpi.com/​1999-4893/​12/​2/​34

[31] Майкл Городецький, Пітер В. Шор і Мері Бет Раскай, «Канали розриву заплутаності» Огляди в математичній фізиці 15, 629–641 (2003).
https://​/​doi.org/​10.1142/​S0129055X03001709

[32] Сінь-Юань Хуанг, Річард Куенг і Джон Прескілл, «Передбачення багатьох властивостей квантової системи на основі дуже кількох вимірювань» Nature Physics 16, 1050–1057 (2020).
https:/​/​doi.org/​10.1038/​s41567-020-0932-7

[33] Вільям Хаггінс, Піюш Патіл, Бредлі Мітчелл, К. Біргітта Уейлі та Е. Майлз Стоуденмайр, «На шляху до квантового машинного навчання з тензорними мережами» Квантова наука та технологія 4, 024001 (2019).
https://​/​doi.org/​10.1088/​2058-9565/​aaea94

[34] Річард Куенґанд Девід Гросс «Стані стабілізатора кубіту є складними проективними 3-дизайнами» (2015).
https://​/​doi.org/​10.48550/​ARXIV.1510.02767
https://​/​arxiv.org/​abs/​1510.02767

[35] Джунде Лі, Махабубул Алам і Сваруп Гош, «Великомасштабна квантова наближена оптимізація за допомогою розділяй і володарюй» (2021).
https://​/​doi.org/​10.48550/​ARXIV.2102.13288
https://​/​arxiv.org/​abs/​2102.13288

[36] Сет Ллойд, Марія Шульд, Аруса Іджаз, Джош Ізаак і Натан Кіллоран, «Квантові вбудовування для машинного навчання» (2020).
https://​/​doi.org/​10.48550/​ARXIV.2001.03622
https://​/​arxiv.org/​abs/​2001.03622

[37] Ангус Лоуїд та Ешвін Наяк «Нижні межі для вивчення квантових станів за допомогою вимірювань в одній копії» (2022).
https://​/​doi.org/​10.48550/​ARXIV.2207.14438
https://​/​arxiv.org/​abs/​2207.14438

[38] Данило Ликов, Джонатан Вурц, Коді Пул, Марк Саффман, Том Ноель та Юрій Алексєєв, «Пороги частоти дискретизації для квантової переваги алгоритму квантової наближеної оптимізації» (2022).
https://​/​doi.org/​10.48550/​ARXIV.2206.03579
https://​/​arxiv.org/​abs/​2206.03579

[39] Ігор Л. Маркованд Яоюнь Ши «Моделювання квантових обчислень шляхом скорочення тензорних мереж» SIAM Journal on Computing 38, 963–981 (2008).
https: / / doi.org/ 10.1137 / 050644756

[40] Саймон С. Маршалл, Каспер Гюрік і Ведран Дунько, «Вимірне квантове машинне навчання за допомогою малих квантових комп’ютерів» (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.13739
https://​/​arxiv.org/​abs/​2203.13739

[41] Матія Медвідович і Джузеппе Карлео «Класичне варіаційне моделювання квантового алгоритму наближеної оптимізації» npj Квантова інформація 7 (2021).
https: / / doi.org/ 10.1038 / s41534-021-00440-z

[42] Косуке Мітараян і Кейсуке Фуджі «Створення віртуального двокубітового вентиля шляхом вибірки однокубітових операцій» New Journal of Physics 23, 023021 (2021).
https://​/​doi.org/​10.1088/​1367-2630/​abd7bc

[43] Косуке Мітараян і Кейсуке Фуджі «Накладні витрати для моделювання нелокального каналу з локальними каналами шляхом квазіймовірнісної вибірки» Квант 5, 388 (2021).
https:/​/​doi.org/​10.22331/​q-2021-01-28-388

[44] Філіпп Моріц, Роберт Нісіхара, Стефані Ванг, Олексій Туманов, Річард Ляу, Ерік Лянг, Меліх Елібол, Зонгхен Янг, Вільям Пол, Майкл І. Джордан та Іон Стойка, «Ray: розподілена структура для нових програм ШІ» (2017) .
https://​/​doi.org/​10.48550/​ARXIV.1712.05889
https://​/​arxiv.org/​abs/​1712.05889

[45] Акоп Пашаян, Джоел Дж. Уолман і Стівен Д. Бартлетт, «Оцінка ймовірностей результатів квантових схем за допомогою квазіймовірностей» Phys. Преподобний Летт. 115, 070501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.115.070501

[46] Tianyi Peng, Aram W. Harrow, Maris Ozols і Xiaodi Wu, “Simulation Large Quantum Circuits on a Small Quantum Computer” Physical Review Letters 125 (2020).
https://​/​doi.org/​10.1103/​physrevlett.125.150504

[47] Майкл А. Перлін, Зейн Х. Салім, Мартін Сухара та Джеймс К. Осборн, «Квантова розрізка ланцюга за допомогою томографії максимальної правдоподібності» npj Квантова інформація 7 (2021).
https:/​/​doi.org/​10.1038/​s41534-021-00390-6

[48] Альберто Перуццо, Джаррод МакКлін, Пітер Шедболт, Ман-Хонг Юнг, Сяо-Ці Чжоу, Пітер Дж. Лав, Алан Аспуру-Гузік та Джеремі Л. О'Браєн, «Варіаційний розв’язувач власних значень на фотонному квантовому процесорі» Nature Communications 5 (2014).
https: / / doi.org/ 10.1038 / ncomms5213

[49] Крістоф Півето та Девід Саттер «Концюгове в’язання з класичним спілкуванням» (2022).
https://​/​doi.org/​10.48550/​ARXIV.2205.00016
https://​/​arxiv.org/​abs/​2205.00016

[50] Зейн Х. Салім, Тіг Томеш, Майкл А. Перлін, Пранав Гокхале та Мартін Сухара, «Квантова розділяй і володарюй для комбінаторної оптимізації та розподілених обчислень» (2021).
arXiv: 2107.07532

[51] Ігал Сасон і Серхіо Верду «$f$ -нерівності розбіжностей» IEEE Transactions on Information Theory 62, 5973–6006 (2016).
https://​/​doi.org/​10.1109/​TIT.2016.2603151

[52] Марія Шульд, Алекс Бочаров, Кріста М. Своре та Натан Вібе, «Центроцентричні квантові класифікатори», Physical Review A 101 (2020).
https://​/​doi.org/​10.1103/​physreva.101.032308

[53] Марія Шульд, Вілле Бергхольм, Крістіан Гоголін, Джош Ізаак і Натан Кіллоран, «Оцінка аналітичних градієнтів на квантовому обладнанні» Phys. Rev. A 99, 032331 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.99.032331

[54] Хайк Шукуріан, Торстен Уайлд, Аксель Ауветер і Арндт Боде, «Прогнозування споживання енергії та енергоспоживання сильних і слабких масштабованих додатків HPC» Суперкомп’ютерні кордони та інновації 1, 20–41 (2014).
https://​/​doi.org/​10.14529/​jsfi140202

[55] Вей Танганд Маргарет Мартоносі «ScaleQC: масштабована структура для гібридних обчислень на квантових і класичних процесорах» (2022).
https://​/​doi.org/​10.48550/​ARXIV.2207.00933
https://​/​arxiv.org/​abs/​2207.00933

[56] Ewout Van Den Berg «Простий метод вибірки випадкових операторів Кліффорда» 2021 Міжнародна конференція IEEE з квантових обчислень та інженерії (QCE) 54–59 (2021).
https: / / doi.org/ 10.1109 / QCE52317.2021.00021

[57] Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel, “Quantum approximate optimization algorithm for MaxCut: A fermionic view” Phys. Rev. A 97, 022304 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.022304

[58] Джон Вотрус «Теорія квантової інформації», Cambridge University Press (2018).
https: / / doi.org/ 10.1017 / 9781316848142

[59] Зак Вебб «Група Кліффорда формує унітарний 3-дизайн» (2015).
https://​/​doi.org/​10.48550/​ARXIV.1510.02769
https://​/​arxiv.org/​abs/​1510.02769

[60] Роланд Вірсема, Леонардо Геріні, Хуан Феліпе Карраскілья та Леандро Аоліта, «Підвищення зв’язності схем завдяки квантово-класично-квантовим інтерфейсам» (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.04984
https://​/​arxiv.org/​abs/​2203.04984

[61] Xiao Yuan, Jinzhao Sun, Junyu Liu, Qi Zhao, and You Zhou, “Quantum Simulation with Hybrid Tensor Networks” Phys. Преподобний Летт. 127, 040501 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.127.040501

[62] Huangjun Zhu «Багатокубітні групи Кліффорда є унітарними 3-дизайнами» Phys. Rev. A 96, 062336 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Цитується

[1] Ліранде Піра та Кріс Феррі, «Запрошення до розподілених квантових нейронних мереж», arXiv: 2211.07056, (2022).

[2] Лукас Бреннер, Крістоф Півето та Девід Саттер, «Оптимальне різання дроту за допомогою класичної комунікації», arXiv: 2302.03366, (2023).

[3] Метью ДеКросс, Елі Чертков, Меган Кохаген і Майкл Фосс-Фейг, «Компіляція повторного використання Qubit із вимірюванням і скиданням у середині схеми», arXiv: 2210.08039, (2022).

[4] Крістіан Уфрехт, Маніраман Періясамі, Себастьян Рітш, Деніел Д. Шерер, Аксель Плінге та Крістофер Мутшлер, «Розрізання багатоконтрольних квантових воріт за допомогою обчислення ZX», arXiv: 2302.00387, (2023).

[5] Марвін Бехтольд, Йоганна Барзен, Френк Лейманн, Олександр Мандл, Джуліан Обст, Фелікс Тругер і Бенджамін Ведер, «Дослідження впливу відключення ланцюга в QAOA для проблеми MaxCut на пристроях NISQ», arXiv: 2302.01792, (2023).

[6] Рітаджит Маджумдар і Крістофер Дж. Вуд, «Розрізання квантової схеми з усуненням помилок», arXiv: 2211.13431, (2022).

[7] Деніел Т. Чен, Зейн Х. Салім і Майкл А. Перлін, «Квантова розділяй і володарюй для класичних тіней», arXiv: 2212.00761, (2022).

[8] Гідеон Учехара, Тор М. Аамодт і Олівія Ді Маттео, «Оптимізація ланцюга, натхненного обертанням», arXiv: 2211.07358, (2022).

[9] Карлос А. Ріофріо, Олівер Мітевскі, Кейтлін Джонс, Флоріан Креллнер, Александар Вучковіч, Джозеф Доч, Йоганнес Клепш, Томас Емер та Андре Лукков, «Характеристика продуктивності квантових генеративних моделей», arXiv: 2301.09363, (2023).

[10] Дієго Гуала, Шаомінг Чжан, Естер Круз, Карлос А. Ріофріо, Йоганнес Клепш і Хуан Мігель Арразола, «Практичний огляд класифікації зображень за допомогою квантових схем варіаційної тензорної мережі», arXiv: 2209.11058, (2022).

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

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

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

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