Генеративный анализ данных

Квантовый

Квантовое преимущество в квантовых вычислениях, основанных на измерениях и плоских во времени

Переиздано Платоном
Переиздано Платоном

Дата:

Вид: 0

Майкл де Оливейра1,2,3, Луис С. Барбоза1,2,3и Эрнесто Ф. Гальван3,4

1Университет Минью, факультет компьютерных наук, Брага, Португалия
2INESC TEC, Брага, Португалия
3Международная Иберийская лаборатория нанотехнологий (INL) Av. Местре Хосе Вейга, 4715-330, Брага, Португалия
4Институт физики, Федеральный университет Флуминенсе Av. Гал. Милтон Таварес де Соуза s/n, Нитерой, RJ, 24210-340, Бразилия

Находите эту статью интересной или хотите обсудить? Scite или оставить комментарий на SciRate.

Абстрактные

Было показано, что несколько классов квантовых схем обеспечивают преимущество в квантовых вычислениях при определенных предположениях. Изучение все более ограниченных классов квантовых схем, способных к квантовому преимуществу, мотивировано возможными упрощениями экспериментальных демонстраций. В этой статье мы изучаем эффективность квантовых вычислений на основе измерений с полностью плоским временным упорядочением измерений. Мы предлагаем новые конструкции для детерминированного вычисления произвольных булевых функций, опираясь на корреляции, присутствующие в многокубитных состояниях Гринбергера, Хорна и Цайлингера (GHZ). Мы характеризуем необходимую сложность измерения с помощью иерархии Клиффорда, а также в целом уменьшаем количество необходимых кубитов по сравнению с предыдущими конструкциями. В частности, мы идентифицируем семейство булевых функций, для которых возможно детерминированное вычисление с использованием неадаптивного MBQC, обладающее квантовым преимуществом в ширине и количестве элементов по сравнению с классическими схемами.

Рекомендованное изображение: неадаптивная модель MBQC может быть описана конкретной вычислительной архитектурой, которая разделена на процесс подготовки квантового состояния, процедуру измерения и соответствующую до- и постклассическую линейную обработку (вверху слева). Эта модель облегчает изучение требований к ресурсам для оценки симметричных булевых функций с точки зрения асимптотического числа кубитов и необходимых операций (вверху справа). Эти элементы раскрывают наши основные результаты (внизу), которые сформулированы для стандартных классических и квантовых наборов вентилей, а также описания схем (внизу слева), характеризующие набор булевых функций, которые демонстрируют квантовое преимущество в отношении количества вентилей и ширины схемы (внизу справа).

[Встраиваемое содержимое]

Популярное резюме

Квантовые вычисления обещают обеспечить вычислительное преимущество по сравнению с лучшими классическими алгоритмами для решения многих задач. Точные результаты, количественно определяющие это преимущество, редки и помогают сосредоточить исследования на важнейших квантовых ресурсах, которые обеспечивают производительность выше классической. Это квантовое преимущество может иметь место в отношении различных ресурсов: общего количества требуемых вентилей, глубины получаемых схем или размера используемой памяти (известного как ширина схемы).

В этой работе мы анализируем вычисление булевых функций, что могут делать квантовые компьютеры, используя коррелированные результаты измерений запутанных состояний Гринбергера-Хорна-Цайлингера (GHZ) многих кубитов. Этот вариант квантовых вычислений на основе измерений не требует адаптивности, поэтому все кубиты можно измерять одновременно. Эта плоская временная структура вычислительного процесса в некоторых случаях приводит к созданию очень экономичных квантовых схем. Мы определяем характеристики булевой функции, которые определяют, сколько кубитов необходимо и требуемую точность измерения. Мы показываем, что для конкретного семейства булевых функций существует строгое преимущество в ширине и количестве элементов по сравнению с соответствующим семейством классических схем. В будущем наши методы могут помочь разработать более эффективные способы использования квантовых ресурсов для адаптивных схем, демонстрирующих большую вычислительную выразительность.

► Данные BibTeX

► Рекомендации

[1] Скотт Ааронсон, ДеВон Ингрэм и Уильям Кречмер. «Акробатика BQP». Шачар Ловетт, редактор 37-й конференции по сложности вычислений (CCC 2022). Том 234 Международных трудов Лейбница по информатике (LIPIcs), страницы 20:1–20:17. Дагштуль, Германия (2022 г.). Замок Дагштуль – Центр информатики Лейбница.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2022.20

[2] Ричард Джожа и Ноа Линден. «О роли запутанности в квантово-вычислительном ускорении». Труды Лондонского королевского общества. Серия A: Математические, физические и технические науки 459, 2011–2032 (2003).
https: / / doi.org/ 10.1098 / rspa.2002.1097

[3] Марк Ховард, Джоэл Уоллман, Виктор Вейч и Джозеф Эмерсон. «Контекстуальность обеспечивает «магию» квантовых вычислений». Природа 510, 351–355 (2014).
https: / / doi.org/ 10.1038 / nature13460

[4] Хуан Бермехо-Вега, Николас Дельфосс, Дэн Э. Браун, Сихан Окай и Роберт Рауссендорф. «Контекстуальность как ресурс для моделей квантовых вычислений с кубитами». Физ. Преподобный Летт. 119, 120505 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.120505

[5] Эрнесто Ф. Гальван. «Дискретные функции Вигнера и ускорение квантовых вычислений». Физ. Ред. А 71, 042302 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.042302

[6] А. Мари и Дж. Эйсерт. «Положительные функции Вигнера делают классическое моделирование квантовых вычислений эффективным». Физ. Преподобный Летт. 109, 230503 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.230503

[7] Лов К. Гровер. «Преимущества суперпозиции». Наука 280, 228–228 (1998).
https: / / doi.org/ 10.1126 / science.280.5361.228

[8] Роберт Рауссендорф и Ганс Дж. Бригель. «Односторонний квантовый компьютер». физ. Преподобный Летт. 86, 5188–5191 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[9] Маартен Ван ден Нест, Акимаса Мияке, Вольфганг Дюр и Ханс Дж. Бригель. «Универсальные ресурсы для квантовых вычислений на основе измерений». Физ. Преподобный Летт. 97, 150504 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.150504

[10] Джанет Андерс и Дэн Э. Браун. «Вычислительная мощность корреляций». Физ. Преподобный Летт. 102, 050502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.050502

[11] Винсент Данос и Эльхам Кашефи. «Детерминизм в односторонней модели». Физ. Ред. А 74, 052310 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052310

[12] Дэниел Э. Браун, Эльхам Кашефи, Мехди Мхалла и Саймон Пердрикс. «Обобщенный поток и детерминизм в квантовых вычислениях, основанных на измерениях». Новый журнал физики 9, 250 (2007).
https:/​/​doi.org/​10.1088/​1367-2630/​9/​8/​250

[13] Майкл Дж. Бремнер, Эшли Монтанаро и Дэн Дж. Шеперд. «Средняя сложность по сравнению с приближенным моделированием коммутирующих квантовых вычислений». Физ. Преподобный Летт. 117, 080501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.080501

[14] Мэтти Дж. Хобан, Джоэл Дж. Уоллман, Хуссейн Анвар, Наири Ашер, Роберт Рауссендорф и Дэн Э. Браун. «Классические вычисления, основанные на измерениях». Физ. Преподобный Летт. 112, 140505 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.112.140505

[15] Майкл Дж. Бремнер, Эшли Монтанаро и Дэн Дж. Шеперд. «Достижение квантового превосходства с помощью редких и шумных коммутирующих квантовых вычислений». Квант 1, 8 (2017).
https:/​/​doi.org/​10.22331/​q-2017-04-25-8

[16] Леонардо Ново, Хуани Бермехо-Вега и Рауль Гарсиа-Патрон. «Квантовое преимущество измерений энергии квантовых систем многих тел». Квант 5, 465 (2021).
https:/​/​doi.org/​10.22331/​q-2021-06-02-465

[17] Масахито Хаяси и Юки Такеучи. «Проверка коммутирующих квантовых вычислений посредством оценки точности взвешенных состояний графа». Новый журнал физики 21, 93060 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab3d88

[18] Хуан Бермехо-Вега, Доминик Ханглайтер, Мартин Шварц, Роберт Рауссендорф и Йенс Эйсерт. «Архитектуры для квантового моделирования, демонстрирующие квантовое ускорение». Физ. Ред. X 8, 021010 (2018).
https: / / doi.org/ 10.1103 / PhysRevX.8.021010

[19] Джейкоб Миллер, Стивен Сандерс и Акимаса Мияке. «Квантовое превосходство в вычислениях, основанных на измерениях в постоянном времени: унифицированная архитектура для выборки и проверки». Физ. Ред. А 96, 062320 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062320

[20] Мэтти Дж. Хобан, Эрл Т. Кэмпбелл, Клеархос Лукопулос и Дэн Э. Браун. «Неадаптивные квантовые вычисления на основе измерений и многосторонние неравенства Белла». Новый журнал физики 13, 23014 (2011).
https:/​/​doi.org/​10.1088/​1367-2630/​13/​2/​023014

[21] Рюхей Мори. «Периодическое Фурье-представление булевых функций». Квантовая информация. Вычислить. 19, 392–412 (2019). URL: https://dl.acm.org/doi/abs/10.5555/3370251.3370253.
https: / / dl.acm.org/ дои / ABS / 10.5555 / 3370251.3370253

[22] Маркус Фрембс, Сэм Робертс, Эрл Т. Кэмпбелл и Стивен Д. Бартлетт. «Иерархии ресурсов для квантовых вычислений на основе измерений». Новый физический журнал 25, 013002 (2023).
https://doi.org/10.1088/1367-2630/acaee2

[23] Елена Макепранг, Дэниел Бхатти, Мэтти Дж. Хобан и Стефани Барз. «Мощь кутритов для неадаптивных квантовых вычислений, основанных на измерениях». Новый физический журнал 25, 073007 (2023).
https://doi.org/10.1088/1367-2630/acdf77

[24] Дэниел Коллинз, Николя Гизин, Санду Попеску, Дэвид Робертс и Валерио Скарани. «Неравенства типа Белла для обнаружения истинной неразделимости $mathit{n}$-тела». Физ. Преподобный Летт. 88, 170405 (2002).
https: / / doi.org/ 10.1103 / PhysRevLett.88.170405

[25] Николя Бруннер, Даниэль Кавальканти, Стефано Пиронио, Валерио Скарани и Стефани Венер. «Колокольная нелокальность». Преподобный Мод. физ. 86, 419–478 (2014).
https: / / doi.org/ 10.1103 / RevModPhys.86.419

[26] Дмитрий Кравченко. «Квантовые игры, квантовые состояния, их свойства и приложения». Кандидатская диссертация. Латвийский университет. (2013).

[27] Уильям Слофстра. «Нижние границы запутанности, необходимые для игры в нелокальные игры XOR». Журнал математической физики 52, 102202 (2011).
https: / / doi.org/ 10.1063 / 1.3652924

[28] Андрис Амбайнис, Янис Ираидс, Дмитрий Кравченко и Мадарс Вирза. «Преимущество квантовых стратегий в случайных симметричных играх xor». Антонин Кучера, Томас А. Хенцингер, Ярослав Нешетржил, Томаш Войнар и Давид Антош, редакторы журнала «Математические и инженерные методы в информатике». Страницы 57–68. Берлин, Гейдельберг (2013). Шпрингер Берлин Гейдельберг.
https:/​/​doi.org/​10.1007/​978-3-642-36046-6_7

[29] Андрис Амбайнис и Янис Ираидс. «Доказуемое преимущество квантовых стратегий в случайных симметричных играх XOR». Симоне Северини и Фернандо Брандао, редакторы, 8-я конференция по теории квантовых вычислений, связи и криптографии (TQC 2013). Том 22 Международных трудов Лейбница по информатике (LIPIcs), страницы 146–156. Дагштуль, Германия (2013). Замок Дагштуль – Центр информатики Лейбница.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2013.146

[30] Сэмюэл Маркович и Бенни Резник. «Последствия сложности связи в многосторонних системах». Физ. Ред. А 77, 032120 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.032120

[31] Марцин Павловский, Томаш Патерек, Дагомир Кашликовский, Валерио Скарани, Андреас Винтер и Марек Жуковский. «Информационная причинность как физический принцип». Природа 461, 1101–1104 (2009).
https: / / doi.org/ 10.1038 / nature08400

[32] Санду Попеску и Даниэль Рорлих. «Квантовая нелокальность как аксиома». Основы физики 24, 379–385 (1994).
https: / / doi.org/ 10.1007 / BF02058098

[33] Джонатан Барретт, Ной Линден, Серж Массар, Стефано Пиронио, Санду Попеску и Дэвид Робертс. «Нелокальные корреляции как теоретико-информационный ресурс». Физ. Ред. А 71, 022101 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.022101

[34] АА Разборов. «Квантовая коммуникационная сложность симметричных предикатов». Известия: Математика 67, 145 (2003).
https:/​/​doi.org/​10.1070/​IM2003v067n01ABEH000422

[35] Чжицян Чжан и Яоюнь Ши. «Коммуникационные сложности симметричных функций XOR». Квантовая информация и вычисления 9, 255–263 (2009). URL: https://dl.acm.org/doi/abs/10.5555/2011781.2011786.
https: / / dl.acm.org/ дои / ABS / 10.5555 / 2011781.2011786

[36] Пьер Боттерон. «Нелокальные ящики и сложность связи». Дипломная работа. Университет Поля Сабатье Тулузы III. (2022). URL: https://pierre-botteron.github.io/Articles/2022-06-MSc-Thesis.pdf.
https://pierre-botteron.github.io/Articles/2022-06-MSc-Thesis.pdf

[37] Квангиль Пэ и Вонмин Сон. «Обобщенные критерии нелокальности при корреляционной симметрии». Физ. Ред. А 98, 022116 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.022116

[38] Маркус Фрембс, Сэм Робертс и Стивен Д. Бартлетт. «Контекстуальность как ресурс для квантовых вычислений, основанных на измерениях, за пределами кубитов». Новый журнал физики 20, 103011 (2018).
https: / / doi.org/ 10.1088 / 1367-2630 / aae3ad

[39] Сергей Бравый, Дэвид Госсет и Роберт Кениг. «Квантовое преимущество с мелкими цепями». Наука 362, 308–311 (2018).
https: / / doi.org/ 10.1126 / science.aar3106

[40] Дэниел Гриер и Люк Шеффер. «Интерактивные мелкие схемы Клиффорда: квантовое преимущество перед NC¹ и за его пределами». В материалах 52-го ежегодного симпозиума ACM SIGACT по теории вычислений. Страницы 875–888. STOC 2020Нью-Йорк, Нью-Йорк, США (2020). Ассоциация вычислительной техники.
https: / / doi.org/ 10.1145 / 3357713.3384332

[41] Либор Каха, Ксавье Куато-Руа и Роберт Кениг. «Телепортация с одним кубитом обеспечивает квантовое преимущество» (2022). arXiv: 2209.14158.
Arxiv: 2209.14158

[42] Франсуа Ле Галль. «Квантовое преимущество в среднем случае с мелкими цепями». Амир Шпилька, редактор 34-й конференции по сложности вычислений (CCC 2019). Том 137 Международных трудов Лейбница по информатике (LIPIcs), страницы 21:1—21:20. Дагштуль, Германия (2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2019.21

[43] Мэтью Кудрон, Джалекс Старк и Томас Видик. «Торговля локальностью на время: поддающаяся сертификации случайность из схем малой глубины». Коммуникации по математической физике 382, ​​49–86 (2021).
HTTPS: / / doi.org/ 10.1007 / s00220-021-03963-ш

[44] Сергей Бравый, Дэвид Госсет, Роберт Кениг и Марко Томамичел. «Квантовое преимущество с шумными мелкими схемами». Физика природы 16, 1040–1045 (2020).
HTTPS: / / doi.org/ 10.1038 / s41567-020-0948-г

[45] Ацуя Хасэгава и Франсуа Ле Галль. «Квантовое преимущество с мелкими цепями в условиях произвольной коррупции». Хи-Кап Ан и Кунихико Садакане, редакторы 32-го Международного симпозиума по алгоритмам и вычислениям (ISAAC 2021). Том 212 Международных трудов Лейбница по информатике (LIPIcs), страницы 74: 1–74: 16. Дагштуль, Германия (2021 г.). Замок Дагштуль – Центр информатики Лейбница.
https: / / doi.org/ 10.4230 / LIPIcs.ISAAC.2021.74

[46] Адам Бене Уоттс, Робин Котари, Люк Шеффер и Авишай Тал. «Экспоненциальное разделение между мелкими квантовыми схемами и неограниченными мелкими классическими схемами с веером». В материалах 51-го ежегодного симпозиума ACM SIGACT по теории вычислений. Страницы 515–526. STOC 2019Нью-Йорк, штат Нью-Йорк, США (2019). Ассоциация вычислительной техники.
https: / / doi.org/ 10.1145 / 3313276.3316404

[47] Натали Парэм. «О мощности и ограничениях мелких квантовых схем». Дипломная работа. Университет Ватерлоо. (2022). URL: https://uwspace.uwaterloo.ca/handle/10012/18702.
https: // uwspace.uwaterloo.ca/ handle / 10012/18702

[48] Дмитрий Маслов, Джин-Сунг Ким, Сергей Бравый, Теодор Джей Йодер и Сара Шелдон. «Квантовое преимущество для вычислений в ограниченном пространстве». Физика природы 17, 894–897 (2021).
https:/​/​doi.org/​10.1038/​s41567-021-01271-7

[49] Фарид Аблаев, Аида Гайнутдинова, Марек Карпински, Кристофер Мур и Кристофер Поллетт. «О вычислительной мощности вероятностных и квантовых ветвящихся программ». Информация и вычисления 203, 145–162 (2005).
https: / / doi.org/ 10.1016 / j.ic.2005.04.003

[50] Д. Шеперд и М. Дж. Бремнер. «Временно неструктурированные квантовые вычисления». Труды Лондонского королевского общества, серия A 465, 1413–1439 (2009).
https: / / doi.org/ 10.1098 / rspa.2008.0443

[51] Дэниел М. Гринбергер, Майкл А. Хорн и Антон Цайлингер. «Выход за пределы теоремы Белла». В Менасе Кафатосе, редакторе журнала «Теорема Белла, квантовая теория и концепции Вселенной». Страницы 69–72. Дордрехт (1989). Спрингер Нидерланды.
https:/​/​doi.org/​10.1007/​978-94-017-0849-4_10

[52] Диого Крус, Ромен Фурнье, Фабьен Гремион, Аликс Жаннеро, Кеничи Комагата, Тара Тошич, Ярла Тиесбруммель, Чун Лам Чан, Николя Макрис, Марк-Андре Дюпертюи и Клеман Жаверзак-Гали. «Эффективные квантовые алгоритмы для состояний GHZ и W и их реализация на квантовом компьютере IBM». Передовые квантовые технологии 2, 1900015 (2019).
https: / / doi.org/ 10.1002 / qute.201900015

[53] Р. Ф. Вернер и М. М. Вольф. «Всемногочастные неравенства корреляции колокола для двух дихотомических наблюдаемых на сайте». физ. Ред. А 64, 032112 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.032112

[54] Райан О'Доннелл. «Анализ булевых функций». Издательство Кембриджского университета. (2014). URL: http:/​/​www.cs.cmu.edu/​ ./​odonnell/​papers/​Anaлиз-of-Boolean-Functions-by-Ryan-ODonnell.pdf.
http://​/​www.cs.cmu.edu/​~./​odonnell/​papers/​Anaлиз-of-Boolean-Functions-by-Ryan-ODonnell.pdf

[55] Анастасия Чистопольская и Владимир Владимирович Подольский. «Сложность дерева решений о четности больше, чем степень детализации» (2018). arXiv: 1810.08668.
Arxiv: 1810.08668

[56] Канто и М. Видео. «Симметричные булевы функции». Транзакции IEEE по теории информации 51, 2791–2811 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.851743

[57] Ларри Дж. Стокмейер. «О комбинационной сложности некоторых симметричных булевых функций». Теория математических систем 10, 323–336 (1976).
https: / / doi.org/ 10.1007 / BF01683282

[58] РФ Арнольд и М.А. Харрисон. «Алгебраические свойства симметричных и частично симметричных булевых функций». Транзакции IEEE на электронных компьютерах EC-12, 244–251 (1963).
https://doi.org/10.1109/PGEC.1963.263535

[59] Ан Брекен и Барт Пренил. «Об алгебраической иммунности симметричных булевых функций». В Субхамой Майтре, CE Вени Мадхаване и Рамаратнаме Венкатесане, редакторах, Progress in Cryptology – INDOCRYPT 2005. Том 3797 конспектов лекций по информатике, страницы 35–48. Берлин, Гейдельберг (2005). Шпрингер Берлин Гейдельберг.
https: / / doi.org/ 10.1007 / 11596219_4

[60] Гарри Бурман и Рональд де Вольф. «Меры сложности и сложность дерева решений: обзор». Теоретическая информатика 288, 21–43 (2002).
https:/​/​doi.org/​10.1016/​S0304-3975(01)00144-X

[61] Мэтью Эми, Дмитрий Маслов, Мишель Моска и Мартин Реттелер. «Алгоритм «встреча посередине» для быстрого синтеза квантовых схем с оптимальной глубиной». Транзакции IEEE по автоматизированному проектированию интегральных схем и систем 32, 818–830 (2013).
https: / / doi.org/ 10.1109 / TCAD.2013.2244643

[62] В.В. Шенде, С.С. Буллок и И.Л. Марков. «Синтез квантово-логических схем». Транзакции IEEE по автоматизированному проектированию интегральных схем и систем 25, 1000–1010 (2006).
https: / / doi.org/ 10.1109 / TCAD.2005.855930

[63] Юха Вартиайнен, Микко Мёттонен и Мартти М Саломаа. «Эффективное разложение квантовых вентилей». Физ. Преподобный Летт. 92, 177902 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.92.177902

[64] Бэй Цзэн, Се Чен и Исаак Л. Чуан. «Операции полуклиффорда, структура иерархии $mathcal{C}_{k}$ и сложность вентилей для отказоустойчивых квантовых вычислений». Физ. Ред. А 77, 042313 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.042313

[65] Гэри Дж. Муни, Чарльз Д. Хилл и Ллойд К. Л. Холленберг. «Оптимальный по стоимости синтез однокубитных вентилей в иерархии Клиффорда». Квант 5, 396 (2021).
https:/​/​doi.org/​10.22331/​q-2021-02-15-396

[66] Надиш де Силва. «Эффективная телепортация квантовых ворот в более высокие измерения». Труды Королевского общества A 477, 20200865 (2021).
https: / / doi.org/ 10.1098 / rspa.2020.0865

[67] Дэниел Готтесман и Исаак Л. Чуанг. «Демонстрация жизнеспособности универсальных квантовых вычислений с использованием телепортации и однокубитных операций». Природа 402, 390–393 (1999).
https: / / doi.org/ 10.1038 / 46503

[68] Дэниел Готтесман. «Гейзенберговское представление квантовых компьютеров» (1998). arXiv:quant-ph/9807006.
Arxiv: колич-фот / 9807006

[69] Вадим Ключников, Дмитрий Маслов и Мишель Моска. «Быстрый и эффективный точный синтез однокубитных унитарных элементов, генерируемых Клиффордом и t-воротами». Квантовая информация. Вычислить. 13, 607–630 (2013). URL: https://dl.acm.org/doi/abs/10.5555/2535649.2535653.
https: / / dl.acm.org/ дои / ABS / 10.5555 / 2535649.2535653

[70] Николас Бруннер, Джеймс Шарам и Тамаш Вертези. «Проверка структуры многочастной запутанности с помощью колоколовых неравенств». Физ. Преподобный Летт. 108, 110501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.108.110501

[71] Джулия Кемпе, Хиротада Кобаяши, Кейджи Мацумото, Бен Тонер и Томас Видик. «Запутанные игры трудно аппроксимировать». SIAM Journal on Computing 40, 848–877 (2011).
https: / / doi.org/ 10.1137 / 090751293

[72] Ихуэй Квек, Энеет Каур и Марк М. Уайльд. «Многомерная оценка следов при постоянной квантовой глубине». Квант 8, 1220 (2024).
https:/​/​doi.org/​10.22331/​q-2024-01-10-1220

[73] Питер Селинджер. «Эффективное приближение Клиффорда + Т однокубитных операторов». Квантовая информация. Вычислить. 15, 159–180 (2015).

[74] Вадим Ключников, Дмитрий Маслов и Мишель Моска. «Практическая аппроксимация однокубитных унитарных единиц однокубитными квантовыми Клиффордом и Т-схемами». Транзакции IEEE на компьютерах 65, 161–172 (2016).
https: / / doi.org/ 10.1109 / TC.2015.2409842

[75] Нил Дж. Росс. «Оптимальное безвспомогательное приближение КЛИФФОРДА + V для Z-вращений». Квантовая информация. Вычислить. 15, 932–950 (2015). URL: https://dl.acm.org/doi/abs/10.5555/2871350.2871354.
https: / / dl.acm.org/ дои / ABS / 10.5555 / 2871350.2871354

[76] Итан Бернштейн и Умеш Вазирани. «Квантовая теория сложности». В материалах двадцать пятого ежегодного симпозиума ACM по теории вычислений. Страницы 11–20. STOC '93 Нью-Йорк, Нью-Йорк, США (1993). Ассоциация вычислительной техники.
https: / / doi.org/ 10.1145 / 167088.167097

[77] Алекс Бочаров, Мартин Реттелер и Криста М Своре. «Эффективный синтез вероятностных квантовых схем с резервным копированием». Физ. Ред. А 91, 052317 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.052317

[78] Алекс Бочаров, Мартин Реттелер и Криста М Своре. «Эффективный синтез универсальных квантовых схем, повторяющихся до успеха». Физ. Преподобный Летт. 114, 080502 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.080502

[79] Инго Вегенер. «Сложность булевых функций». Джон Уайли $&$ Sons, Inc. США (1987).

[80] Гериберт Фоллмер. «Введение в сложность схем: единый подход». Издательская компания Springer, Incorporated. (2010). 1-е издание. URL: https://link.springer.com/book/10.1007/978-3-662-03927-4.
https:/​/​link.springer.com/​book/​10.1007/​978-3-662-03927-4

[81] Р Смоленский. «Алгебраические методы в теории нижних оценок сложности булевых схем». В материалах девятнадцатого ежегодного симпозиума ACM по теории вычислений. Страницы 77–82. STOC '87 Нью-Йорк, Нью-Йорк, США (1987). Ассоциация вычислительной техники.
https: / / doi.org/ 10.1145 / 28395.28404

[82] Джайкумар Радхакришнан. «Лучшие оценки для пороговых формул». В [1991] Материалы 32-го ежегодного симпозиума по основам информатики. Страницы 314–323. Компьютерное общество IEEE (1991).
https: / / doi.org/ 10.1109 / SFCS.1991.185384

[83] Майкл Дж. Фишер, Альберт Р. Мейер и Майкл С. Патерсон. «$Omega(Nlog n)$ Нижние границы длины булевых формул». СИАМ Дж. Компьютер. 11, 416–427 (1982).
https: / / doi.org/ 10.1137 / 0211033

[84] Санджив Арора и Боаз Барак. «Вычислительная сложность: современный подход». Издательство Кембриджского университета. США (2009). 1-е издание. URL: https://dl.acm.org/doi/abs/10.5555/1540612.
https: / / dl.acm.org/ дои / ABS / 10.5555 / 1540612

[85] Скотт Ааронсон. «Какая структура необходима для огромного квантового ускорения?» (2022). arXiv: 2209.06930.
Arxiv: 2209.06930

[86] Дэвид А Баррингтон. «Ветвящиеся программы ограниченной ширины полиномиального размера распознают именно эти языки в NC1». Журнал компьютерных и системных наук 38, 150–164 (1989).
https:/​/​doi.org/​10.1016/​0022-0000(89)90037-8

[87] Скотт Ааронсон и Алекс Архипов. «Вычислительная сложность линейной оптики». В материалах сорок третьего ежегодного симпозиума ACM по теории вычислений. Страницы 333–342. STOC '11Нью-Йорк, штат Нью-Йорк, США (2011 г.). Ассоциация вычислительной техники.
https: / / doi.org/ 10.1145 / 1993636.1993682

[88] Питер В. Шор. «Алгоритмы полиномиального времени для простой факторизации и дискретных логарифмов на квантовом компьютере». SIAM Review 41, 303–332 (1999).
https: / / doi.org/ 10.1137 / S0036144598347011

[89] Дэниел Р. Саймон. «О возможностях квантовых вычислений». SIAM Journal on Computing 26, 1474–1483 (1997).
https: / / doi.org/ 10.1137 / S0097539796298637

[90] Жиль Брассар, Гарри Бурман, Ноа Линден, Андре Аллан Мето, Ален Тапп и Унгер Фальк. «Ограничение нелокальности в любом мире, в котором сложность связи нетривиальна». Физ. Преподобный Летт. 96, 250401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.96.250401

[91] Вим ван Дам. «Неправдоподобные последствия сверхсильной нелокальности». Естественные вычисления 12, 9–12 (2013).
https:/​/​doi.org/​10.1007/​s11047-012-9353-6

[92] Мэтью Эми и Мишель Моска. «Оптимизация T-счета и коды Рида – Мюллера». Транзакции IEEE по теории информации 65, 4771–4784 (2019).
https: / / doi.org/ 10.1109 / TIT.2019.2906374

[93] Петер Бюргиссер, Михаэль Клаузен и Мохаммад Шокроллахи. «Алгебраическая теория сложности». Том 315. Springer Science & Business Media. (2013). URL: https://dl.acm.org/doi/abs/10.5555/1965416.
https: / / dl.acm.org/ дои / ABS / 10.5555 / 1965416

[94] Гуанг Хао Лоу и Исаак Л. Чуанг. «Оптимальное гамильтоново моделирование с помощью квантовой обработки сигналов». физ. Преподобный Летт. 118, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

[95] Чонван Хаа. «Произведение разложения периодических функций при квантовой обработке сигналов». Квант 3, 190 (2019).
https:/​/​doi.org/​10.22331/​q-2019-10-07-190

[96] Скотт Ааронсон, Шалев Бен-Дэвид, Робин Котари, Шравас Рао и Авишай Тал. «Степень против приблизительной степени и квантовые последствия теоремы Хуанга о чувствительности». В материалах 53-го ежегодного симпозиума ACM SIGACT по теории вычислений. Страницы 1330–1342. STOC 2021Нью-Йорк, штат Нью-Йорк, США (2021 г.). Ассоциация вычислительной техники.
https: / / doi.org/ 10.1145 / 3406325.3451047

[97] Хао Хуан. «Индуцированные подграфы гиперкубов и доказательство гипотезы чувствительности». Анналы математики 190, 949–955 (2019).
https: / / doi.org/ 10.4007 / annals.2019.190.3.6

[98] Андрис Амбайнис, Каспарс Балодис, Александр Беловс, Трой Ли, Миклош Санта и Юрис Смотровс. «Разделение сложности запроса на основе функций указателя». Журнал ACM 64 (2017).
https: / / doi.org/ 10.1145 / 3106234

[99] Петер Хойер и Роберт Шпалек. «Квантовые схемы с неограниченным разветвлением». В Хельмуте Альте и Мишеле Хабибе, редакторах, STACS 2003. Страницы 234–246. Берлин, Гейдельберг (2003). Шпрингер Берлин Гейдельберг.
https:/​/​doi.org/​10.1007/​3-540-36494-3_22

[100] Остин К. Дэниел, Инъюэ Чжу, К. Уэрта Альдерете, Викас Бучеммавари, Алайна М. Грин, Нхунг Х. Нгуен, Тайлер Дж. Тертелл, Эндрю Чжао, Норберт М. Линке и Акимаса Мияке. «Преимущество квантовых вычислений, подтвержденное нелокальными играми с циклическим состоянием кластера». Физ. Ред. Исследования 4, 033068 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033068

[101] Пол Херрингер и Роберт Рауссендорф. «Классификация квантовой проволоки на основе измерений в стабилизаторе PEPS». Квантум 7, 1041 (2023).
https:/​/​doi.org/​10.22331/​q-2023-06-12-1041

[102] Абхишек Ананд. «О мощности чередующихся квантовых и классических схем малой глубины». Дипломная работа. Университет Ватерлоо. (2022). URL: https://uwspace.uwaterloo.ca/handle/10012/18805.
https: // uwspace.uwaterloo.ca/ handle / 10012/18805

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

[104] Бюлент Демирель, Вейкай Венг, Кристофер Талакер, Мэтти Хобан и Стефани Барз. «Корреляции для вычислений и вычисления для корреляций». npj Quantum Information 7, 1–8 (2021).
https:/​/​doi.org/​10.1038/​s41534-020-00354-2

[105] Маноранджан Суэйн, Амит Рай, Бикаш К. Бехера и Прасанта К. Паниграхи. «Экспериментальная демонстрация нарушений неравенств Мермина и Светличного для состояний W и GHZ». Квантовая обработка информации 18, 218 (2019).
https:/​/​doi.org/​10.1007/​s11128-019-2331-5

[106] Бо Ян, Руди Рэймонд, Хироши Имаи, Хёнсок Чанг и Хидефуми Хираиси. «Тестирование масштабируемых неравенств Белла для состояний квантового графа на квантовых устройствах IBM». Журнал IEEE по новым и избранным темам в схемах и системах 12, 638–647 (2022).
https://​/​doi.org/​10.1109/​JETCAS.2022.3201730

[107] Ф. Баккари, Р. Аугусиак, И. Шупич, Й. Тура и А. Ачин. «Масштабируемые неравенства колокола для состояний графа кубита и надежное самотестирование». Физ. Преподобный Летт. 124, 020402 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.124.020402

[108] Кен Икс Вей, Исаак Лауэр, Шрикант Шринивасан, Ниреджа Сундаресан, Дуглас Т. МакКлюр, Дэвид Тойли, Дэвид С. Маккей, Джей М. Гамбетта и Сара Шелдон. «Проверка многочастных запутанных состояний Гринбергера-Хорна-Цайлингера с помощью множественных квантовых когерентностей». Физ. Ред. А 101, 032343 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.032343

[109] Вэй-Цзя Хуан, Вэй-Чен Цзянь, Цзянь-Хун Чо, Че-Чун Хуан, Цунг-Вэй Хуан и Чинг-Рэй Чанг. «Неравенства Мермина для нескольких кубитов с ортогональными измерениями в 53-кубитной системе IBM Q». Квантовая инженерия 2, e45 (2020).
https://​/​doi.org/​10.1002/​que2.45

[110] Мерон Шеффер, Даниэль Азсес и Эмануэле Дж. Далла Торре. «Игра в квантовые нелокальные игры с шестью шумными кубитами в облаке». Передовые квантовые технологии 5, 2100081 (2022).
https: / / doi.org/ 10.1002 / qute.202100081

[111] Ведран Дунько, Теодорос Капурниотис и Эльхам Кашефи. «Квантовые безопасные делегированные классические вычисления». Квантовая информация. Вычислить. 16, 61–86 (2016).

[112] Стефани Барз, Ведран Дунько, Флориан Шледерер, Мерритт Мур, Элхам Кашефи и Ян А. Уолмсли. «Расширенные делегированные вычисления с использованием когерентности». Физ. Ред. А 93, 032339 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.032339

[113] Марко Клементи, Анна Паппа, Андреас Экстайн, Ян Уолмсли, Элхам Кашефи и Стефани Барз. «Классические многосторонние вычисления с использованием квантовых ресурсов». Физическое обозрение А 96, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062317

[114] Насир Ахмед и Камисетти Рамамохан Рао. «Преобразование Уолша-Адамара». В ортогональных преобразованиях для цифровой обработки сигналов. Страницы 99–152. Спрингер (1975).

[115] Майкл А. Нильсен и Исаак Л. Чуанг. «Квантовые вычисления и квантовая информация: издание к 10-летию». Издательство Кембриджского университета. (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667

[116] Филип Фейнсильвер и Ежи Кочик. «Полиномы Кравчука и матрицы Кравчука». Страницы 115–141. Последние достижения в области прикладной теории вероятности. Спрингер США. Бостон, Массачусетс (2005).
https:/​/​doi.org/​10.1007/​0-387-23394-6_5

[117] Филип Файнсильвер и Рене Шотт. «Преобразования Кравчука и свертки». Вестник математических наук, страницы 1–19 (2018).
https:/​/​doi.org/​10.1007/​s13373-018-0132-2

[118] М. Стобинска, А. Бурачевски, М. Мур, В. Р. Клементс, Дж. Дж. Ренема, С. В. Нам, Т. Герритс, А. Лита, В. С. Колтхаммер, А. Экстайн и И. А. Уолмсли. «Квантовая интерференция обеспечивает обработку квантовой информации в постоянном времени». Достижения науки 5, eaau9674 (2019).
https: / / doi.org/ 10.1126 / sciadv.aau9674

[119] Равиндран Каннан и Ахим Бачем. «Полиномиальные алгоритмы вычисления нормальных форм Смита и Эрмита целочисленной матрицы». SIAM Journal on Computing 8, 499–507 (1979).
https: / / doi.org/ 10.1137 / 0208040

[120] Джош Алман и Вирджиния Василевска Уильямс. «Усовершенствованный лазерный метод и более быстрое умножение матриц». В материалах тридцать второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Страница 522–539. СОДА '21США (2021). Общество промышленной и прикладной математики.
https: / / doi.org/ 10.1137 / 1.9781611976465.32

Цитируется

Эта статья опубликована в Quantum под Creative Commons Attribution 4.0 International (CC BY 4.0) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.

Spot_img

Последняя разведка

Spot_img

Авторские права @ 2024 Plato Technologies Inc.