Розгляд затримки для стохастичних оптимізаторів у варіаційних квантових алгоритмах

Розгляд затримки для стохастичних оптимізаторів у варіаційних квантових алгоритмах

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

Метт Менікеллі1, Юнсу Ха2і Метью Оттен3

1Відділ математики та інформатики, Аргонська національна лабораторія, 9700 S. Cass Ave., Lemont, IL 60439
2Департамент промислової та системної інженерії Едварда П. Фітса, Університет штату Північна Кароліна, 915 Partners Way, Raleigh, NC 27601
3HRL Laboratories, LLC, 3011 Malibu Canyon Road, Malibu, CA 90265

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

абстрактний

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

Варіаційні квантові алгоритми є перспективними кандидатами для вирішення практичних завдань на квантових комп’ютерах короткого періоду. Проте процес оптимізації цих алгоритмів може бути обчислювально дорогим через дві потреби: 1) виконувати повторні вимірювання (знімки) на квантовому комп’ютері та 2) коригувати параметри квантової схеми. Тут ми пропонуємо новий алгоритм стохастичної оптимізації під назвою SHOALS (SHOt Adaptive Line Search), розроблений за припущенням, що час, витрачений на оптимізацію, виконуючи знімки, домінує над часом, витраченим на оптимізацію, виконуючи налаштування схеми. Ми демонструємо, що SHOALS перевершує інші алгоритми стохастичної оптимізації в цьому налаштуванні. Навпаки, коли час пострілу можна порівняти з часом перемикання схеми, алгоритми стохастичного градієнтного спуску виявляються більш ефективними. Розглядаючи компроміси між часом пуску, часом перемикання схеми та ефективністю алгоритму оптимізації, ми показуємо, що загальний час роботи варіаційних квантових алгоритмів можна значно скоротити.

► Дані BibTeX

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

[1] Бенджамін П. Ланьон, Джеймс Д. Вітфілд, Джефф Дж. Гіллетт, Майкл Е. Гогін, Марсело П. Алмейда, Іван Кассал, Джейкоб Д. Б’ямонте, Масуд Мохсені, Бен Дж. Пауелл, Марко Барб’єрі та ін. «Назустріч квантовій хімії на квантовому комп’ютері». Природна хімія 2, 106–111 (2010).
https://​/​doi.org/​10.1038/​nchem.483

[2] Ян С. Клоет, Меттью Р. Дітріх, Джон Аррінгтон, Олексій Базавов, Майкл Бішоф, Адам Фріз, Олексій В. Горшков, Анна Грасселіно, Кавтар Хафіді, Зубін Якоб та ін. «Можливості для ядерної фізики та квантової інформаційної науки» (2019). arXiv:1903.05453.
arXiv: 1903.05453

[3] Адам Сміт, М. С. Кім, Френк Полманн і Йоганнес Кнолле. «Моделювання квантової динаміки багатьох тіл на сучасному цифровому квантовому комп’ютері». npj Квантова інформація 5, 1–13 (2019).
https:/​/​doi.org/​10.1038/​s41534-019-0217-0

[4] Бенджамін Нахман, Давіде Провасолі, Вібе А де Йонг і Крістіан В. Бауер. «Квантовий алгоритм для моделювання фізики високих енергій». Physical Review Letters 126, 062001 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.062001

[5] Якоб Біамонте, Пітер Віттек, Нікола Панкотті, Патрік Ребентрост, Натан Вібе та Сет Ллойд. «Квантове машинне навчання». Nature 549, 195–202 (2017).
https: / / doi.org/ 10.1038 / nature23474

[6] Роман Орус, Семюель Мугель та Енріке Лізасо. «Квантові обчислення для фінансів: огляд і перспективи». Огляди з фізики 4, 100028 (2019).
https://​/​doi.org/​10.1016/​j.revip.2019.100028

[7] Джон Прескілл. «Квантові обчислення в епоху NISQ і за її межами». Квант 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[8] U Dorner, R Demkowicz-Dobrzanski, BJ Smith, JS Lundeen, W Wasilewski, K Banaszek, and IA Walmsley. “Оцінка оптимальної квантової фази”. Physical Review Letters 102, 040403 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.040403

[9] Джон Прескілл. «Відмовостійке квантове обчислення». Вступ до квантових обчислень та інформації. Сторінки 213–269. World Scientific (1998).

[10] Марко Серезо, Ендрю Аррасміт, Раян Беббуш, Саймон С. Бенджамін, Сугуру Ендо, Кейсуке Фуджі, Джаррод Р. Макклін, Косуке Мітараі, Сяо Юань, Лукаш Сінчіо та ін. “Варіаційні квантові алгоритми”. Nature Reviews PhysicsPages 1–20 (2021).
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[11] Пітер Джей Джей О'Меллі, Райан Баббуш, Ян Д. Ківлічан, Джонатан Ромеро, Джаррод Р. МакКлін, Рамі Барендс, Джуліан Келлі, Педрам Роушан, Ендрю Трантер, Нан Дін та ін. «Маштабована квантова симуляція молекулярних енергій». Фізичний огляд X 6, 031007 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.031007

[12] Сяо Юань, Сугуру Ендо, Ці Чжао, Ін Лі та Саймон С. Бенджамін. “Теорія варіаційного квантового моделювання”. Квант 3, 191 (2019).
https:/​/​doi.org/​10.22331/​q-2019-10-07-191

[13] Метью Оттен, Крістіан Л. Кортес і Стівен К. Грей. «Стійка до шуму квантова динаміка з використанням анзаців, що зберігають симетрію» (2019). arXiv:1910.06284.
arXiv: 1910.06284

[14] Абхінав Кандала, Антоніо Меццакапо, Крістан Темме, Майка Такіта, Маркус Брінк, Джеррі М. Чоу та Джей М. Гамбетта. «Апаратно ефективний варіаційний квантовий власний вирішувач для малих молекул і квантових магнітів». Природа 549, 242–246 (2017).
https: / / doi.org/ 10.1038 / nature23879

[15] Косуке Мітараї, Макото Негоро, Масахіро Кітаґава та Кейсуке Фуджі. «Навчання квантових схем». Physical Review A 98, 032309 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.032309

[16] Меттью Оттен, Імен Р. Гумірі, Бенджамін В. Пріст, Джордж Ф. Чаплайн і Майкл Д. Шнайдер. «Навчання квантової машини з використанням гаусових процесів із продуктивними квантовими ядрами» (2020). arXiv:2004.11280.
arXiv: 2004.11280

[17] Роберт М. Перріш, Едвард Г. Хохенштайн, Пітер Л. Макмехон і Тодд Дж. Мартінес. “Квантове обчислення електронних переходів з використанням варіаційного квантового розв’язувача власних сигналів”. Physical Review Letters 122, 230401 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.230401

[18] Кевін Дж. Сон, Цзяхао Яо, Меттью П. Харріган, Ніколас С. Рубін, Чжан Цзян, Лін Лін, Раян Беббуш і Джаррод Р. МакКлін. «Використання моделей для покращення оптимізаторів для варіаційних квантових алгоритмів». Квантова наука та технологія 5, 044008 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb6d9

[19] Джей Гамбетта, В. А. Брафф, А. Валлрафф, С. М. Гірвін і Р. Дж. Шолкопф. «Протоколи для оптимального зчитування кубітів за допомогою безперервного квантового вимірювання без руйнування». Physical Review A 76, 012325 (2007).
https: / / doi.org/ 10.1103 / PhysRevA.76.012325

[20] Сьюзан М. Кларк, Деніел Лобсер, Мелісса С. Ревелле, Крістофер Дж. Йейл, Девід Боссерт, Ешлін Д. Берч, Метью Н. Чоу, Крейг В. Гогл, Меган Айворі, Джессіка Пер та ін. «Розробка відкритого тестового стенда для квантових наукових обчислень». IEEE Transactions on Quantum Engineering 2, 1–32 (2021).
https://​/​doi.org/​10.1109/​TQE.2021.3096480

[21] Колін Д. Брузевич, Джон К'яверіні, Роберт МакКоннелл і Джеремі М. Сейдж. «Квантові обчислення з захопленими іонами: прогрес і проблеми». Applied Physics Reviews 6, 021314 (2019).
https: / / doi.org/ 10.1063 / 1.5088164

[22] Йонас М. Кюблер, Ендрю Аррасміт, Лукаш Сінчіо та Патрік Дж. Коулз. «Адаптивний оптимізатор для ощадливих варіаційних алгоритмів». Квант 4, 263 (2020).
https:/​/​doi.org/​10.22331/​q-2020-05-11-263

[23] Дідерік П. Кінгма та Джиммі Ба. «Адам: метод стохастичної оптимізації» (2014). arXiv:1412.6980.
arXiv: 1412.6980

[24] Тригве Хельгакер, Поул Йоргенсен і Єппе Ольсен. “Теорія електронної будови молекул”. Джон Вайлі та сини. (2014).
https: / / doi.org/ 10.1002 / 9781119019572

[25] Том Шаул, Іоанніс Антоноглу та Девід Сільвер. “Модульні тести для стохастичної оптимізації”. У Yoshua Bengio та Yann LeCun, редактори, 2-га Міжнародна конференція з уявлень про навчання, ICLR 2014, Банф, AB, Канада, 14-16 квітня 2014 р., Матеріали конференції. (2014). url: http://​/​arxiv.org/​abs/​1312.6055.
arXiv: 1312.6055

[26] Хілал Асі та Джон К. Дучі. «Важливість кращих моделей у стохастичній оптимізації». Праці Національної академії наук 116, 22924–22930 (2019).
https: / / doi.org/ 10.1073 / pnas.1908018116

[27] Біллі Джин, Катя Шайнберг і Мяолан Се. «Високоімовірні межі складності для рядкового пошуку на основі стохастичних оракулів» (2021). arXiv:2106.06454.
arXiv: 2106.06454

[28] Хосе Бланше, Коралія Картіс, Метт Менікеллі та Катя Шайнберг. “Аналіз швидкості конвергенції стохастичного методу довірчої області через супермартингали”. Журнал з оптимізації INFORMS 1, 92–119 (2019).
https://​/​doi.org/​10.1287/​ijoo.2019.0016

[29] Кортні Пакетт і Катя Шайнберг. «Стохастичний метод пошуку лінії з очікуваним аналізом складності». SIAM Journal on Optimization 30, 349–376 (2020).
https://​/​doi.org/​10.1137/​18M1216250

[30] Альберт С. Берахас, Ліюань Цао та Катя Шайнберг. “Аналіз глобальної швидкості конвергенції загального алгоритму пошуку лінії з шумом”. SIAM Journal on Optimization 31, 1489–1518 (2021).
https://​/​doi.org/​10.1137/​19M1291832

[31] Коралія Картіс, Ніколас І. М. Гулд і Ph L Toint. “Про складність найкрутішого спуску, методи Ньютона та регуляризовані методи Ньютона для неопуклих задач оптимізації без обмежень”. Siam journal on optimization 20, 2833–2852 (2010).
https: / / doi.org/ 10.1137 / 090774100

[32] Коралія Картіс, Ніколас І. М. Гулд і Філіп Л. Туант. “Про складність оракула алгоритмів першого порядку та без похідних для гладкої неопуклої мінімізації”. SIAM Journal on Optimization 22, 66–86 (2012).
https: / / doi.org/ 10.1137 / 100812276

[33] Яір Кармон, Джон К. Дучі, Олівер Гіндер та Аарон Сідфорд. “Нижні оцінки для знаходження стаціонарних точок І”. Математичне програмування 184, 71–120 (2020).
https: / / doi.org/ 10.1007 / s10107-019-01406-y

[34] Яір Кармон, Джон К. Дучі, Олівер Гіндер та Аарон Сідфорд. ««Опукло, доки не буде доведено провину»: Безрозмірне прискорення градієнтного спуску на неопуклих функціях». На міжнародній конференції з машинного навчання. Сторінки 654–663. PMLR (2017).
https: / / doi.org/ 10.5555 / 3305381.3305449

[35] Чі Джин, Праніт Нетрапаллі та Майкл I Джордан. «Прискорений градієнтний спуск усуває сідлові точки швидше, ніж градієнтний спуск». На конференції з теорії навчання. Сторінки 1042–1085. PMLR (2018). url: https://​/​proceedings.mlr.press/​v75/​jin18a.html.
https://​/​proceedings.mlr.press/​v75/​jin18a.html

[36] Саїд Гадімі та Гуанхуей Лан. “Стохастичні методи першого та нульового порядку для неопуклого стохастичного програмування”. SIAM Journal on Optimization 23, 2341–2368 (2013).
https: / / doi.org/ 10.1137 / 120880811

[37] Йоссі Арджевані, Яір Кармон, Джон С. Дучі, Ділан Дж. Фостер, Натан Сребро та Блейк Вудворт. «Нижні межі для неопуклої стохастичної оптимізації» (2019). arXiv:1912.02365.
arXiv: 1912.02365

[38] Цун Фанг, Кріс Цзюньчі Лі, Чжоучен Лін і Тонг Чжан. «Павук: майже оптимальна неопукла оптимізація за допомогою стохастичної інтегрованої диференціальної оцінки». У S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi та R. Garnett, редактори, Досягнення в нейронних системах обробки інформації. Том 31. Curran Associates, Inc. (2018). url: https://​/​proceedings.neurips.cc/​paper/​2018/​file/​1543843a4723ed2ab08e18053ae6dc5b-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​1543843a4723ed2ab08e18053ae6dc5b-Paper.pdf

[39] Широ Тамія і Хаята Ямасакі. «Байєсова оптимізація лінії стохастичного градієнта: зменшення кількості вимірювань при оптимізації параметризованих квантових схем» (2021). arXiv:2111.07952.
https:/​/​doi.org/​10.1038/​s41534-022-00592-6
arXiv: 2111.07952

[40] Паскуаль Джордан і Ежен Поль Вігнер. “über das paulische äquivalenzverbot”. У зібранні творів Юджина Поля Вігнера. Сторінки 109–129. Springer (1993).

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

[42] Джунхо Лі, Вільям Дж. Хаггінс, Мартін Хед-Гордон і К. Біргітта Вейлі. “Узагальнені унітарно пов’язані кластерні хвильові функції для квантових обчислень”. Журнал хімічної теорії та обчислення 15, 311–324 (2018).
https: / / doi.org/ 10.1021 / acs.jctc.8b01004

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

[44] Ілля Г Рябінкін, Цзу-Чін Єн, Скотт Н Генін, Артур Ф Ізмайлов. «Метод з’єднаного кубітного кластера: системний підхід до квантової хімії на квантовому комп’ютері». Журнал хімічної теорії та обчислень 14, 6317–6326 (2018).
https: / / doi.org/ 10.1021 / acs.jctc.8b00932

[45] Хо Лун Тан, В. О. Школьников, Джордж С. Беррон, Харпер Р. Грімслі, Ніколас Дж. Мейхолл, Едвін Барнс та Софія Економу. “qubit-ADAPT-VQE: адаптивний алгоритм для побудови апаратно-ефективного аналізу на квантовому процесорі”. PRX Quantum 2, 020310 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.020310

[46] Дмитро Федоров, Юрій Алексєєв, Стівен К. Грей і Метью Оттен. «Унітарний селективний кластерний метод». Квант 6, 703 (2022).
https:/​/​doi.org/​10.22331/​q-2022-05-02-703

[47] Пранав Гокхале, Олівія Ангіулі, Йоншан Дін, Кайвен Гуй, Тіг Томеш, Мартін Сучара, Маргарет Мартоносі та Фредерік Чонг. “$ o (n^3) $ вартість вимірювання для варіаційного квантового власного розв’язувача на молекулярних гамільтоніанах”. IEEE Transactions on Quantum Engineering 1, 1–24 (2020).
https://​/​doi.org/​10.1109/​TQE.2020.3035814

[48] Руобінг Чен, Метт Менікеллі та Катя Шайнберг. «Стохастична оптимізація з використанням методу довірчої області та випадкових моделей». Математичне програмування 169, 447–487 (2018).
https:/​/​doi.org/​10.1007/​s10107-017-1141-8

[49] Леон Ботту, Френк Е Кертіс і Хорхе Носедаль. «Методи оптимізації для широкомасштабного машинного навчання». Siam Review 60, 223–311 (2018).
https://​/​doi.org/​10.1137/​16M1080173

[50] Йоель Дрорі та Охад Шамір. “Складність знаходження стаціонарних точок зі стохастичним градієнтним спуском”. На міжнародній конференції з машинного навчання. Сторінки 2658–2667. PMLR (2020). url: https://​/​proceedings.mlr.press/​v119/​drori20a.html.
https://​/​proceedings.mlr.press/​v119/​drori20a.html

[51] Цун Фан, Чжоучен Лінь і Тун Чжан. “Точний аналіз неопуклої SGD, що виходить із сідлових точок”. На конференції з теорії навчання. Сторінки 1192–1234. PMLR (2019). url: https://​/​proceedings.mlr.press/​v99/​fang19a.html.
https://​/​proceedings.mlr.press/​v99/​fang19a.html

[52] С. Редді, Манзіл Захір, Девендра Сачан, Сатьєн Кале та Санджив Кумар. “Адаптивні методи неопуклої оптимізації”. У матеріалах 32-ї конференції з нейронних систем обробки інформації (NIPS 2018). (2018). url: https://​/​proceedings.neurips.cc/​paper/​2018/​file/​90365351ccc7437a1309dc64e4db32a3-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​90365351ccc7437a1309dc64e4db32a3-Paper.pdf

[53] Леон Боту та Олів'є Буске. «Компроміси широкомасштабного навчання». У J. Platt, D. Koller, Y. Singer і S. Roweis, редактори, Досягнення в нейронних системах обробки інформації. Том 20. Curran Associates, Inc. (2007). url: https://​/​proceedings.neurips.cc/​paper/​2007/​file/​0d3180d672e08b4c5312dcdafdf6ef36-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2007/​file/​0d3180d672e08b4c5312dcdafdf6ef36-Paper.pdf

[54] Пітер Дж. Каралекас, Ніколас А. Тезак, Ерік С. Петерсон, Колм А. Раян, Маркус П. да Сілва та Роберт С. Сміт. «Квантово-класична хмарна платформа, оптимізована для варіаційних гібридних алгоритмів». Квантова наука та технологія 5, 024003 (2020).
https://​/​doi.org/​10.1088/​2058-9565/​ab7559

[55] Х. Дж. Брігель, Томмазо Каларко, Дітер Якш, Хуан Ігнасіо Сірак і Пітер Золлер. «Квантові обчислення з нейтральними атомами». Журнал сучасної оптики 47, 415–451 (2000).
https: / / doi.org/ 10.1080 / 09500340008244052

[56] Сергій Бравий, Джей М. Гамбетта, Антоніо Меццакапо та Крістан Темме. «Звуження кубітів для моделювання ферміонних гамільтоніанів» (2017). arXiv:1701.08213.
arXiv: 1701.08213

[57] MD SAJID ANIS, Héctor Abraham, AduOffei, Rochisha Agarwal, Gabriele Agliardi, Merav Aharoni, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, Thomas Alexander, Matthew Amy, Sashwat Anagolum, Eli Arbel, Abraham Asfaw, Anish Athalye, Artur Avkhadiev та ін. «Qiskit: фреймворк з відкритим кодом для квантових обчислень» (2021).

[58] Чжу Чжу, Річард Берд, Пейхуан Лу та Хорхе Носедал. «Алгоритм 778: L-BFGS-B: підпрограми Fortran для великомасштабної обмеженої оптимізації». ACM Transactions on Mathematical Software (TOMS) 23, 550–560 (1997).
https: / / doi.org/ 10.1145 / 279232.279236

[59] Рагу Боллапрагада, Річард Берд і Хорхе Носедал. «Стратегії адаптивної вибірки для стохастичної оптимізації». SIAM Journal on Optimization 28, 3312–3343 (2018).
https://​/​doi.org/​10.1137/​17M1154679

[60] Рагу Боллапрагада, Хорхе Ноцедал, Дееваца Мудігере, Хао-Джун Ши та Пінг Так Пітер Танг. «Прогресивний метод пакетування L-BFGS для машинного навчання». На міжнародній конференції з машинного навчання. Сторінки 620–629. PMLR (2018). url: https://​/​proceedings.mlr.press/​v80/​bollapragada18a.html.
https://​/​proceedings.mlr.press/​v80/​bollapragada18a.html

[61] Рагу Пасупаті, Пітер Глінн, Сумядіп Ґош і Фатеме С. Хашемі. “Про частоту дискретизації в рекурсіях на основі моделювання”. SIAM Journal on Optimization 28, 45–73 (2018).
https: / / doi.org/ 10.1137 / 140951679

[62] Ендрю Аррасміт, Лукаш Сінчіо, Роландо Д Сомма та Патрік Джей Коулз. «Операторська вибірка для економної оптимізації у варіаційних алгоритмах» (2020). arXiv:2004.06252.
arXiv: 2004.06252

[63] Ян'ян Сюй і Вотао Інь. «Блокова стохастична градієнтна ітерація для опуклої та неопуклої оптимізації». SIAM Journal on Optimization 25, 1686–1716 (2015).
https: / / doi.org/ 10.1137 / 140983938

Цитується

[1] Метт Менікеллі, Стефан М. Уайлд і Мяолан Се, «Стохастичний метод квазіньютона за відсутності загальних випадкових чисел», arXiv: 2302.09128, (2023).

[2] Косуке Іто, «Адаптивний розподіл кадрів з урахуванням затримки для ефективних варіаційних квантових алгоритмів під час виконання», arXiv: 2302.04422, (2023).

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

Не вдалося отримати Перехресне посилання, наведене за даними під час останньої спроби 2023-03-16 18:30:43: Не вдалося отримати цитовані дані для 10.22331/q-2023-03-16-949 з Crossref. Це нормально, якщо DOI був зареєстрований нещодавно.

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

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