1Факультет фізики, ETH Zürich, Швейцарія
2Інститут теоретичних досліджень, ETH Zürich, Швейцарія
Вам цей документ цікавий чи ви хочете обговорити? Скайте або залиште коментар на SciRate.
абстрактний
Доказ кількісності — це тип протоколу виклик-відповідь, у якому класичний верифікатор може ефективно засвідчити $textit{квантову перевагу}$ ненадійного првера. Тобто квантовий прувер може правильно відповісти на виклики верифікатора та бути прийнятим, у той час як будь-який класичний прувер із поліноміальним часом буде відхилено з високою ймовірністю на основі вірогідних обчислювальних припущень. Щоб відповісти на виклики верифікатора, існуючі докази квантовості зазвичай вимагають від квантового првера виконання комбінації квантових схем поліноміального розміру та вимірювань.
У цьому документі ми наводимо дві конструкції доказів квантової точності, у яких досліднику потрібно лише виконати $textit{квантові схеми постійної глибини}$ (і вимірювання) разом із класичним логарифмічним обчисленням. Наша перша конструкція — це загальний компілятор, який дозволяє нам перекладати всі існуючі докази квантової точності у версії з постійною квантовою глибиною. Наша друга конструкція базується на проблемі $textit{навчання з округленням}$, і дає схеми з меншою глибиною та потребує менше кубітів, ніж загальна конструкція. Крім того, друга конструкція також має певну стійкість до шуму.
► Дані BibTeX
► Список літератури
[1] Скотт Ааронсон і Алекс Архіпов. Обчислювальна складність лінійної оптики. У матеріалах сорок третього щорічного симпозіуму ACM з теорії обчислень, сторінки 333–342, 2011.
https: / / doi.org/ 10.1145 / 1993636.1993682
[2] Френк Аруте, Кунал Ар’я, Раян Беббуш, Дейв Бекон, Джозеф С. Бардін, Рамі Барендс, Рупак Бісвас, Серхіо Бойшо, Фернандо Дж. С. Л. Брандао, Девід А. Буелл та ін. Квантова перевага за допомогою програмованого надпровідного процесора. Nature, 574(7779):505–510, 2019.
https://doi.org/10.1038/s41586-019-1666-5
[3] MD SAJID ANIS, Abby-Mitchell, Héctor Abraham, AduOffei та ін. Qiskit: фреймворк з відкритим кодом для квантових обчислень, 2021 р.
[4] Санджив Арора та Боаз Барак. Обчислювальна складність: сучасний підхід. Cambridge University Press, 2009.
[5] Скотт Ааронсон і Ліцзі Чен. Теоретико-складні основи експериментів квантової переваги. У матеріалах 32-ї конференції з обчислювальної складності, CCC '17, сторінки 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:///doi.org/10.48550/arXiv.1612.05903
[6] Скотт Ааронсон і Сем Ганн. Про класичну стійкість підробки лінійного крос-ентропійного бенчмаркінгу. Теорія обчислень, 16(11):1–8, 2020.
https:///doi.org/10.4086/toc.2020.v016a011
[7] Б. Епплбаум, Ю. Ішаї та Е. Кушилевіц. Криптографія в ${NC}^0$. На 45-му щорічному симпозіумі IEEE з основ інформатики, сторінки 166–175, 2004 р.
https:///doi.org/10.1109/FOCS.2004.20
[8] Джоель Алвен, Стефан Кренн, Кшиштоф П'єтжак і Даніель Вікс. Навчання з округленням, знову. In Advances in Cryptology – CRYPTO 2013, сторінки 57–74, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] Девід А. Баррінгтон. Програми розгалуження розміру полінома обмеженої ширини розпізнають саме ці мови в ${NC}^1$. Journal of Computer and System Sciences, 38(1):150–164, 1989.
https://doi.org/10.1016/0022-0000(89)90037-8
[10] Звіка Бракерскі, Пол Крістіано, Урміла Махадев, Умеш Вазірані та Томас Відік. Криптографічний тест кількісності та сертифікованої випадковості з одного квантового пристрою. У 2018 році IEEE 59-й щорічний симпозіум з основ комп’ютерних наук (FOCS), сторінки 320–331. IEEE, 2018.
https: / / doi.org/ 10.1145 / 3441309
[11] Колін Д. Брузевич, Джон К'яверіні, Роберт МакКоннелл і Джеремі М. Сейдж. Квантові обчислення з захопленими іонами: прогрес і проблеми. Applied Physics Reviews, 2019.
https: / / doi.org/ 10.1063 / 1.5088164
[12] Адам Буланд, Білл Фефферман, Чінмай Ніркхе та Умеш Вазірані. Про складність і верифікацію квантової випадкової схемної дискретизації. Nature Physics, 15(2):159–163, лютий 2019 р.
https://doi.org/10.1038/s41567-018-0318-2
[13] Серхіо Бойхо, Сергій В. Ісаков, Вадим Н. Смілянський, Раян Беббуш, Нан Дін, Чжан Цзян, Майкл Дж. Бремнер, Джон М. Мартініс і Хартмут Невен. Характеристика квантової переваги в короткочасних пристроях. Nature Physics, 14(6):595–600, 2018.
https: / / doi.org/ 10.1038 / s41567-018-0124-x
[14] Звіка Бракерскі, Венката Коппула, Умеш Вазірані та Томас Відік. Простіші докази квантовості. На 15-й конференції з теорії квантових обчислень, комунікації та криптографії (TQC 2020), том 158 Leibniz International Proceedings in Informatics (LIPIcs), сторінки 8:1–8:14, Дагштуль, Німеччина, 2020. Schloss Dagstuhl–Leibniz- Центр інформатики.
https:///doi.org/10.4230/LIPIcs.TQC.2020.8
[15] Абхішек Банерджі, Кріс Пейкерт і Алон Розен. Псевдовипадкові функції та решітки. У Advances in Cryptology – EUROCRYPT 2012, сторінки 719–737. Springer Berlin Heidelberg, 2012.
https://doi.org/10.1007/978-3-642-29011-4_42
[16] Джон Ф. Клаузер, Майкл А. Хорн, Ебнер Шімоні та Річард А. Холт. Пропонований експеримент для перевірки локальних теорій прихованих змінних. Physical Review Letters, 23(15):880, 1969.
https: / / doi.org/ 10.1103 / PhysRevLett.23.880
[17] Меттью Кудрон, Джалекс Старк і Томас Відік. Обмін локальністю на час: сертифікована випадковість із низьких ланцюгів. Повідомлення в математичній фізиці, 382(1):49–86, 2021.
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[18] Річард Клів і Джон Вотрус. Швидкі паралельні схеми для квантового перетворення Фур'є. У матеріалах 41-го щорічного симпозіуму з основ інформатики, сторінки 526–536. IEEE, 2000.
https:///doi.org/10.1109/SFCS.2000.892140
[19] П'єр Дюсар. Autour de la fonction qui compte le nombre de nombres premiers. Докторська дисертація, Університет Ліможа, 1998.
https:///www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] Остін Г. Фаулер, Маттео Маріантоні, Джон М. Мартініс та Ендрю Н. Клеланд. Поверхневі коди: на шляху до практичних великомасштабних квантових обчислень. Physical Review A, 86(3):032324, 2012.
https: / / doi.org/ 10.1103 / PhysRevA.86.032324
[21] Франсуа Ле Галль. Приватне листування, 2022.
[22] Крейг Гідні та Мартін Екеро. Як розкласти 2048 біт цілих чисел RSA за 8 годин, використовуючи 20 мільйонів зашумлених кубітів. Квант, 5:433, 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] Александру Георгіу та Метті Дж. Хобан. Оцінити ентропію виходів неглибоких схем важко. Препринт arXiv arXiv:2002.12814, 2020.
https:///doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] Шуічі Хірахара та Франсуа Ле Гал. Перевірка квантності з квантовими схемами малої глибини. У 46-му Міжнародному симпозіумі з математичних основ комп’ютерної науки (MFCS 2021), том 202 Leibniz International Proceedings in Informatics (LIPIcs), сторінки 59:1–59:15, Дагштуль, Німеччина, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
https:///doi.org/10.4230/LIPIcs.MFCS.2021.59
[25] Арам В. Харроу та Ешлі Монтанаро. Квантова обчислювальна перевага. Природа, 549(7671):203–209, 2017.
https: / / doi.org/ 10.1038 / nature23458
[26] Пітер Хоєр і Роберт Шпалек. Quantum Fan-out потужний. Теорія обчислень, 1(5):81–103, 2005.
https:///doi.org/10.4086/toc.2005.v001a005
[27] Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi та Jianxin Chen. Класичне моделювання схем квантової переваги. Препринт arXiv arXiv:2005.06787, 2020.
https:///doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] Грегорі Д Каханамоку-Майєр. Підробка квантових даних: класична перемога над квантовим тестом на основі IQP. Препринт arXiv arXiv:1912.05547, 2019.
https:///doi.org/10.48550/arXiv.1912.05547
arXiv: 1912.05547
[29] Грегорі Д. Каханамоку-Майєр, Сунвон Чой, Умеш В. Вазірані та Норман Й. Яо. Класично перевірена квантова перевага за допомогою обчислювального тесту Белла. Фізика природи, 18(8):918–924, 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] Вадим Любашевський, Кріс Пейкерт та Одед Регев. Про ідеальні ґратки та навчання з помилками над кільцями. У щорічній міжнародній конференції з теорії та застосування криптографічних методів, сторінки 1–23. Springer, 2010.
https: / / doi.org/ 10.1145 / 2535925
[31] Урміла Махадев. Класична перевірка квантових обчислень. У 2018 році IEEE 59-й щорічний симпозіум з основ комп’ютерних наук (FOCS), сторінки 259–267. IEEE, 2018.
https:///doi.org/10.1109/FOCS.2018.00033
[32] Майкл Нільсен і Ісаак Чуанг. Квантові обчислення та квантова інформація, 2002.
[33] А. С. Попова і А. Н. Рубцов. Злом квантового порогу переваги для вибірки гауссового бозона. На конференції та виставці Quantum 2.0, сторінка QW2A.15. Видавнича група «Оптика», 2022.
https:///doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] Джон Прескілл. Квантові обчислення в епоху NISQ і за її межами. Квант, 2:79, 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] Михайло О Рабін. Імовірнісний алгоритм перевірки простоти. Журнал теорії чисел, 12(1):128–138, 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] Одед Регев. На решітках, навчання з помилками, випадкові лінійні коди та криптографія. Журнал ACM (JACM), 56(6):1–40, 2009.
https: / / doi.org/ 10.1145 / 1568318.1568324
[37] Ден Шеперд і Майкл Бремнер. Тимчасово неструктуроване квантове обчислення. Праці Королівського товариства A: Математичні, фізичні та інженерні науки, 465(2105):1413–1439, 2009.
https: / / doi.org/ 10.1098 / rspa.2008.0443
[38] Петро Шор. Алгоритми квантових обчислень: дискретні логарифми та розкладання на множники. У матеріалах 35-го щорічного симпозіуму з основ інформатики, сторінки 124–134. IEEE, 1994.
https:///doi.org/10.1109/SFCS.1994.365700
[39] Юлінь Ву, Ван-Су Бао, Сіруй Цао, Фушен Чен, Мін-Чен Чен, Сявей Чен, Тун-Сунь Чун, Хуей Ден, Яцзе Ду, Даоцзінь Фан, Мін Гун, Чен Го, Чу Го, Шаоцзюнь Го, Ляньчен Хань , Ліньїнь Хун, Хе-Лян Хуан, Йон-Хен Хуо, Ліпін Лі, На Лі, Шаовей Лі, Юань Лі, Футянь Лян, Чунь Лінь, Цзінь Лінь, Хаорань Цянь, Дан Цяо, Хао Жун, Хун Су, Ліхуа Сунь, Ляньюань Ван, Шию Ван, Дачао Ву, Ю Сюй, Кай Янь, Вейфен Ян, Ян Ян, Янсен Є, Цзянхань Інь, Чонг Ін, Цзяле Юй, Чень Чжа, Ча Чжан, Хайбінь Чжан, Кайлі Чжан, Імін Чжан, Хань Чжао , Ювей Чжао, Лян Чжоу, Цінлін Чжу, Чао-Ян Лу, Чен-Жі Пен, Сяобо Чжу та Цзянь-Вей Пан. Сильна квантова обчислювальна перевага з використанням надпровідного квантового процесора. фіз. Rev. Lett., 127:180501, 2021.
https: / / doi.org/ 10.1103 / PhysRevLett.127.180501
[40] K Wright, KM Beck, Sea Debnath, JM Amini, Y Nam, N Grzesiak, JS Chen, NC Pisenti, M Chmielewski, C Collins та ін. Бенчмаркінг 11-кубітового квантового комп’ютера. Nature Communications, 10(1):1–6, 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] Г Вендін. Квантова обробка інформації надпровідними ланцюгами: огляд. Звіти про прогрес у фізиці, 80(10):106001, 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
[42] Адам Бене Воттс, Робін Котарі, Люк Шеффер і Авішай Тал. Експоненціальне розділення між дрібними квантовими ланцюгами та необмеженими дрібними класичними ланцюгами. У матеріалах 51-го щорічного симпозіуму ACM SIGACT з теорії обчислень, сторінки 515–526, 2019 р.
https: / / doi.org/ 10.1145 / 3313276.3316404
[43] Ендрю Чі-Чі Яо. Як генерувати та обмінюватися секретами. У 27-му щорічному симпозіумі з основ інформатики (sfcs 1986), сторінки 162–167. IEEE, 1986.
https:///doi.org/10.1109/SFCS.1986.25
[44] Цінлін Чжу, Сіруй Цао, Фушен Чен, Мін-Чен Чен, Сявей Чен, Тун-Хсунь Чун, Хуей Ден, Яцзе Ду, Даоцзінь Фан, Мін Гун, Чен Го, Чу Го, Шаоцзюнь Го, Ляньчен Хань, Ліньінь Хун, Хе -Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang , Дачао Ву, Юлінь Ву, Ю Сюй, Кай Янь, Вейфен Ян, Ян Ян, Янсен Є, Цзянхань Інь, Чон Ін, Цзяле Юй, Чень Чжа, Ча Чжан, Хайбінь Чжан, Кайлі Чжан, Імін Чжан, Хань Чжао, Ювей Чжао, Лян Чжоу, Чао-Ян Лу, Чен-Жи Пен, Сяобо Чжу та Цзянь-Вей Пан. Квантова обчислювальна перевага через 60-кубітну 24-циклову випадкову вибірку схеми. Науковий вісник, 67(3):240–245, 2022.
https:///doi.org/10.1016/j.scib.2021.10.017
[45] Дайвей Чжу, Грегорі Д. Каханамоку-Майєр, Лаура Льюїс, Крістал Ноел, Ор Кац, Бахаа Харраз, Цінфен Ван, Ендрю Різінгер, Лей Фенг, Дебопрійо Бісвас, Лейрд Іган, Александру Георгіу, Юнсон Нам, Томас Відік, Умеш Вазірані, Норман Ю. Яо, Марко Четіна та Крістофер Монро. Інтерактивні протоколи для класично перевіреної квантової переваги. Препринт arXiv arXiv:2112.05156, 2021.
https:///doi.org/10.48550/arXiv.2112.05156
arXiv: 2112.05156
[46] Хань-Сен Чжун, Хуей Ван, Ю-Хао Ден, Мін-Чен Чен, Лі-Чао Пен, І-Хань Луо, Цзянь Цінь, Діан Ву, Сін Дін, І Ху, Пен Ху, Сяо-Янь Ян, Вей- Цзюнь Чжан, Хао Лі, Юйсюань Лі, Сяо Цзян, Лінь Ган, Гуанвень Ян, Ліксінг Ю, Жень Ван, Лі Лі, Най-Ле Лю, Чао-Ян Лу та Цзянь-Вей Пан. Квантова обчислювальна перевага використання фотонів. Наука, 370(6523):1460–1463, 2020.
https:///doi.org/10.1126/science.abe8770
Цитується
[1] Натанан Тантівасадакарн, Ашвін Вішванат та Рубен Верресен, «Ієрархія топологічного порядку з унітарних систем кінцевої глибини, вимірювання та прямого зв’язку», arXiv: 2209.06202.
[2] Сергій Бравий, Ісаак Кім, Олександр Кліш і Роберт Кеніг, «Адаптивні схеми постійної глибини для маніпулювання неабелевими анйонами», arXiv: 2205.01933.
[3] Дайвей Чжу, Грегорі Д. Каханамоку-Меєр, Лаура Льюїс, Крістал Ноель, Ор Кац, Бахаа Гарраз, Цінфен Ван, Ендрю Різінгер, Лей Фенг, Дебопрійо Бісвас, Лерд Іган, Александру Георгіу, Юнсон Нам, Томас Відік, Умеш Вазірані, Норман Й. Яо, Марко Четіна та Крістофер Монро, «Інтерактивні протоколи для квантової переваги, що піддається класичній перевірці», arXiv: 2112.05156.
[4] Віпін Сінгх Сехрават, Фу Йі Йео та Дмитро Васильєв, «Специфічні ключові гомоморфні PRF із лінійної регресії та екстремальної теорії множин», arXiv: 2205.00861.
[5] Грегорі Д. Каханамоку-Майєр, Сунвон Чой, Умеш В. Вазірані та Норман Яо Яо, «Квантова перевага, яку можна класично перевірити за допомогою обчислювального тесту Белла», Фізика природи 18 8, 918 (2022).
[6] Розбех Бассіріан, Адам Буланд, Білл Фефферман, Сем Ганн і Авішай Тал, «Про сертифіковану випадковість з експериментів із квантовою перевагою», arXiv: 2111.14846.
[7] Най-Хуі Чіа та Ши-Хан Хунг, «Класична перевірка квантової глибини», arXiv: 2205.04656.
[8] Акіхіро Мізутані, Юкі Такеучі, Ріо Хіромаса, Юсуке Аікава та Сейічіро Тані, «Комп’ютерне самотестування для заплутаних магічних станів», Physical Review A 106 1, L010601 (2022).
[9] Yihui Quek, Mark M. Wilde, and Eneet Kaur, “Multivariate trace estimation in constant quantum depth”, arXiv: 2206.15405.
Вищезазначені цитати від SAO / NASA ADS (останнє оновлення успішно 2022-09-21 12:16:02). Список може бути неповним, оскільки не всі видавці надають відповідні та повні дані про цитування.
On Служба, на яку посилається Crossref даних про цитування робіт не знайдено (остання спроба 2022-09-21 12:16:00).
Ця стаття опублікована в Quantum під Creative Commons Attribution 4.0 International (CC на 4.0) ліцензія. Авторське право залишається за оригінальними власниками авторських прав, такими як автори або їх установи.
