Google DeepMind
CQIF, DAMTP, Кембриджский университет, Великобритания
Находите эту статью интересной или хотите обсудить? Scite или оставить комментарий на SciRate.
Абстрактные
Подготовка квантового состояния является важным компонентом других квантовых алгоритмов более высокого уровня, таких как гамильтоновое моделирование, или для загрузки распределений в квантовое устройство для использования, например, в контексте задач оптимизации, таких как машинное обучение. Начиная с общего метода «черного ящика», разработанного Гровером в 2000 году, который использует усиление амплитуды для загрузки коэффициентов, рассчитанных оракулом, был получен длинный ряд результатов и улучшений с различными дополнительными условиями для загружаемых амплитуд, кульминацией которых стало Сандерса и др., в котором почти полностью избегают арифметических операций на этапе подготовки.
В этой работе мы строим оптимизированную схему загрузки состояния черного ящика, с помощью которой различные важные наборы коэффициентов могут быть загружены значительно быстрее, чем за $O(sqrt N)$ раундов усиления амплитуды, всего до $O(1)$ многих. Мы достигаем этого с помощью двух вариантов нашего алгоритма. В первом используется модификация оракула Сандерса и др., которая требует меньше вспомогательных функций ($log_2 g$ против $g+2$ в битовой точности $g$) и меньше не-Клиффордских операций на раунд усиления амплитуды в пределах контекст нашего алгоритма. Второй использует тот же оракул, но с немного увеличенной стоимостью с точки зрения вспомогательных средств ($g+log_2g$) и операций, не связанных с Клиффордом, за раунд усиления. Поскольку количество раундов усиления амплитуды входит в качестве мультипликативного фактора, наша схема загрузки состояния черного ящика дает ускорение вплоть до экспоненциального по сравнению с предыдущими методами. Это ускорение выходит за рамки случая черного ящика.
Популярное резюме
В этой работе мы улучшаем подпрограмму хоста, значительно уменьшая количество необходимых запросов к черному ящику, обеспечивая ускорение вплоть до экспоненциального — естественно, в зависимости от загружаемых данных, но результаты справедливы для широкого диапазона реалистичных задач. интересующие наборы данных или распределения. Кроме того, мы разрабатываем специальную подпрограмму черного ящика, адаптированную для особенно хорошей работы с нашей схемой загрузки данных хоста, которая еще больше снижает требуемые накладные расходы на кубиты и вентили.
► Данные BibTeX
► Рекомендации
[1] Лов К. Гровер «Синтез квантовых суперпозиций с помощью квантовых вычислений» Physical Review Letters 85, 1334-1337 (2000).
https: / / doi.org/ 10.1103 / PhysRevLett.85.1334
[2] Юваль Р. Сандерс, Гуанг Хао Лоу, Артур Шерер и Доминик В. Берри, «Подготовка квантового состояния черного ящика без арифметики» Physical Review Letters 122, 020502 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.020502
[3] Арам В. Харроу, Авинатан Хассидим и Сет Ллойд, «Квантовый алгоритм для линейных систем уравнений», Physical Review Letters 103, 150502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
Arxiv: 0811.3171
[4] Джулия Кемпе «Квантовые случайные блуждания - вводный обзор» Contemporary Physics 44, 307–327 (2003).
https: / / doi.org/ 10.1080 / 00107151031000110776
Arxiv: 0303081
[5] Миклош Сантаха «Алгоритмы поиска на основе квантового блуждания» Теория и приложения моделей вычислений 31–46 (2008).
https://doi.org/10.1007/978-3-540-79228-4_3
http://link.springer.com/10.1007/978-3-540-79228-4%7B%5C_%7D3
[6] Доминик В. Берри и Эндрю М. Чайлдс «Моделирование Гамильтона методом черного ящика и унитарная реализация» (2009).
https: / / doi.org/ 10.26421 / QIC12.1-2
Arxiv: 0910.4157
[7] Фернандо Г.С.Л. Брандао, Амир Калев, Тонъян Ли, Седрик Йен-Ю Лин, Криста М. Своре и Сяоди Ву, «Квантовые решатели SDP: большие ускорения, оптимальность и приложения для квантового обучения», ICALP 2019 (2017).
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.27
Arxiv: 1710.02581
[8] Сергей Бравый, Александр Клиш, Роберт Кениг и Юджин Тан, «Препятствия для подготовки состояний и вариационной оптимизации из-за защиты симметрии» (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
Arxiv: 1910.08980
[9] Доминик В. Берри, Эндрю М. Чайлдс и Робин Котари, «Гамильтоновское моделирование с почти оптимальной зависимостью от всех параметров» (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.54
Arxiv: 1501.01715
[10] Н. Коди Джонс, Джеймс Д. Уитфилд, Питер Л. МакМахон, Ман-Хонг Юнг, Родни Ван Метер, Алан Аспуру-Гузик и Йошихиса Ямамото, «Ускоренное моделирование квантовой химии на отказоустойчивых квантовых компьютерах», Новый журнал физики, 14, 115023 (2012).
https://doi.org/10.1088/1367-2630/14/11/115023
Arxiv: 1204.0567
[11] Андрей Н. Соклаков и Рюдигер Шак «Эффективная подготовка состояния для регистра квантовых битов» Physical Review A 73, 012307 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.012307
[12] Мартин Плешанд Часлав Брукнер «Подготовка квантового состояния с разложением универсальных ворот» Physical Review A 83, 032302 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.032302
Arxiv: 1003.5760
[13] Микко Моттонен, Юха Дж. Вартиайнен, Вилле Бергхольм и Мартти М. Саломаа, «Преобразование квантовых состояний с использованием равномерно управляемых вращений» Quant. Инф. Комп. 5, 467 (2004).
https:///doi.org/10.48550/arXiv.quant-ph/0407010
Arxiv: 0407010
[14] Исраэль Ф. Араужо, Даниэль К. Парк, Франческо Петруччионе и Аденилтон Дж. да Силва, «Алгоритм «разделяй и властвуй» для подготовки квантового состояния» (2020).
https://doi.org/10.1038/s41598-021-85474-1
Arxiv: 2008.01511
[15] Лов Гровер и Терри Рудольф «Создание суперпозиций, соответствующих эффективно интегрируемым распределениям вероятностей» (2002).
https:///doi.org/10.48550/arXiv.quant-ph/0208112
Arxiv: 0208112
[16] Эндрю М. Чайлдс «О связи между квантовым блужданием в непрерывном и дискретном времени», Сообщения по математической физике 294, 581–603 (2009).
https://doi.org/10.1007/s00220-009-0930-1
[17] Криста Зуфаль, Орельен Лукки и Стефан Вернер, «Квантовые генеративно-состязательные сети для обучения и загрузки случайных распределений» npj Quantum Information (2019).
https://doi.org/10.1038/s41534-019-0223-2
Arxiv: 1904.00043
[18] Майкл А. Нильсен и Исаак Л. Чуанг «Квантовые вычисления и квантовая информация» Cambridge University Press (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667
http://books.google.com/books?id=-s4DEy7o-a0C%7B%5C&%7Dpgis=1%20http://ebooks.cambridge.org/ref/id/CBO9780511976667
[19] Теодор Дж. Йодер, Гуанг Хао Лоу и Исаак Л. Чуанг, «Квантовый поиск с фиксированной точкой с оптимальным количеством запросов», Physical Review Letters 113, 210501 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.210501
[20] Стивен А. Куккаро, Томас Г. Дрейпер, Сэмюэл А. Кутин и Дэвид Петри Моултон, «Новая квантовая схема сложения с переносом пульсаций» (2004).
https:///doi.org/10.48550/arXiv.quant-ph/0410184
Arxiv: 0410184
[21] Крейг Гидни «Уменьшение вдвое стоимости квантового сложения» Quantum 2, 74 (2018).
https://doi.org/10.22331/q-2018-06-18-74
Arxiv: 1709.06648
[22] Юн Хэ, Мин-Син Луо, Э. Чжан, Хонг-Ке Ван и Сяо-Фэн Ван, «Разложение n-кубитных вентилей Тоффоли со сложностью линейной схемы», Международный журнал теоретической физики 56, 2350–2361 (2017).
https://doi.org/10.1007/s10773-017-3389-4
[23] Джон А. Смолин и Дэвид П. Ди Винченцо «Пяти двухбитных квантовых вентилей достаточно для реализации квантового вентиля Фредкина» Physical Review A 53, 2855–2856 (1996).
https: / / doi.org/ 10.1103 / PhysRevA.53.2855
[24] Лаборатория квантового ИИ Google, Фрэнк Аруте, Кунал Арья, Райан Бэббуш, Дэйв Бэкон, Джозеф К. Бардин, Рами Барендс, Рупак Бисвас, Серджио Бойшо, Фернандо Г.С.Л. Брандао, Дэвид А. Бьюэлл, Брайан Беркетт, Ю Чен, Зиджун Чен, Бен Кьяро, Роберто Коллинз, Уильям Кортни, Эндрю Дансворт, Эдвард Фархи, Брукс Фоксен, Остин Фаулер, Крейг Гидни, Марисса Джустина, Роб Графф, Кит Герин, Стив Хабеггер, Мэтью П. Харриган, Майкл Дж. Хартманн, Алан Хо, Маркус Хоффманн , Трент Хуанг, Трэвис С. Хамбл, Сергей В. Исаков, Эван Джеффри, Чжан Цзян, Двир Кафри, Константин Кечеджи, Джулиан Келли, Пол В. Климов, Сергей Кныш, Александр Коротков, Федор Кострица, Дэвид Ландхус, Майк Линдмарк, Эрик Лусеро, Дмитрий Лях, Сальваторе Мандра, Джаррод Р. МакКлин, Мэтью МакЮэн, Энтони Мегрант, Сяо Ми, Кристель Михильсен, Масуд Мохсени, Джош Мутус, Офер Нааман, Мэтью Нили, Чарльз Нил, Мерфи Юежен Ню, Эрик Остби, Андре Петухов, Джон С. Платт, Крис Кинтана, Элеонора Г. Риффель, Педрам Рушан, НиколасК. Рубин, Дэниел Санк, Кевин Дж. Сатцингер, Вадим Смелянский, Кевин Дж. Санг, Мэтью Д. Тревитик, Амит Вайнсенчер, Бенджамин Виллалонга, Теодор Уайт, З. Джейми Яо, Пинг Йе, Адам Зальцман, Хартмут Невен, Джон М. , Мартинис, Quantum AI Lab Google, Фрэнк Аруте, Кунал Арья, Райан Баббуш, Дэйв Бэкон, Джозеф С. Бардин, Рами Барендс, Рупак Бисвас, Серджио Бойшо, Фернандо Г.С.Л. Брандао, Дэвид А. Бьюэлл, Брайан Беркетт, Ю Чен, Зиджун Чен, Бен Чиаро, Роберто Коллинз, Уильям Кортни, Эндрю Дансворт, Эдвард Фархи, Брукс Фоксен, Остин Фаулер, Крэйг Гидни, Марисса Джустина, Роб Графф, Кит Герин, Стив Хабеггер, Мэтью П. Харриган, Майкл Дж. Хартманн, Алан Хо , Маркус Хоффманн, Трент Хуанг, Трэвис С. Хамбл, Сергей В. Исаков, Эван Джеффри, Чжан Цзян, Двир Кафри, Константин Кечеджи, Джулиан Келли, Пол В. Климов, Сергей Кныш, Александр Коротков, Федор Кострица, Дэвид Ландхуис, Майк Линдмарк, Эрик Лусеро, Дмитрий Лях, Сальваторе Мандра, Джаррод Р. МакКлин, Мэттью МакЮэн, Энтони Мегран т, Сяо Ми, Кристель Михильсен, Масуд Мохсени, Джош Мутус, Офер Нааман, Мэтью Нили, Чарльз Нил, Мерфи Юежен Ню, Эрик Остби, Андре Петухов, Джон С. Платт, Крис Кинтана, Элеонора Г. Риффель, Педрам Рушан, Николас К. Рубин, Дэниел Санк, Кевин Дж. Сатцингер, Вадим Смелянский, Кевин Дж. Сунг, Мэтью Д. Тревитик, Амит Вайнсенчер, Бенджамин Виллалонга, Теодор Уайт, З. Джейми Яо, Пинг Йе, Адам Зальцман, Хартмут Невен и Джон М. Мартинис, «Квантовое превосходство с использованием программируемого сверхпроводящего процессора» Nature 574, 505–510 (2019).
https://doi.org/10.1038/s41586-019-1666-5
http:///www.nature.com/articles/s41586-019-1666-5
[25] Эшли Монтанаро «Квантовый поиск с советами» 1–14 (2009).
Arxiv: 0908.3066
Цитируется
[1] Кохей Накадзи, Шумпей Уно, Йохичи Судзуки, Руди Рэймонд, Тамия Онодера, Томоки Танака, Хироюки Тэдзука, Наоки Мицуда и Наоки Ямамото, «Приблизительное амплитудное кодирование в неглубоких параметризованных квантовых схемах и его применение к индикаторам финансового рынка», Physical Review Research 4, 2 (023136).
[2] Вэйвен Цзян, Цзиньцзюнь Сюн и Ию Ши, «Структура совместной разработки нейронных сетей и квантовых схем для достижения квантового преимущества», Nature Communications 12, 579 (2021 год).
[3] Владимир Варгас-Кальдерон, Фабио А. Гонсалес и Герберт Винк-Посада, «Классификация без оптимизации и оценка плотности с помощью квантовых схем», Arxiv: 2203.14452.
[4] Габриэль Марин-Санчес, Хавьер Гонсалес-Конде и Микель Санс, «Квантовые алгоритмы для приближенной загрузки функций», Arxiv: 2111.07933.
[5] Шэнбинь Ван, Чжимин Ван, Гуолун Цуй, Лисинь Фань, Шаншан Ши, Жуйминь Шан, Вендун Ли, Чжицян Вэй и Юнцзянь Гу, «Квантовая амплитудная арифметика», Arxiv: 2012.11056.
[6] Б. Дэвид Кладер, Александр М. Далзелл, Никитас Стаматопулос, Грант Солтон, Марио Берта и Уильям Дж. Зенг, «Квантовые ресурсы, необходимые для блочного кодирования матрицы классических данных», Arxiv: 2206.03505.
[7] М. Ю. Кириллин, А. В. Приезжев, Дж. Хаст, Ристо Мюллюля, «ЛАЗЕРНЫЕ ПРИМЕНЕНИЯ И ДРУГИЕ ТЕМЫ В КВАНТОВОЙ ЭЛЕКТРОНИКЕ: Моделирование методом Монте-Карло оптического просветления бумаги в оптической когерентной томографии», Квантовая электроника 36 2, 174 (2006).
[8] Шэнбинь Ван, Чжимин Ван, Гуолун Цуй, Шаншан Ши, Жуйминь Шан, Лисинь Фан, Вендун Ли, Чжицян Вей и Юнцзянь Гу, «Быстрая подготовка квантового состояния черного ящика на основе линейной комбинации унитарных величин», ��������� ��������� ���������� 20 8, 270 (2021).
[9] Рауль Хиз, Патрисия Бикерт и Астрид Элиза Нидерле, «Представление бинарных классификационных деревьев с бинарными характеристиками квантовыми схемами», Arxiv: 2108.13207.
[10] Вэйвен Цзян, Цзиньцзюнь Сюн и Ию Ши, «Когда машинное обучение встречается с квантовыми компьютерами: пример», Arxiv: 2012.10360.
[11] Тиаго М.Л. де Верас, Леон Д. да Силва и Аденилтон Дж. да Силва, «Подготовка двойного разреженного квантового состояния», ��������� ��������� ���������� 21 6, 204 (2022).
[12] Д.А. Зимняков, Л.В. Кузнецова, О.В. Ушакова, Ристо Мюллюля, “Специальный выпуск, посвященный многократному рассеянию излучения в случайных средах: об оценке эффективных оптических параметров плотноупакованных фибриллярных сред”, Квантовая электроника 37 1, 9 (2007).
[13] Шэнбинь Ван, Чжимин Ван, Рунхонг Хе, Гуолонг Цуй, Шаншан Ши, Жуйминь Шан, Цзяюнь Ли, Янан Ли, Вендун Ли, Чжицян Вэй и Юнцзянь Гу, «Подготовка квантового состояния черного ящика с обратными коэффициентами», Arxiv: 2112.05937.
Приведенные цитаты из САО / НАСА ADS (последнее обновление успешно 2022-08-04 12:34:11). Список может быть неполным, поскольку не все издатели предоставляют подходящие и полные данные о цитировании.
Не удалось получить Перекрестная ссылка на данные во время последней попытки 2022-08-04 12:34:09: Не удалось получить цитируемые данные для 10.22331 / q-2022-08-04-773 от Crossref. Это нормально, если DOI был зарегистрирован недавно.
Эта статья опубликована в Quantum под Creative Commons Attribution 4.0 International (CC BY 4.0) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.
