Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В квантовых вычислениях , квантовое Превосходство или квантовое преимущество является целью демонстрации того, что программируемое квантовое устройство может решить проблему , что ни один классического компьютер не может решить в любом допустимом количестве времени (независимо от полезности этой проблемы). [1] [2] [3] Концептуально квантовое превосходство включает в себя как инженерную задачу создания мощного квантового компьютера, так и теоретико-вычислительную задачу поиска проблемы, которая может быть решена этим квантовым компьютером и имеет сверхполиномиальное ускорение по сравнению с самый известный или возможный классический алгоритм для этой задачи. [4] [5] Термин был введенДжон Прескилл в 2012 г., [1] [6], но концепция квантового вычислительного преимущества, особенно для моделирования квантовых систем, восходит к предложениям Юрия Манина (1980) [7] и Ричарда Фейнмана (1981) о квантовых вычислениях. вычисления. [8] Примеры предложений для демонстрации квантового превосходства включают предложение о дискретизации бозонов Ааронсона и Архипова [9] , специализированные проблемы фрустрированного кластерного цикла D-Wave [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 Systems из Бернаби в Британской Колумбии стала первой компанией, продающей квантовый компьютер на коммерческой основе. [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 Magazine предположил, что квантовое превосходство может произойти в 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 актуален, поскольку самый мощный суперкомпьютер того времени, Summit , был создан IBM. [39] [14] [40]

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

Вычислительная сложность [ править ]

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

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

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

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

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

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

Алгоритм Шора для факторизации целых чисел [ править ]

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

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

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

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

Отбор проб бозона [ править ]

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

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

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

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

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

Критика [ править ]

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

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

Критика названия [ править ]

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

См. Также [ править ]

  • Список квантовых процессоров
    • Процессор Sycamore
    • Цзючжан (квантовый компьютер)

Ссылки [ править ]

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