Google DeepMind
CQIF, DAMTP, Кембриджський університет, Великобританія
Вам цей документ цікавий чи ви хочете обговорити? Скайте або залиште коментар на 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] Ювал Р. Сандерс, Гуан Хао Лоу, Артур Шерер і Домінік В. Беррі, «Підготовка квантового стану чорної скриньки без арифметики», листи фізичного огляду 122, 020502 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.020502
[3] Арам В. Харроу, Авінатан Хасідім і Сет Ллойд, «Квантовий алгоритм для лінійних систем рівнянь» Фізичні оглядові листи 103, 150502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
arXiv: 0811.3171
[4] Джулія Кемпе «Квантові випадкові блукання – вступний огляд» Сучасна фізика 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] N Cody Jones, James D. Whitfield, Peter L. McMahon, Man-Hong Yung, Rodney Van Meter, Alán Aspuru-Guzik, and Yoshihisa Yamamoto, “Faster quantum chemistry simulation on fault-tolerant quantum computers” New Journal of Physics 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] Мартін Плешанд Часлав Брукнер «Підготовка квантового стану з універсальними розкладами» Фізичний огляд A 83, 032302 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.032302
arXiv: 1003.5760
[13] Мікко Моттонен, Юха Дж. Вартіайнен, Вілле Берггольм і Мартті М. Саломаа, «Перетворення квантових станів за допомогою рівномірно керованих обертань» Квант. Інф. комп. 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] Christa Zoufal, Aurélien Lucchi та Stefan Woerner, «Квантові генеративні змагальні мережі для навчання та завантаження випадкових розподілів» 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] Теодор Дж. Йодер, Гуан Хао Лоу та Ісаак Л. Чуанг, «Квантовий пошук у фіксованій точці з оптимальною кількістю запитів», листи фізичного огляду 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] Крейг Гідні «Зниження вартості квантового додавання вдвічі» Квант 2, 74 (2018).
https://doi.org/10.22331/q-2018-06-18-74
arXiv: 1709.06648
[22] Yong He, Ming-Xing Luo, E. Zhang, Hong-Ke Wang і Xiao-Feng Wang, “Decompositions of n-qubit Toffoli Gates with Linear Circuit Complexity” International Journal of Theoretical Physics 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] Quantum AI Lab 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] Kouhei Nakaji, Shumpei Uno, Yohichi Suzuki, Rudy Raymond, Tamiya Onodera, Tomoki Tanaka, Hiroyuki Tezuka, Naoki Mitsuda та Naoki Yamamoto, «Кодування наближеної амплітуди в дрібних параметризованих квантових схемах і його застосування до індикаторів фінансового ринку», Physical Review Research 4 2, 023136 (2022).
[2] Weiwen Jiang, Jinjun Xiong та Yiyu Shi, «Спільне проектування нейронних мереж і квантових схем для квантової переваги», Nature Communications 12, 579 (2021).
[3] Володимир Варгас-Кальдерон, Фабіо А. Гонсалес і Герберт Вінк-Посада, «Класифікація без оптимізації та оцінка щільності за допомогою квантових схем», arXiv: 2203.14452.
[4] Габріель Марін-Санчес, Хав’єр Гонсалес-Конде та Мікель Санс, «Квантові алгоритми для наближеного завантаження функцій», arXiv: 2111.07933.
[5] Шенгбінь Ван, Чжімінь Ван, Голонг Цуй, Лісінь Фан, Шаншанг Ши, Руймінь Шан, Вендон Лі, Чжицян Вей та Юнцзянь Гу, «Квантова амплітудна арифметика», arXiv: 2012.11056.
[6] B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, and William J. Zeng, “Quantum Resources Required to Block-Encode a Matrix of Classical Data”, arXiv: 2206.03505.
[7] М. Ю. Кириллін, А. В. Пріезжев, Дж. Хаст і Рісто Мюллюля, «ЗАСТОСУВАННЯ ЛАЗЕРУ ТА ІНШІ ТЕМИ В КВАНТОВІЙ ЕЛЕКТРОНІЦІ: моделювання оптичного очищення паперу методом Монте-Карло в оптичній когерентній томографії», Квантова електроніка 36 2, 174 (2006).
[8] Шенгбінь Ван, Чжімін Ван, Гуолонг Цуй, Шаншанг Ши, Руймінь Шан, Лісінь Фан, Вендонг Лі, Чжицян Вей та Юнцзянь Гу, «Швидка підготовка квантового стану чорної скриньки на основі лінійної комбінації унітарних елементів», Квантова обробка інформації 20 8, 270 (2021).
[9] Рауль Хіз, Патрісія Бікерт та Астрід Еліза Нідерле, «Представлення бінарних класифікаційних дерев з бінарними ознаками квантовими ланцюгами», arXiv: 2108.13207.
[10] Weiwen Jiang, Jinjun Xiong та Yiyu Shi, «When Machine Learning Meets Quantum Computers: A Case Study», arXiv: 2012.10360.
[11] Тіаго М. Л. де Верас, Леон Д. да Сілва та Аденілтон Дж. да Сілва, “Подвійний розріджений квантовий препарат стану”, Квантова обробка інформації 21 6, 204 (2022).
[12] Д. А. Зимняков, Л. В. Кузнєцова, О. В. Ушакова, Рісто Мюллюля, “Спецвипуск, присвячений багаторазовому розсіянню випромінювання у випадкових середовищах: Про оцінку ефективних оптичних параметрів щільно упакованих фібрилярних середовищ”, Квантова електроніка 37 1, 9 (2007).
[13] Шенгбінь Ван, Чжімінь Ван, Рунхун Хе, Гуолонг Цуй, Шаншанг Ши, Жуймінь Шан, Цзяюнь Лі, Янань Лі, Вендун Лі, Чжицян Вей та Юнцзянь Гу, «Підготовка квантового стану чорного ящика з інверсними коефіцієнтами», arXiv: 2112.05937.
Вищезазначені цитати від SAO / NASA 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 на 4.0) ліцензія. Авторське право залишається за оригінальними власниками авторських прав, такими як автори або їх установи.
