stringtranslate.com

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

В квантовых вычислениях квантовое превосходство или квантовое преимущество — это демонстрация того, что программируемый квантовый компьютер может решить проблему, которую не может решить ни один классический компьютер , за любой возможный промежуток времени, независимо от полезности проблемы. [1] [2] [3] Этот термин был придуман Джоном Прескиллом в 2012 году, [1] [4] но концепция восходит к предложениям Юрия Манина 1980 года [5] и Ричарда Фейнмана 1981 года [6] квантовой теории. вычисления.

Концептуально квантовое превосходство включает в себя как инженерную задачу создания мощного квантового компьютера, так и задачу теории сложности вычислений по поиску проблемы, которая может быть решена этим квантовым компьютером и имеет суперполиномиальное ускорение по сравнению с наиболее известным или возможным классическим алгоритмом для этой задачи. задача. [7] [8]

Примеры предложений по демонстрации квантового превосходства включают предложение Ааронсона и Архипова по выборке бозонов [9] и выборку выходных данных случайных квантовых схем . [10] [11] Выходные распределения, полученные в результате измерений при дискретизации бозонов или дискретизации квантовой случайной схемы, являются плоскими, но структурированы таким образом, что невозможно классически эффективно осуществлять выборку из распределения, близкого к распределению, генерируемому квантовый эксперимент . Чтобы этот вывод был справедливым, необходимо использовать лишь очень мягкие предположения теории сложности вычислений. В этом смысле схемы квантовой случайной выборки могут потенциально продемонстрировать квантовое превосходство. [12]

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

Фон

Квантовое преимущество в 20 веке

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

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

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

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

Google объявила о планах продемонстрировать квантовое превосходство до конца 2017 года с помощью массива из 49 сверхпроводящих кубитов . [29] В начале января 2018 года Intel анонсировала аналогичную аппаратную программу. [30] В октябре 2017 года IBM продемонстрировала моделирование 56 кубитов на классическом суперкомпьютере , тем самым увеличив вычислительную мощность, необходимую для установления квантового превосходства. [31] В ноябре 2018 года Google объявила о партнерстве с НАСА , которое будет «анализировать результаты квантовых схем, работающих на квантовых процессорах Google, и… проводить сравнения с классическим моделированием, чтобы помочь Google в проверке своего оборудования и установить базовый уровень для квантовых вычислений». превосходство». [32] Теоретическая работа, опубликованная в 2018 году, предполагает, что квантовое превосходство должно быть возможно с «двумерной решеткой из 7×7 кубитов и примерно 40 тактовыми циклами», если уровень ошибок можно будет снизить до достаточно низкого уровня. [33] Обсуждаемая схема представляла собой вариант схемы квантовой случайной выборки, в которой кубиты проходят случайные квантовые схемы с квантовыми вентилями, взятыми из универсального набора вентилей, с последующими измерениями в вычислительной базе.

18 июня 2019 года журнал Quanta Magazine предположил, что квантовое превосходство может произойти в 2019 году, согласно закону Невена . [34] 20 сентября 2019 года газета Financial Times сообщила, что «Google утверждает, что достигла квантового превосходства с массивом из 54 кубитов, из которых 53 были функциональными, которые использовались для выполнения серии операций за 200 секунд, которые потребовали бы создание суперкомпьютера займет около 10 000 лет». [35] [36] 23 октября Google официально подтвердила эти претензии. [37] [38] [39] В ответ IBM предположила, что некоторые из заявлений были чрезмерными, и предположила, что это может занять 2,5 дня вместо 10 000 лет, перечислив методы, которые классический суперкомпьютер может использовать для максимизации скорости вычислений. Реакция IBM актуальна, поскольку самый мощный суперкомпьютер того времени Summit был создан IBM. [40] [15] [41] С тех пор исследователи разработали более совершенные алгоритмы для решения проблемы выборки, используемые для утверждения квантового превосходства, что существенно сокращает разрыв между процессором Sycamore от Google и классическими суперкомпьютерами [42] [43] [44] и даже превосходит это. [45] [46] [47]

В декабре 2020 года группа из Университета науки и технологий Китая (USTC) под руководством Цзянь-Вэй Паня достигла квантового превосходства, реализовав выборку гауссовских бозонов на 76 фотонах с помощью своего фотонного квантового компьютера Jiuzhang . [48] ​​[49] [50] В документе говорится, что для генерации количества выборок, которые квантовый компьютер генерирует за 200 секунд, классическому суперкомпьютеру потребуется 2,5 миллиарда лет вычислений. [3]

В октябре 2021 года команды USTC снова заявили о квантовом первенстве, построив два суперкомпьютера под названием Jiuzhang 2.0 и Zuchongzhi. В светильнике Jiuzhang 2.0 реализована выборка гауссовских бозонов для обнаружения 113 фотонов от 144-модового оптического интерферометра, а частота дискретизации увеличена до10 24 – разница в 37 фотонов и 10 порядков по сравнению с предыдущим Цзючжаном. [51] [52] Zuchongzhi — это программируемый сверхпроводящий квантовый компьютер, который для эффективной работы необходимо хранить при чрезвычайно низких температурах и использует случайную выборку схемы для получения 56 кубитов из настраиваемой архитектуры связи из 66 трансмонов — улучшение по сравнению с достижением Google Sycamore 2019 года. на 3 кубита, что означает увеличение вычислительных затрат классического моделирования на 2–3 порядка. [53] [54] [55] В третьем исследовании сообщалось, что Zuchongzhi 2.1 выполнил задачу выборки, которая «примерно на 6 порядков сложнее, чем задача Sycamore» «в классической симуляции». [56]

В июне 2022 года Занаду сообщил об эксперименте по выборке бозонов, суммирующем эксперименты Google и USTC. В их установке использовались петли оптического волокна и мультиплексирование для замены сети светоделителей на одну, что также облегчило ее реконфигурацию. Они обнаружили в среднем от 125 до 219 фотонов из 216 сжатых мод (сжатый свет следует распределению числа фотонов, поэтому они могут содержать более одного фотона на моду) и утверждают, что получили ускорение в 50 миллионов раз больше, чем в предыдущих экспериментах. [57] [58]

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

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

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

Трудность доказать, что невозможно сделать с помощью классических вычислений, является распространенной проблемой при окончательной демонстрации квантового превосходства. В отличие от проблем принятия решений, которые требуют ответа «да» или «нет», задачи выборки требуют выборки из вероятностных распределений . [64] Если существует классический алгоритм , который может эффективно осуществлять выборку из выходных данных произвольной квантовой схемы , полиномиальная иерархия рухнет на третий уровень, что обычно считается очень маловероятным. [10] [11] Выборка бозонов — это более конкретное предложение, классическая сложность которого зависит от сложности вычисления перманента большой матрицы со сложными элементами, что является #P-полной проблемой. [65] Аргументы, использованные для достижения этого вывода, были распространены на выборку IQP, [66] где необходима только гипотеза о том, что средняя и наихудшая сложности задачи одинаковы, [64] , а также на случайную выборку. Выборка цепей [11] — задача, которую повторили исследовательские группы Google [38] и USTC. [48]

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

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

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

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

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

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

Выборка бозонов

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

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

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

Самый известный алгоритм моделирования произвольной случайной квантовой схемы требует определенного количества времени, которое экспоненциально масштабируется с количеством кубитов , что привело одну группу к выводу, что около 50 кубитов может быть достаточно, чтобы продемонстрировать квантовое превосходство. [33] Буланд, Фефферман, Нирхе и Вазирани [11] в 2018 году представили теоретические доказательства того, что эффективное моделирование случайной квантовой схемы потребует коллапса вычислительной полиномиальной иерархии . Google объявила о своем намерении продемонстрировать квантовое превосходство к концу 2017 года, создав и запустив 49-кубитный чип, который сможет за разумное время производить выборку дистрибутивов, недоступных любым современным классическим компьютерам. [29] Крупнейший универсальный симулятор квантовых схем, работавший на классических суперкомпьютерах того времени, был способен моделировать 48 кубитов. [78] Но для определенных типов схем возможны более крупные модели квантовых схем с 56 кубитами. [79] Это может потребовать увеличения количества кубитов, чтобы продемонстрировать квантовое превосходство. [31] 23 октября 2019 года компания Google опубликовала результаты этого эксперимента по квантовому превосходству в статье в журнале Nature «Квантовое превосходство с использованием программируемого сверхпроводящего процессора», в которой они разработали новый 53-кубитный процессор под названием «Сикамор», то есть способен использовать быстрые и высокоточные квантовые логические элементы для проведения эталонного тестирования. Google утверждает, что их машина выполнила целевые вычисления за 200 секунд, и подсчитала, что их классическому алгоритму потребуется 10 000 лет на самом быстром в мире суперкомпьютере, чтобы решить ту же задачу. [80] IBM оспорила это утверждение, заявив, что улучшенный классический алгоритм сможет решить эту проблему за два с половиной дня на том же суперкомпьютере. [81] [82] [83]

Критика

Подверженность ошибкам

Квантовые компьютеры гораздо более восприимчивы к ошибкам, чем классические компьютеры, из-за декогеренции и шума . [84] Пороговая теорема утверждает, что шумный квантовый компьютер может использовать квантовые коды, исправляющие ошибки [85] [86] для моделирования бесшумного квантового компьютера, при условии, что ошибка, вносимая в каждый компьютерный цикл, меньше некоторого числа. [87] Численное моделирование показывает, что это число может достигать 3%. [88] Однако пока точно не известно, как ресурсы, необходимые для исправления ошибок, будут масштабироваться в зависимости от количества кубитов . [89] Скептики указывают на неизвестное поведение шума в увеличенных квантовых системах как на потенциальное препятствие для успешной реализации квантовых вычислений и демонстрации квантового превосходства. [84] [90]

Критика имени

Некоторые исследователи предлагают не использовать термин «квантовое превосходство», утверждая, что слово «превосходство» вызывает неприятные сравнения с расистской верой в превосходство белой расы . В противоречивой комментаторской статье [91] [92] в журнале Nature , подписанной тринадцатью исследователями, утверждается, что вместо этого следует использовать альтернативную фразу «квантовое преимущество». [93] [94] Джон Прескилл , профессор теоретической физики Калифорнийского технологического института , придумавший этот термин, с тех пор пояснил, что этот термин был предложен для явного описания момента, когда квантовый компьютер обретает способность выполнять задачу, которая классический компьютер никогда не мог этого сделать. Далее он пояснил, что специально отверг термин «квантовое преимущество», поскольку он не полностью отражает смысл его нового термина: слово «преимущество» подразумевало бы, что компьютер с квантовым превосходством будет иметь небольшое преимущество над классическим компьютером, в то время как компьютер с квантовым превосходством будет иметь небольшое преимущество перед классическим компьютером. слово «превосходство» лучше передает полное превосходство над любым классическим компьютером.

Термин «квантовое первенство» был придуман в феврале 2021 года в обзорной статье Scientific American как более подходящая замена. [4] Филип Болл из Nature написал в декабре 2020 года, что термин «квантовое преимущество» «в значительной степени заменил» термин «квантовое превосходство». [95]

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

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

  1. ^ аб Прескилл, Джон (26 марта 2012 г.). «Квантовые вычисления и граница запутанности». arXiv : 1203,5813 [квант-ph].
  2. ^ abcd Прескилл, Джон (06 августа 2018 г.). «Квантовые вычисления в эпоху NISQ и за ее пределами». Квантовый . 2 : 79. arXiv : 1801.00862 . Бибкод : 2018Количество...2...79P. doi : 10.22331/кв-2018-08-06-79 .
  3. ^ Аб Чжун, Хан-Сен; Ван, Хуэй; Дэн, Ю-Хао; Чен, Мин-Ченг; Пэн, Ли-Чао; Ло, И-Хан; Цинь, Цзянь; Ву, Диан; Дин, Син; Ху, Йи; Ху, Пэн (03 декабря 2020 г.). «Преимущество квантовых вычислений с использованием фотонов». Наука . 370 (6523): 1460–1463. arXiv : 2012.01625 . Бибкод : 2020Sci...370.1460Z. doi : 10.1126/science.abe8770. ISSN  0036-8075. PMID  33273064. S2CID  227254333.
  4. ^ abc «Джон Прескилл объясняет« квантовое превосходство »». Журнал Кванта . 2 октября 2019 года . Проверено 21 апреля 2020 г.
  5. ^ Манин, Ю. И. (1980). Вычислимое и невычислимое . Сов.Радио. стр. 13–15. Архивировано из оригинала 10 мая 2013 г. Проверено 4 марта 2013 г.
  6. ^ Фейнман, Ричард П. (1982-06-01). «Моделирование физики с помощью компьютеров». Международный журнал теоретической физики . 21 (6–7): 467–488. Бибкод : 1982IJTP...21..467F. CiteSeerX 10.1.1.45.9310 . дои : 10.1007/BF02650179. ISSN  0020-7748. S2CID  124545445. 
  7. ^ аб Харроу, Арам В.; Монтанаро, Эшли (сентябрь 2017 г.). «Квантовое вычислительное превосходство». Природа . 549 (7671): 203–209. arXiv : 1809.07442 . Бибкод : 2017Natur.549..203H. дои : 10.1038/nature23458. ISSN  1476-4687. PMID  28905912. S2CID  2514901.
  8. ^ Папагеоргиу, Анаргирос; Трауб, Джозеф Ф. (12 августа 2013 г.). «Меры ускорения квантовых вычислений». Физический обзор А. 88 (2): 022316. arXiv : 1307.7488 . Бибкод : 2013PhRvA..88b2316P. doi : 10.1103/PhysRevA.88.022316. ISSN  1050-2947. S2CID  41867048.
  9. ^ аб Ааронсон, Скотт; Архипов, Алексей (2011). «Вычислительная сложность линейной оптики». Материалы сорок третьего ежегодного симпозиума ACM по теории вычислений . СТОК '11. Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 333–342. arXiv : 1011.3245 . дои : 10.1145/1993636.1993682. ISBN 9781450306911. S2CID  681637.
  10. ^ аб Ааронсон, Скотт; Чен, Лицзе (18 декабря 2016 г.). «Теоретико-сложные основы экспериментов по квантовому превосходству». arXiv : 1612.05903 [квант-ph].
  11. ^ abcd Буланд, Адам; Фефферман, Билл; Нирхе, Чинмей; Вазирани, Умеш (29 октября 2018 г.). «О сложности и проверке квантовой случайной выборки цепей». Физика природы . 15 (2): 159–163. arXiv : 1803.04402 . дои : 10.1038/s41567-018-0318-2. ISSN  1745-2473. S2CID  125264133.
  12. ^ Ханглейтер, Доминик; Эйсерт, Йенс (20 июля 2023 г.). «Вычислительное преимущество квантовой случайной выборки». Обзоры современной физики . 95 (3): 035001. arXiv : 2206.04079 . Бибкод : 2023RvMP...95c5001H. doi : 10.1103/RevModPhys.95.035001. S2CID  249538723.
  13. ^ Мец, Кейд (23 октября 2019 г.). «Google заявляет о квантовом прорыве, который может изменить компьютерные технологии (опубликовано в 2019 г.)». Нью-Йорк Таймс . ISSN  0362-4331 . Проверено 7 декабря 2020 г.
  14. ^ Ааронсон, Скотт (30 октября 2019 г.). «Мнение | Почему важна веха Google в области квантового превосходства (опубликовано в 2019 г.)» . Нью-Йорк Таймс . ISSN  0362-4331 . Проверено 7 декабря 2020 г.
  15. ^ ab «О «квантовом превосходстве»». Блог исследований IBM . 22 октября 2019 г. Проверено 24 октября 2019 г.
  16. ^ Крейн, Лия. «IBM говорит, что Google, возможно, все-таки не достиг квантового превосходства». Новый учёный . Проверено 7 декабря 2020 г.
  17. ^ Тьюринг, Алан (1936). О вычислимых числах с применением к проблеме Entscheidungs .
  18. ^ Бениофф, Пол (1 мая 1980 г.). «Компьютер как физическая система: микроскопическая квантовомеханическая гамильтонова модель компьютеров, представленная машинами Тьюринга». Журнал статистической физики . 22 (5): 563–591. Бибкод : 1980JSP....22..563B. дои : 10.1007/BF01011339. ISSN  1572-9613. S2CID  122949592.
  19. ^ аб Фейнман, Ричард П. (1982-06-01). «Моделирование физики с помощью компьютеров». Международный журнал теоретической физики . 21 (6): 467–488. Бибкод : 1982IJTP...21..467F. дои : 10.1007/BF02650179. ISSN  1572-9575. S2CID  124545445.
  20. ^ «Квантовые вычисления». Стэнфордская энциклопедия философии . 30 сентября 2019 г.
  21. ^ Шор, Питер (1996). Алгоритмы полиномиального времени для факторизации простых чисел и дискретных логарифмов на квантовом компьютере .
  22. ^ Монро, К.; Микхоф, DM; Король, БЭ; Итано, ВМ; Вайнленд, диджей (18 декабря 1995 г.). «Демонстрация фундаментального квантового логического элемента». Письма о физических обзорах . 75 (25): 4714–4717. Бибкод : 1995PhRvL..75.4714M. doi : 10.1103/PhysRevLett.75.4714 . ISSN  0031-9007. ПМИД  10059979.
  23. ^ Гровер, Лов К. (19 ноября 1996 г.). «Быстрый квантовомеханический алгоритм поиска в базе данных». arXiv : Quant-ph/9605043 .
  24. ^ Джонс, Дж.А.; Моска, М. (август 1998 г.). «Реализация квантового алгоритма для решения проблемы Дойча на квантовом компьютере ядерного магнитного резонанса». Журнал химической физики . 109 (5): 1648–1653. arXiv : Quant-ph/9801027 . дои : 10.1063/1.476739. ISSN  0021-9606. S2CID  19348964.
  25. ^ Балаганур, Самир (20 ноября 2019 г.). «Человеческая гонка к квантовому превосходству: полная хронология». Журнал Analytics India . Проверено 16 ноября 2020 г.
  26. ^ Мерали, Зия (июнь 2011 г.). «Первая продажа квантовых вычислений». Природа . 474 (7349): 18. Бибкод :2011Natur.474...18M. дои : 10.1038/474018a . ISSN  0028-0836. PMID  21637232. S2CID  4425833.
  27. ↑ Баттерсби, Стивен (13 апреля 2012 г.). «Спорный квантовый компьютер побил рекорд факторинга». Новый учёный . Проверено 16 ноября 2020 г.
  28. ^ Харди, Квентин (16 мая 2013 г.). «Google покупает квантовый компьютер». Блог Битс . Проверено 16 ноября 2020 г.
  29. ^ Аб Кортленд, Рэйчел (24 мая 2017 г.). «Google планирует продемонстрировать превосходство квантовых вычислений». IEEE-спектр . Проверено 11 января 2018 г.
  30. ↑ Сюй, Джереми (8 января 2018 г.). «CES 2018: 49-кубитный чип Intel стремится к квантовому превосходству». IEEE-спектр . Проверено 22 июля 2017 г.
  31. ↑ Аб Ким, Марк (20 октября 2017 г.). «Планам Google по квантовым вычислениям угрожает кривая IBM» . Новый учёный . Проверено 22 октября 2017 г.
  32. ↑ Харрис, Марк (5 ноября 2018 г.). «Google привлек НАСА, чтобы помочь ему доказать квантовое превосходство в течение нескольких месяцев». Обзор технологий Массачусетского технологического института . Проверено 30 ноября 2018 г.
  33. ^ аб Бойшо, Серхио; Исаков Сергей В.; Смелянский Вадим Н.; Бэббуш, Райан; Дин, Нэн; Цзян, Чжан; Бремнер, Майкл Дж.; Мартинис, Джон М.; Невен, Хартмут (23 апреля 2018 г.). «Характеристика квантового превосходства в устройствах ближайшего будущего». Физика природы . 14 (6): 595–600. arXiv : 1608.00263 . Бибкод : 2018NatPh..14..595B. дои : 10.1038/s41567-018-0124-x. S2CID  4167494.
  34. ↑ Хартнетт, Кевин (18 июня 2019 г.). «Новый закон, описывающий рост квантовых вычислений?». Журнал Кванта .
  35. ^ [1], Работа в области квантовых вычислений: открывая будущее технологий, январь 2024 г.
  36. ^ «Почему квантовые вычисления полезны для решения задач оптимизации?». Новизин . Ассошиэйтед Пресс.
  37. ^ «Демонстрация квантового превосходства» - через www.youtube.com.
  38. ^ ab «Квантовое превосходство с использованием программируемого сверхпроводящего процессора».
  39. ^ Аруте, Фрэнк; и другие. (23 октября 2019 г.). «Квантовое превосходство с использованием программируемого сверхпроводникового процессора». Природа . 574 (7779): 505–510. arXiv : 1910.11333 . Бибкод : 2019Natur.574..505A. дои : 10.1038/s41586-019-1666-5 . ПМИД  31645734.
  40. ^ «Что означают дебаты Google против IBM по поводу квантового превосходства | ZDNet» . www.zdnet.com .
  41. ↑ Зиальчита, Паоло (23 октября 2019 г.). «Google претендует на достижение квантового превосходства — IBM сопротивляется». ЭНЕРГЕТИЧЕСКИЙ ЯДЕРНЫЙ РЕАКТОР . Проверено 24 октября 2019 г.
  42. ^ Лю, Юн (Александр); Лю, Синь (Люси); Ли, Фанг (Нэнси); Фу, Хаохуань; Ян, Юлин; Сун, Цзявэй; Чжао, Пэнпэн; Ван, Чжэнь; Пэн, Дацзя; Чен, Хуаронг; Го, Чу (14 ноября 2021 г.). «Закрытие разрыва в «квантовом превосходстве»». Материалы Международной конференции по высокопроизводительным вычислениям, сетям, хранению и анализу . СК '21. Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 1–12. arXiv : 2110.14502 . дои : 10.1145/3458817.3487399. ISBN 978-1-4503-8442-1. S2CID  239036985.
  43. ^ Балмер, Джейкоб Ф.Ф.; Белл, Брин А.; Чедвик, Рэйчел С.; Джонс, Алекс Э.; Мойзе, Диана; Ригацци, Алессандро; Торбек, Ян; Хаус, Утц-Уве; Ван Веренберг, Томас; Патель, Радж Б.; Уолмсли, Ян А. (28 января 2022 г.). «Граница квантового преимущества при выборке гауссовских бозонов». Достижения науки . 8 (4): eabl9236. arXiv : 2108.01622 . Бибкод : 2022SciA....8.9236B. doi : 10.1126/sciadv.abl9236. ISSN  2375-2548. ПМЦ 8791606 . ПМИД  35080972. 
  44. ^ Маккормик, Кэти (10 февраля 2022 г.). «Гонка между классическими и квантовыми компьютерами еще не окончена». Физика . 15 : 19. Бибкод :2022PhyOJ..15...19M. дои : 10.1103/Физика.15.19 . S2CID  246910085.
  45. ^ Пан, Фэн; Чен, Кейанг; Чжан, Пан (2022). «Решение проблемы выборки квантовых схем платана». Письма о физических обзорах . 129 (9): 090502. arXiv : 2111.03011 . Бибкод : 2022PhRvL.129i0502P. doi : 10.1103/PhysRevLett.129.090502. PMID  36083655. S2CID  251755796.
  46. ^ «В конце концов, обычные компьютеры могут победить квантовый компьютер Google» . 02.08.2022. дои : 10.1126/science.ade2364. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
  47. ^ «Квантовое превосходство Google узурпировано исследователями, использующими обычный суперкомпьютер» . ТехКранч . Проверено 7 августа 2022 г.
  48. ^ Аб Болл, Филип (03 декабря 2020 г.). «Физики в Китае бросают вызов «квантовому преимуществу» Google»". Nature . 588 (7838): 380. Бибкод : 2020Natur.588..380B. doi : 10.1038/d41586-020-03434-7. PMID  33273711.
  49. ↑ Гаристо, Дэниел (3 декабря 2020 г.). «Квантовый компьютер на основе света превосходит самые быстрые классические суперкомпьютеры». Научный американец . Проверено 7 декабря 2020 г.
  50. ^ Коновер, Эмили (03 декабря 2020 г.). «Новый квантовый компьютер Цзючжан на основе света достиг квантового превосходства». Новости науки . Проверено 7 декабря 2020 г.
  51. ^ Чжун, Хан-Сен; Дэн, Ю-Хао; Цинь, Цзянь; Ван, Хуэй; Чен, Мин-Ченг; Пэн, Ли-Чао; Ло, И-Хан; Ву, Диан; Гонг, Си-Цю; Су, Хао; Ху, И (25 октября 2021 г.). «Программируемая по фазе выборка гауссовских бозонов с использованием стимулированного сжатого света». Письма о физических отзывах . 127 (18): 180502. arXiv : 2106.15534 . Бибкод : 2021PhRvL.127r0502Z. doi : 10.1103/PhysRevLett.127.180502. PMID  34767431. S2CID  235669908.
  52. ↑ Джонстон, Хэмиш (26 октября 2021 г.). «Квантовое преимущество совершает гигантский скачок в оптических и сверхпроводящих системах». Мир физики . Проверено 27 октября 2021 г.
  53. ^ Ву, Юлин; Бао, Ван-Су; Цао, Сируи; Чен, Фушенг; Чен, Мин-Ченг; Чен, Сявэй; Чунг, Дун-Сюнь; Дэн, Хуэй; Ду, Яцзе; Фан, Даоджин; Гонг, Мин (25 октября 2021 г.). «Сильное преимущество квантовых вычислений с использованием сверхпроводящего квантового процессора». Письма о физических обзорах . 127 (18): 180501. arXiv : 2106.14734 . Бибкод : 2021PhRvL.127r0501W. doi : 10.1103/PhysRevLett.127.180501. PMID  34767433. S2CID  235658633.
  54. ^ Чжун, Хан-Сен; Дэн, Ю-Хао; Цинь, Цзянь; Ван, Хуэй; Чен, Мин-Ченг; Пэн, Ли-Чао; Ло, И-Хан; Ву, Диан; Гонг, Си-Цю; Су, Хао; Ху, Йи; Ху, Пэн; Ян, Сяо-Янь; Чжан, Вэй-Цзюнь; Ли, Хао; Ли, Юйсюань; Цзян, Сяо; Ган, Лин; Ян, Гуанвэнь; Ты, Ликсинг; Ван, Чжэнь; Ли, Ли; Лю, Най-Ле; Ренема, Джелмер Дж.; Лу, Чао-Ян; Пан, Цзянь-Вэй (25 октября 2021 г.). «Программируемая по фазе выборка гауссовских бозонов с использованием стимулированного сжатого света». Письма о физических обзорах . 127 (18): 180502. arXiv : 2106.15534 . Бибкод : 2021PhRvL.127r0502Z. doi : 10.1103/PhysRevLett.127.180502. PMID  34767431. S2CID  235669908.
  55. ^ Сандерс, Барри К. (25 октября 2021 г.). «Квантовый скачок к квантовому первенству». Физика . 14 : 147. Бибкод : 2021PhyOJ..14..147S. дои : 10.1103/Физика.14.147 . S2CID  244826882.
  56. ^ Цинлин Чжу, Сируи Цао; и другие. (25 октября 2021 г.). «Преимущество квантовых вычислений за счет 60-кубитной 24-цикловой случайной выборки схемы». Научный вестник . 67 (3): 240–245. arXiv : 2109.03494 . дои : 10.1016/j.scib.2021.10.017. ISSN  2095-9273. PMID  36546072. S2CID  237442167.
  57. ↑ Брод, Дэниел Йост (1 июня 2022 г.). «Петли упрощают настройку и увеличивают преимущество квантовых вычислений». Природа . 606 (7912): 31–32. Бибкод : 2022Natur.606...31B. дои : 10.1038/d41586-022-01402-x. PMID  35650360. S2CID  249277681.
  58. ^ Мэдсен, Ларс С.; Лауденбах, Фабиан; Аскарани, Мохсен Фаламарзи; Рортэ, Фабьен; Винсент, Тревор; Балмер, Джейкоб Ф.Ф.; Миатто, Филиппо М.; Нойгауз, Леонард; Хелт, Лукас Г.; Коллинз, Мэтью Дж.; Лита, Адриана Э. (1 июня 2022 г.). «Квантовое вычислительное преимущество с программируемым фотонным процессором». Природа . 606 (7912): 75–81. Бибкод : 2022Natur.606...75M. дои : 10.1038/s41586-022-04725-x. ISSN  1476-4687. ПМЦ 9159949 . ПМИД  35650354. 
  59. ^ Клив, Ричард (2000). «Введение в квантовую теорию сложности» (PDF) . ЦЕРН . Бибкод : 2000qcqi.book..103C.
  60. ^ аб Уотрус, Джон (2009). «Квантовая вычислительная сложность». В Мейерсе, Роберт А. (ред.). Энциклопедия сложности и системных наук . Спрингер Нью-Йорк. стр. 7174–7201. дои : 10.1007/978-0-387-30440-3_428. ISBN 9780387758886. S2CID  1380135.
  61. ↑ ab Watrous, Джон (21 апреля 2018 г.). «Квантовая вычислительная сложность». arXiv : 0804.3401 [квант-ph].
  62. ^ Тереза, Тусарова (26 сентября 2004 г.). «Квантовые классы сложности». arXiv : cs/0409051 .
  63. ^ Тусарова, Тереза ​​(2004). «Квантовые классы сложности». arXiv : cs/0409051 .
  64. ^ Аб Лунд, AP; Бремнер, Майкл Дж.; Ральф, TC (13 апреля 2017 г.). «Проблемы квантовой выборки, BosonSampling и квантовое превосходство». npj Квантовая информация . 3 (1): 15. arXiv : 1702.03061 . Бибкод : 2017npjQI...3...15L. дои : 10.1038/s41534-017-0018-2. ISSN  2056-6387. S2CID  54628108.
  65. ^ Гард, Брайан Т.; Моутс, Кейт Р.; Олсон, Джонатан П.; Роде, Питер П.; Даулинг, Джонатан П. (август 2015 г.). «Введение в отбор бозонов». От атомарного к мезомасштабному: роль квантовой когерентности в системах различной сложности . Всемирная научная. стр. 167–192. arXiv : 1406.6767 . дои : 10.1142/9789814678704_0008. ISBN 978-981-4678-70-4. S2CID  55999387.
  66. ^ Бремнер, Майкл Дж.; Монтанаро, Эшли; Шеперд, Дэн Дж. (18 августа 2016 г.). «Средняя сложность по сравнению с приближенным моделированием коммутирующих квантовых вычислений». Письма о физических обзорах . 117 (8): 080501. arXiv : 1504.07999 . Бибкод : 2016PhRvL.117h0501B. doi : 10.1103/PhysRevLett.117.080501. ISSN  0031-9007. PMID  27588839. S2CID  8590553.
  67. ^ Джордан, Стивен. «Зоопарк квантовых алгоритмов». math.nist.gov . Архивировано из оригинала 29 апреля 2018 г. Проверено 29 июля 2017 г.
  68. ^ Аб Шор, П. (1 января 1999 г.). «Алгоритмы полиномиального времени для простой факторизации и дискретных логарифмов на квантовом компьютере». Обзор СИАМ . 41 (2): 303–332. arXiv : Quant-ph/9508027 . Бибкод : 1999SIAMR..41..303S. дои : 10.1137/S0036144598347011. ISSN  0036-1445.
  69. ^ Рубинштейн, Майкл (19 октября 2006 г.). «Распределение решений задачи xy = N mod a с применением факторизации целых чисел». arXiv : математика/0610612 .
  70. ^ Бабай, Ласло; Билз, Роберт; Сересс, Акос (2009). «Полиномиальная теория матричных групп». Материалы сорок первого ежегодного симпозиума ACM по теории вычислений . СТОК '09. Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 55–64. CiteSeerX 10.1.1.674.9429 . дои : 10.1145/1536414.1536425. ISBN  9781605585062. S2CID  9052772.
  71. ^ Ривест, РЛ; Шамир, А.; Адлеман, Л. (февраль 1978 г.). «Метод получения цифровых подписей и криптосистемы с открытым ключом». Коммун. АКМ . 21 (2): 120–126. CiteSeerX 10.1.1.607.2677 . дои : 10.1145/359340.359342. ISSN  0001-0782. S2CID  2873616. 
  72. ^ Мартин-Лопес, Энрике; Лэнг, Энтони; Лоусон, Томас; Альварес, Роберто; Чжоу, Сяо-Ци; О'Брайен, Джереми Л. (ноябрь 2012 г.). «Экспериментальная реализация алгоритма квантового факторинга Шора с использованием переработки кубитов». Природная фотоника . 6 (11): 773–776. arXiv : 1111.4147 . Бибкод : 2012NaPho...6..773M. дои : 10.1038/nphoton.2012.259. ISSN  1749-4893. S2CID  46546101.
  73. ^ Фаулер, Остин Г.; Мариантони, Маттео; Мартинис, Джон М.; Клеланд, Эндрю Н. (18 сентября 2012 г.). «Поверхностные коды: на пути к практическим крупномасштабным квантовым вычислениям». Физический обзор А. 86 (3): 032324. arXiv : 1208.0928 . Бибкод : 2012PhRvA..86c2324F. doi : 10.1103/PhysRevA.86.032324. S2CID  119277773.
  74. ^ Рахими-Кешари, Салех; Ральф, Тимоти К.; Кейвс, Карлтон М. (20 июня 2016 г.). «Достаточные условия для эффективного классического моделирования квантовой оптики». Физический обзор X . 6 (2): 021039. arXiv : 1511.06526 . Бибкод : 2016PhRvX...6b1039R. doi : 10.1103/PhysRevX.6.021039. S2CID  23490704.
  75. ^ Кэролан, Жак; Харрольд, Кристофер; Воробей, Крис; Мартин-Лопес, Энрике; Рассел, Николас Дж.; Сильверстоун, Джошуа В.; Шедболт, Питер Дж.; Мацуда, Нобуюки; Огума, Манабу (14 августа 2015 г.). «Универсальная линейная оптика». Наука . 349 (6249): 711–716. arXiv : 1505.01182 . doi : 10.1126/science.aab3642. ISSN  0036-8075. PMID  26160375. S2CID  19067232.
  76. ^ аб Клиффорд, Питер; Клиффорд, Рафаэль (5 июня 2017 г.). «Классическая сложность отбора бозонов». arXiv : 1706.01260 [cs.DS].
  77. ^ аб Невилл, Алекс; Воробей, Крис; Клиффорд, Рафаэль; Джонстон, Эрик; Бирчалл, Патрик М.; Монтанаро, Эшли; Лэнг, Энтони (2 октября 2017 г.). «Нет неизбежного квантового превосходства путем выборки бозонов». Физика природы . 13 (12): 1153–1157. arXiv : 1705.00686 . Бибкод : 2017arXiv170500686N. дои : 10.1038/nphys4270. ISSN  1745-2473. S2CID  73635825.
  78. ^ Ханс Де Раедт; Фэнпин Цзинь; Деннис Уиллш; Мадита Вильш; Наоки Ёсиока; Нобуясу Ито; Шэнцзюнь Юань; Кристель Михильсен (ноябрь 2018 г.). «Массово-параллельный квантовый компьютерный симулятор, одиннадцать лет спустя». Компьютерная физика. Коммуникации . 237 : 47–61. arXiv : 1805.04708 . дои : 10.1016/j.cpc.2018.11.005 .
  79. ^ Эдвин Педно; Джон А. Ганнелс; Джакомо Нанничини; Лиор Хореш; Томас Магерлейн; Эдгар Соломоник; Роберт Висниефф (октябрь 2017 г.). «Преодоление барьера в 49 кубитов при моделировании квантовых схем». arXiv : 1710.05867 [квант-ph].
  80. ^ «Квантовое превосходство с использованием программируемого сверхпроводящего процессора». Блог Google AI . Проверено 2 ноября 2019 г.
  81. ↑ Мец, Кейд (23 октября 2019 г.). «Google заявляет о квантовом прорыве, который может изменить компьютерные технологии». Нью-Йорк Таймс . Проверено 14 января 2020 г. .
  82. ^ Эдвин Педно; Джон Ганнелс; Джакомо Нанничини; Лиор Хореш; Роберт Висниефф (октябрь 2019 г.). «Использование вторичной памяти для моделирования глубоких 54-кубитных платовых схем». arXiv : 1910.09534 [квант-ph].
  83. ^ «Столкновение Google и IBM по поводу заявления о квантовом превосходстве» . Журнал Кванта . 23 октября 2019 г. Проверено 29 октября 2020 г.
  84. ^ Аб Калаи, Гил (2 июня 2011 г.). «Как терпят неудачу квантовые компьютеры: квантовые коды, корреляции в физических системах и накопление шума». arXiv : 1106.0485 [квант-ph].
  85. ^ Шор, Питер В. (1 октября 1995 г.). «Схема уменьшения декогеренции в памяти квантового компьютера». Физический обзор А. 52 (4): R2493–R2496. Бибкод : 1995PhRvA..52.2493S. doi :10.1103/PhysRevA.52.R2493. ПМИД  9912632.
  86. ^ Стейн, AM (29 июля 1996 г.). «Коды, исправляющие ошибки в квантовой теории». Письма о физических отзывах . 77 (5): 793–797. Бибкод : 1996PhRvL..77..793S. doi : 10.1103/PhysRevLett.77.793. ПМИД  10062908.
  87. ^ Ааронов, Дорит; Бен-Ор, Майкл (30 июня 1999 г.). «Отказоустойчивые квантовые вычисления с постоянной частотой ошибок». arXiv : Quant-ph/9906129 .
  88. ^ Нилл, Э. (3 марта 2005 г.). «Квантовые вычисления с реально шумными устройствами». Природа . 434 (7029): 39–44. arXiv : Quant-ph/0410199 . Бибкод : 2005Natur.434...39K. дои : 10.1038/nature03350. ISSN  0028-0836. PMID  15744292. S2CID  4420858.
  89. ^ Калаи, Гил (3 мая 2016 г.). «Загадка квантового компьютера (расширенная версия)». arXiv : 1605.00992 [квант-ph].
  90. ^ Дьяконов, М.И. (2007). «Действительно ли возможны отказоустойчивые квантовые вычисления?». В Лурый, С.; Сюй, Дж.; Заславский А. (ред.). Будущие тенденции в микроэлектронике. Вверх по ручью Нано . Уайли. стр. 4–18. arXiv : Quant-ph/0610117 . Бибкод : 2006quant.ph.10117D.
  91. ↑ Совет, редакция (17 декабря 2019 г.). «Мнение | Достижение квантового пробуждения». Уолл Стрит Джорнал . Проверено 21 декабря 2019 г.
  92. ^ Кнаптон, Сара (17 декабря 2019 г.). «Ученых высмеивают за то, что они утверждают, что «квантовое превосходство» — это расистский и колониалистский термин». Телеграф . ISSN  0307-1235 . Проверено 21 декабря 2019 г.
  93. ^ Паласиос-Берракеро, Кармен; Муек, Леони; Персо, Дивья М. (10 декабря 2019 г.). «Вместо превосходства используйте квантовое преимущество». Природа . 576 (7786): 213. дои : 10.1038/d41586-019-03781-0 . ПМИД  31822842.
  94. ^ «Открытое письмо - Ответственность в квантовой науке».
  95. ↑ Болл, Филип (17 декабря 2020 г.). «Физики в Китае бросают вызов «квантовому преимуществу» Google». Природа . 588 (7838): 380. Бибкод : 2020Natur.588..380B. дои : 10.1038/d41586-020-03434-7. PMID  33273711. S2CID  227282052 . Проверено 16 декабря 2020 г.