1Кафедра физики, ETH Zürich, Швейцария
2Институт теоретических исследований, ETH Zürich, Швейцария
Находите эту статью интересной или хотите обсудить? Scite или оставить комментарий на SciRate.
Абстрактные
Доказательство квантовости — это тип протокола запроса-ответа, в котором классический верификатор может эффективно удостоверить $textit{квантовое преимущество}$ ненадежного проверяющего. То есть квантовый доказывающий может правильно ответить на вопросы верификатора и быть принятым, в то время как любой классический доказывающий за полиномиальное время будет отклонен с высокой вероятностью, основанной на правдоподобных вычислительных предположениях. Чтобы ответить на задачи верификатора, существующие доказательства квантовости обычно требуют, чтобы квантовый доказывающий выполнял комбинацию квантовых схем и измерений полиномиального размера.
В этой статье мы приводим две конструкции доказательства квантовости, в которых доказывающему нужно только выполнить $textit{квантовые схемы постоянной глубины}$ (и измерения) вместе с классическими вычислениями логарифмической глубины. Наша первая конструкция — это общий компилятор, который позволяет нам переводить все существующие доказательства квантовости в версии с постоянной квантовой глубиной. Наша вторая конструкция основана на проблеме $textit{обучения с округлением}$ и дает схемы меньшей глубины и требующие меньшего количества кубитов, чем общая конструкция. Кроме того, вторая конструкция также обладает некоторой устойчивостью к шуму.
► Данные BibTeX
► Рекомендации
[1] Скотт Ааронсон и Алекс Архипов. Вычислительная сложность линейной оптики. В материалах сорок третьего ежегодного симпозиума ACM по теории вычислений, страницы 333–342, 2011 г.
https: / / doi.org/ 10.1145 / 1993636.1993682
[2] Фрэнк Аруте, Кунал Арья, Райан Бэббуш, Дэйв Бэкон, Джозеф С. Бардин, Рами Барендс, Рупак Бисвас, Серджио Бойшо, Фернандо Г.С.Л. Брандао, Дэвид А. Бьюэлл и др. Квантовое превосходство с помощью программируемого сверхпроводящего процессора. Природа, 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] Санджив Арора и Боаз Барак. Вычислительная сложность: современный подход. Издательство Кембриджского университета, 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] Жоэль Алвен, Стефан Кренн, Кшиштоф Петшак и Даниэль Викс. Обучение с округлением, новый взгляд. В Достижениях в области криптологии - КРИПТО 2013, страницы 57–74, Берлин, Гейдельберг, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] Дэвид А Баррингтон. Ветвящиеся программы ограниченной ширины полиномиального размера распознают именно эти языки в ${NC}^1$. Журнал компьютерных и системных наук, 38(1):150–164, 1989.
https://doi.org/10.1016/0022-0000(89)90037-8
[10] Цвика Бракерски, Пол Кристиано, Урмила Махадев, Умеш Вазирани и Томас Видик. Криптографический тест квантовости и удостоверяемой случайности от одного квантового устройства. В 2018 г. на 59-м ежегодном симпозиуме IEEE по основам компьютерных наук (FOCS), страницы 320–331. ИИЭР, 2018.
https: / / doi.org/ 10.1145 / 3441309
[11] Колин Д. Брузевич, Джон Чиаверини, Роберт МакКоннелл и Джереми М. Сейдж. Квантовые вычисления с захваченными ионами: прогресс и проблемы. Обзоры прикладной физики, 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] Серхио Бойшо, Сергей В. Исаков, Вадим Н. Смелянский, Райан Баббуш, Нан Дин, Чжан Цзян, Майкл Дж. Бремнер, Джон М. Мартинис и Хартмут Невен. Характеристика квантового превосходства в ближайших устройствах. Физика природы, 14(6):595–600, 2018.
HTTPS: / / doi.org/ 10.1038 / s41567-018-0124-х
[14] Звика Бракерски, Венката Коппула, Умеш Вазирани и Томас Видик. Простые доказательства квантовости. На 15-й конференции по теории квантовых вычислений, связи и криптографии (TQC 2020), том 158 Международного журнала Лейбница по информатике (LIPIcs), страницы 8:1–8:14, Дагштуль, Германия, 2020. Schloss Dagstuhl-Leibniz- Центр информатики.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8
[15] Абхишек Банерджи, Крис Пейкерт и Алон Розен. Псевдослучайные функции и решетки. В Достижениях в области криптологии - EUROCRYPT 2012, страницы 719–737. Springer Берлин Гейдельберг, 2012.
https://doi.org/10.1007/978-3-642-29011-4_42
[16] Джон Ф. Клаузер, Майкл А. Хорн, Эбнер Шимони и Ричард А. Холт. Предлагаемый эксперимент для проверки локальных теорий скрытых переменных. Письма о физическом обзоре, 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-ш
[18] Ричард Клив и Джон Уотроус. Быстрые параллельные схемы для квантового преобразования Фурье. В материалах 41-го ежегодного симпозиума по основам компьютерных наук, стр. 526–536. ИИЭР, 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 Международного журнала Лейбница по информатике (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] Питер Хойер и Роберт Шпалек. Квантовый разветвитель — это мощно. Теория вычислительной техники, 1(5):81–103, 2005 г.
https: / / doi.org/ 10.4086 / toc.2005.v001a005
[27] Купджин Хуан, Фанг Чжан, Майкл Ньюман, Цзюньцзе Кай, Сюнь Гао, Чжэнсюн Тянь, Цзюньинь Ву, Хайхун Сюй, Хуаньцзюнь Юй, Бо Юань, Марио Сегеди, Яоюнь Ши и Цзяньсин Чен. Классическое моделирование схем квантового превосходства. Препринт 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. Спрингер, 2010.
https: / / doi.org/ 10.1145 / 2535925
[31] Урмила Махадев. Классическая верификация квантовых вычислений. В 2018 г. на 59-м ежегодном симпозиуме IEEE по основам компьютерных наук (FOCS), страницы 259–267. ИИЭР, 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. ИИЭР, 1994.
https: / / doi.org/ 10.1109 / SFCS.1994.365700
[39] Юйлинь Ву, Ван-Су Бао, Сируи Цао, Фушэн Чен, Мин-Чэн Чен, Сявэй Чен, Тун-Сун Чун, Хуэй Дэн, Яцзе Ду, Даоцзинь Фань, Мин Гун, Ченг Го, Чу Го, Шаоцзюнь Го, Ляньчэнь Хань , Линьинь Хун, Хе-Лян Хуан, Юн-Хэн Хо, Липин Ли, На Ли, Шаовей Ли, Юань Ли, Футянь Лян, Чунь Линь, Цзинь Линь, Хаоран Цянь, Дэн Цяо, Хао Жун, Хун Су, Лихуа Сунь, Лянъюань Ван, Шию Ван, Дачао Ву, Юй Сюй, Кай Ян, Вэйфэн Ян, Ян Ян, Янсен Е, Цзянхань Инь, Чун Ин, Цзяле Ю, Чен Чжа, Ча Чжан, Хайбин Чжан, Кайли Чжан, Имин Чжан, Хань Чжао , Ювэй Чжао, Лян Чжоу, Цинлин Чжу, Чао-Ян Лу, Ченг-Чжи Пэн, Сяобо Чжу и Цзянь-Вэй Пань. Сильное квантовое вычислительное преимущество с использованием сверхпроводящего квантового процессора. физ. Преп. Письмо, 127:180501, 2021.
https: / / doi.org/ 10.1103 / PhysRevLett.127.180501
[40] К. Райт, К.М. Бек, Си Дебнат, Дж.М. Амини, И. Нам, Н. Гржесяк, Дж.С. Чен, Н.К. Писенти, М. Хмелевски, К. Коллинз и др. Тестирование квантового компьютера с 11 кубитами. Связь с природой, 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. ИИЭР, 1986.
https: / / doi.org/ 10.1109 / SFCS.1986.25
[44] Цинлин Чжу, Сируй Цао, Фушэн Чен, Мин-Чэн Чен, Сявэй Чен, Тун-Сун Чун, Хуэй Дэн, Яцзе Ду, Даоцзинь Фан, Мин Гун, Ченг Го, Чу Го, Шаоцзюнь Го, Ляньчэнь Хань, Линьинь Хун, Хе -Лян Хуан, Юн-Хэн Хо, Липин Ли, На Ли, Шаовей Ли, Юань Ли, Футянь Лян, Чун Линь, Цзинь Линь, Хаоран Цянь, Дан Цяо, Хао Жун, Хун Су, Лихуа Сун, Лянъюань Ван, Шию Ван , Дачао Ву, Юлинь Ву, Юй Сюй, Кай Ян, Вэйфэн Ян, Ян Ян, Янсен Е, Цзянхань Инь, Чун Ин, Цзяле Юй, Чэнь Чжа, Ча Чжан, Хайбин Чжан, Кайли Чжан, Имин Чжан, Хань Чжао, Ювэй Чжао, Лян Чжоу, Чао-Ян Лу, Ченг-Чжи Пэн, Сяобо Чжу и Цзянь-Вэй Пан. Преимущество квантовых вычислений за счет 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] Акихиро Мизутани, Юки Такеучи, Рё Хиромаса, Юсуке Айкава и Сейичиро Тани, «Вычислительное самотестирование запутанных магических состояний», Физический обзор A 106 1, L010601 (2022).
[9] Йихуи Квек, Марк М. Уайлд и Энит Каур, «Многомерная оценка следов с постоянной квантовой глубиной», Arxiv: 2206.15405.
Приведенные цитаты из САО / НАСА ADS (последнее обновление успешно 2022-09-21 12:16:02). Список может быть неполным, поскольку не все издатели предоставляют подходящие и полные данные о цитировании.
On Цитируемый сервис Crossref Данные о цитировании работ не найдены (последняя попытка 2022-09-21 12:16:00).
Эта статья опубликована в Quantum под Creative Commons Attribution 4.0 International (CC BY 4.0) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.
