Квантовое превосходство - Quantum supremacy

В квантовые вычисления, квантовое превосходство или же квантовое преимущество Цель состоит в том, чтобы продемонстрировать, что программируемое квантовое устройство может решить проблему, которую ни один классический компьютер не может решить за любой возможный промежуток времени (независимо от полезности проблемы).[1][2][3] Концептуально квантовое превосходство включает в себя как инженерную задачу создания мощного квантового компьютера, так и теоретико-вычислительной сложности задача поиска проблемы, которую может решить этот квантовый компьютер и которая имеет суперполином ускорение по наиболее известному или возможному классическому алгоритму для этой задачи.[4][5] Термин был придуман Джон Прескилл в 2012,[1][6] но концепция квантового вычислительного преимущества, особенно для моделирования квантовых систем, восходит к Юрий Манин s (1980)[7] и Ричард Фейнман (1981) предложения квантовых вычислений.[8] Примеры предложений продемонстрировать квантовое превосходство включают выборка бозонов предложение Ааронсон и Архипов,[9] D-волны специализированные проблемы фрустрированного кластерного цикла,[10] и выборка вывода случайных квантовые схемы.[11]

Примечательным свойством квантового превосходства является то, что его можно реально достичь с помощью квантовых компьютеров в ближайшем будущем,[6] поскольку ему не требуется квантовый компьютер для выполнения каких-либо полезных задач[12] или используйте качественные квантовая коррекция ошибок,[13] оба из которых являются долгосрочными целями.[2] Следовательно, исследователи рассматривают квантовое превосходство в первую очередь как научную цель, имеющую относительно небольшое непосредственное влияние на будущую коммерческую жизнеспособность квантовых вычислений.[2] Поскольку эта цель - создание квантового компьютера, который может выполнять задачу, которую не может выполнить ни один другой существующий компьютер, - может стать более сложной, если классические компьютеры или алгоритмы моделирования улучшатся, квантовое превосходство может быть временно или многократно достигнуто, что ставит претензии на достижение квантового превосходства под значительную внимательное изучение.[14][15]

Фон

Квантовое превосходство в 20 веке

В 1936 г. Алан Тьюринг опубликовал свою статью «О вычислимых числах»,[16] в ответ на 1900 г. Проблемы Гильберта. В статье Тьюринга описывается то, что он назвал «универсальной вычислительной машиной», которая позже стала известна как Машина Тьюринга. В 1980 г. Пол Бениофф использовал статью Тьюринга, чтобы предложить теоретическую осуществимость квантовых вычислений. Его статья «Компьютер как физическая система: микроскопическая квантово-механическая гамильтонова модель компьютеров, представленная машинами Тьюринга»,[17] был первым, кто продемонстрировал, что можно показать обратимую природу квантовых вычислений, пока рассеиваемая энергия сколь угодно мала. В 1981 г. Ричард Фейнман показал, что квантовую механику нельзя моделировать на классических устройствах.[18] Во время лекции он произнес знаменитую цитату: «Природа не является классической, черт возьми, и если вы хотите смоделировать природу, вам лучше сделать ее квантово-механической, и, черт возьми, это замечательная проблема, потому что это не так. это не выглядит так просто ».[18] Вскоре после этого Дэвид Дойч подготовил описание для квантовая машина Тьюринга и разработал алгоритм создан для работы на квантовом компьютере.[19]

В 1994 году дальнейший прогресс в направлении квантового превосходства был достигнут, когда Петр Шор сформулирован Алгоритм Шора, оптимизация метода факторизации целых чисел за полиномиальное время.[20] Позже, в 1995 году, Кристофер Монро и Дэвид Вайнленд опубликовали свою статью «Демонстрация фундаментальной квантовой логической логики»,[21] отмечая первую демонстрацию квантовый логический вентиль, в частности двухбитный "контролируемый-НЕ ". В 1996 г. Лов Гровер пробудил интерес к созданию квантового компьютера после публикации своего алгоритма, Алгоритм Гровера в своей статье «Быстрый квантово-механический алгоритм поиска в базе данных».[22] В 1998 г. Джонатан А. Джонс и Микеле Моска опубликовал «Реализация квантового алгоритма для решения проблемы Дойча на квантовом компьютере с ядерным магнитным резонансом»,[23] отмечая первую демонстрацию квантового алгоритма.

Прогресс в 21 веке

Огромный прогресс в направлении квантового превосходства был достигнут в 2000-х годах с первого 5-кубита. Ядерный магнитный резонанс компьютер (2000), демонстрация теоремы Шора (2001) и реализация Алгоритм Дойча в кластерном квантовом компьютере (2007).[24] В 2011, Системы D-Wave из Бернаби в Британской Колумбии стала первой компанией, которая начала продавать квантовый компьютер на коммерческой основе.[25] В 2012 году физик Наньян Сюй совершил важное достижение, применив улучшенный алгоритм адиабатического разложения до множителя 143. Однако методы, использованные Сюй, встретили возражения.[26] Вскоре после этого достижения Google приобрела свой первый квантовый компьютер.[27]

Google объявили о планах продемонстрировать квантовое превосходство до конца 2017 года с массивом из 49 сверхпроводящие кубиты.[28] В начале января 2018 г. Intel анонсировала аналогичную аппаратную программу.[29] В октябре 2017 г. IBM продемонстрировали моделирование 56 кубитов на классическом суперкомпьютере, тем самым увеличив вычислительную мощность, необходимую для установления квантового превосходства.[30] В ноябре 2018 года Google объявила о партнерстве с НАСА которая будет «анализировать результаты квантовых схем, работающих на квантовых процессорах Google, и ... обеспечивать сравнения с классическим моделированием, чтобы поддержать Google в проверке своего оборудования и установить основу для квантового превосходства».[31] Теоретическая работа, опубликованная в 2018 году, предполагает, что квантовое превосходство должно быть возможным с «двумерной решеткой из 7x7 кубитов и около 40 тактовых циклов», если частота ошибок может быть достаточно низкой.[32] 18 июня 2019 г. Журнал Quanta предположил, что квантовое превосходство может произойти в 2019 году, согласно Закон Невена.[33] 20 сентября 2019 г. Financial Times сообщил, что «Google утверждает, что достиг квантового превосходства с массивом из 54 кубитов, из которых 53 были функциональными, которые использовались для выполнения серии операций за 200 секунд, на выполнение которых суперкомпьютеру потребовалось бы около 10 000 лет».[34][35] 23 октября Google официально подтвердил претензии.[36][37][38] В ответ IBM предположила, что некоторые претензии чрезмерны, и предположила, что это может занять 2,5 дня вместо 10 000 лет, перечислив методы, которые классический суперкомпьютер может использовать для максимизации скорости вычислений. Ответ IBM актуален как самый мощный суперкомпьютер того времени, Саммит, был сделан IBM.[39][14][40]

В декабре 2020 года группа, базирующаяся в USTC утверждали, что достигли квантового превосходства за счет реализации типа Отбор проб бозона на 76 фотонов с их фотонный квантовый компьютер Цзючжан.[41][42][43] В документе говорится, что для генерации количества выборок, которое квантовый компьютер генерирует за 20 секунд, классическому компьютеру потребуется 600 миллионов лет вычислений.[44]

Вычислительная сложность

Основная статья: Квантовая теория сложности

Сложность аргументы касаются того, какое количество ресурсов необходимо для решения проблемы (обычно время или же объем памяти ) масштабируется с размером ввода. В этой настройке проблема состоит из введенных экземпляр проблемы (двоичная строка) и возвращенное решение (соответствующая строка вывода), а Ресурсы относится к обозначенным элементарным операциям, использованию памяти или обмену данными. Набор локальных операций позволяет компьютеру генерировать выходную строку. Модель схемы и соответствующие операции полезны при описании как классических, так и квантовых проблем; классическая модель схемы состоит из основных операций, таких как И ворота, ИЛИ ворота, и НЕ ворота в то время как квантовая модель состоит из классических схем и применения унитарных операций. В отличие от конечного набора классических вентилей, существует бесконечное количество квантовых вентилей из-за непрерывного характера унитарных операций. Как в классическом, так и в квантовом случаях сложность возрастает с увеличением размера проблемы.[45] Как продолжение классической теория сложности вычислений, квантовая теория сложности считает, что теоретический универсальный квантовый компьютер можно было бы достичь без учета сложности создания физического квантового компьютера или работы с декогеренция и шум.[46] С квантовая информация является обобщением классическая информация, квантовые компьютеры может смоделировать любой классический алгоритм.[46]

Классы квантовой сложности представляют собой наборы задач, которые используют общую квантовую вычислительную модель, причем каждая модель содержит определенные ограничения ресурсов. Схемные модели полезны при описании классов квантовой сложности.[47] Самый полезный класс квантовой сложности - BQP (квантово-полиномиальное время с ограниченной ошибкой), класс проблемы решения это может быть решено в полиномиальное время по универсальный квантовый компьютер.[48] Вопросы о BQP все еще остаются, такие как связь между BQP и иерархией полиномиального времени, содержит ли BQP НП-полный задач, а также точные нижние и верхние границы класса BQP. Ответы на эти вопросы не только раскрыли бы природу BQP, но также ответили бы на сложные вопросы классической теории сложности. Одна из стратегий для лучшего понимания BQP - это определение связанных классов, их упорядочение в обычную иерархию классов, а затем поиск свойств, которые обнаруживаются в их отношении к BQP.[49] Есть несколько других классов квантовой сложности, например QMA (квантовый Мерлин Артур) и QIP (квантовое интерактивное полиномиальное время).[47]

Сложность доказательства того, что нельзя сделать с помощью классических вычислений, является общей проблемой при окончательной демонстрации квантового превосходства. В отличие от задач принятия решения, требующих ответа «да» или «нет», при задачах выборки образцы запрашиваются у распределения вероятностей.[50] Если есть классический алгоритм который может эффективно выполнять выборку из вывода произвольной квантовая схема, то полиномиальная иерархия рухнет до третьего уровня, что обычно считается маловероятным.[11] Отбор проб бозона - более конкретное предложение, классическая твердость которого зависит от сложности расчета постоянный большой матрицы со сложными элементами, которая является # P-complete проблема.[51] Аргументы, использованные для такого вывода, также были распространены на IQP Sampling,[52] где нужна только гипотеза, что средняя и наихудшая сложность задачи одинакова.[50]

Предлагаемые эксперименты

Ниже приведены предложения по демонстрации превосходства квантовых вычислений с использованием современных технологий, часто называемых устройствами NISQ.[2] Такие предложения включают (1) четко определенную вычислительную задачу, (2) квантовый алгоритм для решения этой проблемы (3) сравнительный лучший классический алгоритм для решения проблемы и (4) теоретико-сложный аргумент о том, что при разумном предположении ни один классический алгоритм не может работать значительно лучше, чем существующие алгоритмы (так что квантовый алгоритм алгоритм по-прежнему обеспечивает суперполином ускорение).[4][53]

Алгоритм Шора факторизации целых чисел

Основная статья: Алгоритм Шора

Этот алгоритм находит разложение на простые множители п-битовое целое число в время[54] тогда как самый известный классический алгоритм требует время и лучшая верхняя оценка сложности этой задачи .[55] Это также может обеспечить ускорение решения любой проблемы, которая сводится к целочисленный факторинг, включая проблему членства для матричные группы над поля нечетного порядка.[56]

Этот алгоритм важен как практически, так и исторически для квантовые вычисления. Это было первое полиномиальное время квантовый алгоритм предложен для реальной проблемы, которая считается сложной для классических компьютеров.[54] А именно, он дает суперполиномиальное ускорение при разумном предположении, что ЮАР, самый распространенный на сегодняшний день протокол шифрования, безопасен.[57]

Факторинг имеет некоторое преимущество перед другими предложениями о превосходстве, потому что факторинг может быть проверил быстро с классическим компьютером, просто умножая целые числа, даже в больших случаях, когда алгоритмы факторизации чрезвычайно медленны. Однако реализация алгоритма Шора для больших чисел невозможна с использованием современных технологий,[58][59] поэтому он не преследуется как стратегия демонстрации превосходства.

Отбор проб бозона

Основная статья: Отбор проб бозона

Эта вычислительная парадигма основана на отправке идентичных фотоны через линейно-оптическая сеть может решить определенные задачи выборки и поиска, которые, если предположить несколько гипотез теории сложности (которые вычисляют постоянный гауссовых матриц есть # P-Hard и что полиномиальная иерархия не разрушается) для классических компьютеров трудноразрешимы.[9] Однако было показано, что выборка бозонов в системе с достаточно большими потерями и шумом можно эффективно моделировать.[60]

Самая большая экспериментальная реализация отбора бозонов на сегодняшний день имела 6 режимов, поэтому могла обрабатывать до 6 фотонов одновременно.[61] Лучшее из предложенных классических алгоритм для моделирования пробоотбора бозонов во времени для системы с п фотоны и м режимы вывода.[62][63] Бозон это реализация с открытым исходным кодом в р. Алгоритм приводит к оценке 50 фотоны требуется для демонстрации квантового превосходства с помощью выборки бозонов.[62][63]

Выборка выходного распределения случайных квантовых схем

Самый известный алгоритм для моделирования произвольного случайного квантовая схема требует времени, которое экспоненциально масштабируется с количеством кубиты, что привело к оценке одной группы, что около 50 кубиты может быть достаточно, чтобы продемонстрировать квантовое превосходство.[32] Google объявили о своем намерении продемонстрировать квантовое превосходство к концу 2017 года, построив и запустив 49-кубит чип, который мог бы в разумные сроки отбирать дистрибутивы, недоступные для любых современных классических компьютеров.[28] Самый большой универсал квантовая схема Симулятор, работающий на классических суперкомпьютерах того времени, мог моделировать 48 кубитов.[64] Но для определенных типов цепей больше квантовая схема возможно моделирование с 56 кубитами.[65] Это может потребовать увеличения количества кубиты продемонстрировать квантовое превосходство.[30] 23 октября 2019 года Google опубликовал результаты этого эксперимента квантового превосходства в статье Nature «Квантовое превосходство с использованием программируемого сверхпроводящего процессора», в которой они разработали новый 53-кубитный процессор под названием «Сикамор», способный быстро выполнять , высокая точность квантовые логические ворота, чтобы выполнить эталонное тестирование. Google утверждает, что их машина выполнила целевые вычисления за 200 секунд, и подсчитал, что их классический алгоритм на самом быстром суперкомпьютере в мире потребует 10 000 лет, чтобы решить ту же проблему.[66] IBM оспорила это утверждение, заявив, что улучшенный классический алгоритм должен решить эту проблему за два с половиной дня на том же суперкомпьютере.[67][68][69]

Критика

Восприимчивость к ошибке

Квантовые компьютеры гораздо более подвержены ошибкам, чем классические компьютеры из-за декогеренция и шум.[70] В пороговая теорема утверждает, что шумный квантовый компьютер может использовать квантовые коды исправления ошибок[71][72] для моделирования бесшумного квантового компьютера, предполагая, что ошибка, вносимая в каждый компьютерный цикл, меньше некоторого числа.[73] Численное моделирование показывает, что это число может достигать 3%.[74] Однако пока окончательно не известно, как ресурсы, необходимые для исправление ошибки будет масштабироваться с количеством кубиты.[75] Скептики указывают на неизвестное поведение шума в увеличенных квантовых системах как на потенциальное препятствие для успешной реализации квантовых вычислений и демонстрации квантового превосходства.[70][76]

Критика названия

Некоторые исследователи предложили не использовать термин «квантовое превосходство», утверждая, что слово «превосходство» вызывает неприятные сравнения с расистской верой в белое превосходство. Спорный[77][78] Природа Комментарий, подписанный тринадцатью исследователями, утверждает, что вместо этого следует использовать альтернативную фразу «квантовое преимущество».[79][80] Джон Прескилл, профессор теоретической физики Калифорнийский технологический институт Кто придумал этот термин, с тех пор пояснил, что этот термин был предложен для явного описания момента, когда квантовый компьютер получает способность выполнять задачу, которую классический компьютер никогда не мог. Он также пояснил, что специально отверг термин «квантовое преимущество», поскольку он не полностью отражает значение его нового термина: слово «преимущество» будет означать, что компьютер с квантовым превосходством будет иметь небольшое преимущество перед классическим компьютером, в то время как слово «превосходство» лучше передает полное превосходство над любым классическим компьютером.[6]

Смотрите также

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

  1. ^ а б Прескилл, Джон (26 марта 2012). «Квантовые вычисления и граница запутанности». arXiv:1203.5813 [Quant-ph ].
  2. ^ а б c d Прескилл, Джон (2018-08-06). «Квантовые вычисления в эпоху NISQ и за ее пределами». Квантовый. 2: 79. Дои:10.22331 / q-2018-08-06-79.
  3. ^ Чжун, Хан-Сен; Ван, Хуэй; Дэн Ю-Хао; Чен, Мин-Ченг; Пэн Ли-Чао; Ло, И-Хан; Цинь, Цзянь; Ву, Диан; Дин, Син; Ху, Йи; Ху, Пэн (2020-12-03). «Квантовое вычислительное преимущество с использованием фотонов». Наука. Дои:10.1126 / science.abe8770 (неактивно 05.12.2020). ISSN  0036-8075. PMID  33273064.CS1 maint: DOI неактивен по состоянию на декабрь 2020 г. (связь)
  4. ^ а б Харроу, Арам В .; Монтанаро, Эшли (сентябрь 2017 г.). «Квантовое вычислительное превосходство». Природа. 549 (7671): 203–209. arXiv:1809.07442. Bibcode:2017Натура.549..203H. Дои:10.1038 / природа23458. ISSN  1476-4687. PMID  28905912. S2CID  2514901.
  5. ^ Папагеоргиу, Анаргирос; Трауб, Джозеф Ф. (12 августа 2013 г.). «Меры ускорения квантовых вычислений». Физический обзор A. 88 (2): 022316. arXiv:1307.7488. Bibcode:2013PhRvA..88b2316P. Дои:10.1103 / PhysRevA.88.022316. ISSN  1050-2947. S2CID  41867048.
  6. ^ а б c Джон Прескилл объясняет квантовое превосходство'". Журнал Quanta. Получено 2020-04-21.
  7. ^ Манин, Ю. И. (1980). Вычислимое и невычислимое [Вычислимые и невычислимые] (на русском). Сов.радио. С. 13–15. Архивировано из оригинал на 2013-05-10. Получено 2013-03-04.
  8. ^ Фейнман, Ричард П. (1982-06-01). «Моделирование физики с помощью компьютеров». Международный журнал теоретической физики. 21 (6–7): 467–488. Bibcode:1982IJTP ... 21..467F. CiteSeerX  10.1.1.45.9310. Дои:10.1007 / BF02650179. ISSN  0020-7748. S2CID  124545445.
  9. ^ а б Ааронсон, Скотт; Архипов, Алексей (2011). Вычислительная сложность линейной оптики.. Труды сорок третьего ежегодного симпозиума ACM по теории вычислений. СТОК '11. Нью-Йорк, Нью-Йорк, США: ACM. С. 333–342. arXiv:1011.3245. Дои:10.1145/1993636.1993682. ISBN  9781450306911. S2CID  681637.
  10. ^ Кинг, Джеймс; Яркони, Шейр; Раймонд, Джек; Озфидан, Исил; Кинг, Эндрю Д .; Невиси, Майссам Мохаммади; Хилтон, Джереми П .; МакГеоч, Кэтрин С. (17 января 2017 г.). «Квантовый отжиг в условиях локальной жесткости и глобального разочарования». arXiv:1701.04579 [Quant-ph ].
  11. ^ а б Ааронсон, Скотт; Чен, Лицзе (18 декабря 2016 г.). "Теоретико-сложные основы экспериментов по квантовому превосходству". arXiv:1612.05903 [Quant-ph ].
  12. ^ Мец, Кейд (23.10.2019). "Google заявляет о квантовом прорыве, который может изменить вычисления (опубликовано в 2019 г.)". Нью-Йорк Таймс. ISSN  0362-4331. Получено 2020-12-07.
  13. ^ Ааронсон, Скотт (30 октября 2019 г.). "Мнение | Почему важна веха квантового превосходства Google (опубликовано в 2019 г.)". Нью-Йорк Таймс. ISSN  0362-4331. Получено 2020-12-07.
  14. ^ а б «О» квантовом превосходстве"". Блог IBM Research. 2019-10-22. Получено 2019-10-24.
  15. ^ Крейн, Лия. "IBM заявляет, что Google, возможно, все-таки не достигла квантового превосходства". Новый ученый. Получено 2020-12-07.
  16. ^ Тьюринг, Алан (1936). О вычислимых числах в приложении к задаче Entscheidungs..
  17. ^ Бениофф, Пол (1980-05-01). «Компьютер как физическая система: микроскопическая квантово-механическая гамильтонова модель компьютеров, представленная машинами Тьюринга». Журнал статистической физики. 22 (5): 563–591. Bibcode:1980JSP .... 22..563B. Дои:10.1007 / BF01011339. ISSN  1572-9613. S2CID  122949592.
  18. ^ а б Фейнман, Ричард П. (1982-06-01). «Моделирование физики с помощью компьютеров». Международный журнал теоретической физики. 21 (6): 467–488. Bibcode:1982IJTP ... 21..467F. Дои:10.1007 / BF02650179. ISSN  1572-9575. S2CID  124545445.
  19. ^ «Квантовые вычисления». Стэнфордская энциклопедия философии. 30 сентября 2019.
  20. ^ Шор, Питер (1996). Полиномиальные алгоритмы простой факторизации и дискретных логарифмов на квантовом компьютере.
  21. ^ Monroe, C .; Микхоф, Д. М .; King, B.E .; Itano, W. M .; Вайнленд, Д. Дж. (1995-12-18). «Демонстрация фундаментального квантового логического входа». Письма с физическими проверками. 75 (25): 4714–4717. Bibcode:1995ПхРвЛ..75.4714М. Дои:10.1103 / PhysRevLett.75.4714. ISSN  0031-9007. PMID  10059979.
  22. ^ Гровер, Лов К. (1996-11-19). «Быстрый квантово-механический алгоритм поиска по базе данных». ArXiv: Quant-ph / 9605043. arXiv:Quant-ph / 9605043. Bibcode:1996квант.ч..5043Г.
  23. ^ Jones, J. A .; Моска, М. (август 1998 г.). «Реализация квантового алгоритма для решения проблемы Дойча на квантовом компьютере с ядерным магнитным резонансом». Журнал химической физики. 109 (5): 1648–1653. arXiv:Quant-ph / 9801027. Дои:10.1063/1.476739. ISSN  0021-9606. S2CID  19348964.
  24. ^ Балаганур, Самир (20.11.2019). "Человеческая гонка к квантовому превосходству: полный график". Журнал Analytics India. Получено 2020-11-16.
  25. ^ Мерали, Зея (июнь 2011 г.). «Первая продажа квантовых вычислений». Природа. 474 (7349): 18. Bibcode:2011Натура 474 ... 18 млн. Дои:10.1038 / 474018a. ISSN  0028-0836. PMID  21637232. S2CID  4425833.
  26. ^ Баттерсби, Стивен. «Спорный квантовый компьютер побил рекорд факторинга». Новый ученый. Получено 2020-11-16.
  27. ^ Харди, Квентин (2013-05-16). «Google покупает квантовый компьютер». Блог Bits. Получено 2020-11-16.
  28. ^ а б «Google планирует продемонстрировать превосходство квантовых вычислений». IEEE Spectrum: Новости технологий, инженерии и науки. Получено 2018-01-11.
  29. ^ «CES 2018: 49-кубитный чип Intel побеждает за квантовое превосходство». IEEE Spectrum: Новости технологий, инженерии и науки. Получено 2017-07-22.
  30. ^ а б «Планам Google по квантовым вычислениям угрожает кривая IBM». 20 октября 2017 г.. Получено 22 октября, 2017.
  31. ^ Харрис, Марк. «Google привлекла НАСА, чтобы за несколько месяцев доказать квантовое превосходство». Обзор технологий MIT. Получено 2018-11-30.
  32. ^ а б Бойшо, Серджио; Исаков, Сергей В .; Смелянский, Вадим Н .; Баббуш, Райан; Дин, Нан; Цзян, Чжан; Бремнер, Майкл Дж .; Мартинис, Джон М .; Невен, Хартмут (23 апреля 2018 г.). «Характеризуя квантовое превосходство в устройствах ближайшего времени». Природа Физика. 14 (6): 595–600. arXiv:1608.00263. Bibcode:2018НатФ..14..595Б. Дои:10.1038 / с41567-018-0124-х. S2CID  4167494.
  33. ^ Хартнетт, Кевин (18 июня 2019 г.). "Новый закон, описывающий рост квантовых вычислений?". Журнал Quanta.
  34. ^ [1], Financial Times, Сентябрь 2019 (требуется подписка)
  35. ^ Press, Associated. "Google рекламирует веху в области квантовых вычислений". MarketWatch.
  36. ^ «Демонстрация квантового превосходства» - через www.youtube.com.
  37. ^ «Квантовое превосходство с использованием программируемого сверхпроводящего процессора».
  38. ^ а б Аруте, Франк; и другие. (23 октября 2019 г.). «Квантовое превосходство с использованием программируемого сверхпроводящего процессора». Природа. 574 (7779): 505–510. arXiv:1910.11333. Bibcode:2019Натура.574..505A. Дои:10.1038 / s41586-019-1666-5. PMID  31645734.
  39. ^ "Что означают дебаты Google и IBM по поводу квантового превосходства | ZDNet". www.zdnet.com.
  40. ^ "Google утверждает, что добился квантового превосходства - IBM отступает". NPR.org. Получено 2019-10-24.
  41. ^ Болл, Филипп (2020-12-03). "Физики в Китае оспаривают квантовое преимущество Google'". Природа. Дои:10.1038 / d41586-020-03434-7.
  42. ^ Гаристо, Даниэль. «Световой квантовый компьютер превосходит самые быстрые классические суперкомпьютеры». Scientific American. Получено 2020-12-07.
  43. ^ Коновер, Эмили (2020-12-03). «Новый квантовый компьютер на основе света Jiuzhang достиг квантового превосходства». Новости науки. Получено 2020-12-07.
  44. ^ Чжун, Хан-Сен; Ван, Хуэй; Дэн Ю-Хао; Чен, Мин-Ченг; Пэн Ли-Чао; Ло, И-Хан; Цинь, Цзянь; Ву, Диан; Дин, Син; Ху, Йи; Ху, Пэн (2020-12-03). «Квантовое вычислительное преимущество с использованием фотонов». Наука. Дои:10.1126 / science.abe8770. ISSN  0036-8075. PMID  33273064.
  45. ^ Клив, Ричард (2000). «Введение в теорию квантовой сложности» (PDF). ЦЕРН. Bibcode:2000qcqi.book..103C.
  46. ^ а б Уотроус, Джон (2009). «Квантовая вычислительная сложность». В Мейерс, Роберт А. (ред.). Энциклопедия сложности и системологии. Springer Нью-Йорк. стр.7174 –7201. Дои:10.1007/978-0-387-30440-3_428. ISBN  9780387758886. S2CID  1380135.
  47. ^ а б Уотроус, Джон (21 апреля 2018 г.). «Квантовая вычислительная сложность» (PDF). ArXiv. arXiv:0804.3401.
  48. ^ Тереза, Тусарова (26.09.2004). «Классы квантовой сложности». arXiv:cs / 0409051.
  49. ^ Тусарова, Тереза ​​(2004). «Классы квантовой сложности» (PDF). ArXiv. arXiv:cs / 0409051. Bibcode:2004cs ........ 9051T.
  50. ^ а б Lund, A. P .; Бремнер, Майкл Дж .; Ральф, Т. К. (13 апреля 2017 г.). «Проблемы квантовой дискретизации, BosonSampling и квантового превосходства». Квантовая информация NPJ. 3 (1): 15. arXiv:1702.03061. Bibcode:2017npjQI ... 3 ... 15л. Дои:10.1038 / s41534-017-0018-2. ISSN  2056-6387. S2CID  54628108.
  51. ^ Гард, Брайан Т .; Motes, Keith R .; Олсон, Джонатан П .; Роде, Питер П .; Доулинг, Джонатан П. (август 2015 г.). «Введение в выборку бозонов». От атомного к мезомасштабному: роль квантовой когерентности в системах различной сложности. World Scientific. С. 167–192. arXiv:1406.6767. Дои:10.1142/9789814678704_0008. ISBN  978-981-4678-70-4. S2CID  55999387.
  52. ^ Бремнер, Майкл Дж .; Монтанаро, Эшли; Шеперд, Дэн Дж. (18 августа 2016 г.). «Средняя сложность против приближенного моделирования коммутирующих квантовых вычислений». Письма с физическими проверками. 117 (8): 080501. arXiv:1504.07999. Bibcode:2016ПхРвЛ.117х0501Б. Дои:10.1103 / PhysRevLett.117.080501. ISSN  0031-9007. PMID  27588839. S2CID  8590553.
  53. ^ Джордан, Стивен. "Зоопарк квантовых алгоритмов". math.nist.gov. Архивировано из оригинал на 2018-04-29. Получено 2017-07-29.
  54. ^ а б Шор, П. (1999-01-01). "Полиномиальные алгоритмы простой факторизации и дискретных логарифмов на квантовом компьютере". SIAM Обзор. 41 (2): 303–332. arXiv:Quant-ph / 9508027. Bibcode:1999SIAMR..41..303S. Дои:10.1137 / S0036144598347011. ISSN  0036-1445.
  55. ^ Рубинштейн, Майкл (2006-10-19). «Распределение решений для xy = N mod a с приложением для факторизации целых чисел». arXiv:математика / 0610612.
  56. ^ Бабай, Ласло; Билс, Роберт; Seress, Ákos (2009). Полиномиальная теория матричных групп. Труды сорок первого ежегодного симпозиума ACM по теории вычислений. STOC '09. Нью-Йорк, Нью-Йорк, США: ACM. С. 55–64. CiteSeerX  10.1.1.674.9429. Дои:10.1145/1536414.1536425. ISBN  9781605585062. S2CID  9052772.
  57. ^ Rivest, R.L .; Шамир, А .; Адлеман, Л. (февраль 1978 г.). «Метод получения цифровых подписей и криптосистем с открытым ключом». Commun. ACM. 21 (2): 120–126. CiteSeerX  10.1.1.607.2677. Дои:10.1145/359340.359342. ISSN  0001-0782. S2CID  2873616.
  58. ^ Мартин-Лопес, Энрике; Лэйнг, Энтони; Лоусон, Томас; Альварес, Роберто; Чжоу, Сяо-Ци; О'Брайен, Джереми Л. (ноябрь 2012 г.). «Экспериментальная реализация квантового алгоритма факторизации Шора с использованием рециклинга кубитов». Природа Фотоника. 6 (11): 773–776. arXiv:1111.4147. Bibcode:2012НаФо ... 6..773M. Дои:10.1038 / nphoton.2012.259. ISSN  1749-4893. S2CID  46546101.
  59. ^ Фаулер, Остин Дж .; Мариантони, Маттео; Мартинис, Джон М .; Клеланд, Эндрю Н. (18 сентября 2012 г.). «Поверхностные коды: к практическим крупномасштабным квантовым вычислениям». Физический обзор A. 86 (3): 032324. arXiv:1208.0928. Bibcode:2012PhRvA..86c2324F. Дои:10.1103 / PhysRevA.86.032324. S2CID  119277773.
  60. ^ Рахими-Кешари, Салех; Ральф, Тимоти С .; Пещеры, Карлтон М. (20.06.2016). «Достаточные условия для эффективного классического моделирования квантовой оптики». Физический обзор X. 6 (2): 021039. arXiv:1511.06526. Bibcode:2016PhRvX ... 6b1039R. Дои:10.1103 / PhysRevX.6.021039. S2CID  23490704.
  61. ^ Каролан, Жак; Харролд, Кристофер; Воробей, Крис; Мартин-Лопес, Энрике; Рассел, Николас Дж .; Сильверстоун, Джошуа В .; Shadbolt, Питер Дж .; Мацуда, Нобуюки; Огума, Манабу (14 августа 2015 г.). «Универсальная линейная оптика». Наука. 349 (6249): 711–716. arXiv:1505.01182. Дои:10.1126 / science.aab3642. ISSN  0036-8075. PMID  26160375. S2CID  19067232.
  62. ^ а б Клиффорд, Питер; Клиффорд, Рафаэль (2017-06-05). «Классическая сложность отбора проб бозонов». arXiv:1706.01260 [cs.DS ].
  63. ^ а б Невилл, Алекс; Воробей, Крис; Клиффорд, Рафаэль; Джонстон, Эрик; Birchall, Patrick M .; Монтанаро, Эшли; Лэйнг, Энтони (2017-10-02). «Никакого неминуемого квантового превосходства путем отбора проб бозонов». Природа Физика. 13 (12): 1153–1157. arXiv:1705.00686. Bibcode:2017arXiv170500686N. Дои:10.1038 / nphys4270. ISSN  1745-2473.
  64. ^ Ханс де Рэдт; Фэнпин Цзинь; Деннис Вилльш; Мадита Вилльш; Наоки Йошиока; Нобуясу Ито; Шэнцзюнь Юань; Кристель Михильсен (ноябрь 2018 г.). «Массивно-параллельный симулятор квантового компьютера, одиннадцать лет спустя». Компьютерная физика Коммуникации. 237: 47–61. Дои:10.1016 / j.cpc.2018.11.005.
  65. ^ Эдвин Педно; Джон А. Ганнелс; Джакомо Нанничини; Лиор Хореш; Томас Магерлейн; Эдгар Соломоник; Роберт Виснифф (октябрь 2017 г.). «Преодоление 49-кубитного барьера при моделировании квантовых схем». arXiv:1710.05867 [Quant-ph ].
  66. ^ «Квантовое превосходство с использованием программируемого сверхпроводящего процессора». Блог Google AI. Получено 2019-11-02.
  67. ^ Мец, Кейд (23 октября 2019 г.). «Google заявляет о квантовом прорыве, который может изменить вычисления». Нью-Йорк Таймс. Получено 14 января 2020.
  68. ^ Эдвин Педно; Джон Ганнелс; Джакомо Нанничини; Лиор Хореш; Роберт Виснифф (октябрь 2019 г.). «Использование вторичного хранилища для моделирования глубинных 54-кубитных схем платана». arXiv:1910.09534 [Quant-ph ].
  69. ^ «Столкновение Google и IBM из-за претензии на квантовое превосходство». Журнал Quanta. Получено 2020-10-29.
  70. ^ а б Калаи, Гил (2011-06-02). "Как квантовые компьютеры терпят неудачу: квантовые коды, корреляции в физических системах и накопление шума". arXiv:1106.0485 [Quant-ph ].
  71. ^ Шор, Питер В. (1995-10-01). «Схема уменьшения декогеренции в памяти квантового компьютера». Физический обзор A. 52 (4): R2493 – R2496. Bibcode:1995ПхРвА..52.2493С. Дои:10.1103 / PhysRevA.52.R2493. PMID  9912632.
  72. ^ Стейн, А. М. (1996-07-29). «Коды, исправляющие ошибки в квантовой теории». Письма с физическими проверками. 77 (5): 793–797. Bibcode:1996ПхРвЛ..77..793С. Дои:10.1103 / PhysRevLett.77.793. PMID  10062908.
  73. ^ Ааронов, Дорит; Бен-Ор, Майкл (1999-06-30). «Отказоустойчивые квантовые вычисления с постоянной частотой ошибок». arXiv:Quant-ph / 9906129.
  74. ^ Книл, Э. (2005-03-03). «Квантовые вычисления с реально шумными устройствами». Природа. 434 (7029): 39–44. arXiv:Quant-ph / 0410199. Bibcode:2005Натура.434 ... 39К. Дои:10.1038 / природа03350. ISSN  0028-0836. PMID  15744292. S2CID  4420858.
  75. ^ Калаи, Гил (2016-05-03). «Квантово-компьютерная головоломка (Расширенная версия)». arXiv:1605.00992 [Quant-ph ].
  76. ^ Дьяконов, М. И. (2007). «Возможны ли отказоустойчивые квантовые вычисления?». В С. Лурьи; J. Xu; А. Заславский (ред.). Будущие тенденции в микроэлектронике. Вверх по нано-крику. Вайли. С. 4–18. arXiv:Quant-ph / 0610117. Bibcode:2006quant.ph.10117D.
  77. ^ Правление, Редакция. "Мнение | Достижение квантового пробуждения". WSJ. Получено 2019-12-21.
  78. ^ Knapton, Сара (17 декабря 2019 г.). «Академики, которых высмеивают за утверждение« квантового превосходства », - это расистский и колониальный термин». Телеграф. ISSN  0307-1235. Получено 2019-12-21.
  79. ^ Паласиос-Берракеро, Кармен; Муек, Леони; Персо, Дивья М. (10 декабря 2019 г.). «Вместо« превосходства »используйте« квантовое преимущество ».'". Природа. 576 (7786): 213. Дои:10.1038 / d41586-019-03781-0. PMID  31822842.
  80. ^ «Открытое письмо - Ответственность в квантовой науке».
  81. ^ Мартинис, Джон; Бойшо, Серджио. «Квантовое превосходство с использованием программируемого сверхпроводящего процессора». Блог Google AI. Алфавит. Получено 5 декабря 2019.