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 объявила о партнерстве с NASA , которое «проанализирует результаты квантовых схем, запущенных на квантовых процессорах 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 порядков по сравнению с предыдущим Jiuzhang. [51] [52] Zuchongzhi — это программируемый сверхпроводящий квантовый компьютер, который необходимо поддерживать при чрезвычайно низких температурах для эффективной работы и который использует случайную выборку схемы для получения 56 кубитов из настраиваемой архитектуры связи из 66 трансмонов — улучшение по сравнению с достижением Google Sycamore 2019 на 3 кубита, что означает большую вычислительную стоимость классического моделирования на 2–3 порядка. [53] [54] [55] Третье исследование сообщило, что Zuchongzhi 2.1 выполнил задачу выборки, которая «примерно на 6 порядков сложнее, чем у Sycamore» «в классическом моделировании». [56]

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

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

Сложность вычислений

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

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

Трудность доказательства того, что не может быть сделано с помощью классических вычислений, является распространенной проблемой при окончательной демонстрации квантового превосходства. В отличие от задач принятия решений, требующих ответов «да» или «нет», задачи выборки требуют выборок из распределений вероятностей . [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-кубитный процессор под названием «Sycamore», способный выполнять быстрые, высокоточные квантовые логические вентили , для проведения эталонного тестирования. Google утверждает, что их машина выполнила целевое вычисление за 200 секунд, и подсчитала, что их классический алгоритм займет 10 000 лет в самом быстром в мире суперкомпьютере, чтобы решить ту же задачу. [80] IBM оспорила это утверждение, заявив, что улучшенный классический алгоритм должен быть в состоянии решить эту задачу за два с половиной дня на том же суперкомпьютере. [81] [82] [83]

Критика

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

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

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

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

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

Ссылки

  1. ^ ab Прескилл, Джон (2012-03-26). «Квантовые вычисления и граница запутанности». arXiv : 1203.5813 [quant-ph].
  2. ^ abcd Прескилл, Джон (2018-08-06). «Квантовые вычисления в эпоху NISQ и далее». Quantum . 2 : 79. arXiv : 1801.00862 . Bibcode :2018Quant...2...79P. doi : 10.22331/q-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 "Джон Прескилл объясняет „квантовое превосходство“". Журнал Quanta . 2 октября 2019 г. Получено 21 апреля 2020 г.
  5. ↑ Манин, Ю. И. (1980). Вычислимое и невычислимое [ Computable and Noncomputable ] (на русском языке). Сов. Радио. С. 13–15. Архивировано из оригинала 2013-05-10 . Получено 2013-03-04 .
  6. ^ Фейнман, Ричард П. (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. 
  7. ^ ab Harrow, Aram W.; Montanaro, Ashley (сентябрь 2017 г.). «Квантовое вычислительное превосходство». Nature . 549 (7671): 203–209. arXiv : 1809.07442 . Bibcode :2017Natur.549..203H. doi :10.1038/nature23458. ISSN  1476-4687. PMID  28905912. S2CID  2514901.
  8. ^ Папагеоргиу, Анаргирос; Трауб, Джозеф Ф. (2013-08-12). «Меры ускорения квантовых вычислений». Physical Review A. 88 ( 2): 022316. arXiv : 1307.7488 . Bibcode : 2013PhRvA..88b2316P. doi : 10.1103/PhysRevA.88.022316. ISSN  1050-2947. S2CID  41867048.
  9. ^ ab Ааронсон, Скотт; Архипов, Алекс (2011). «Вычислительная сложность линейной оптики». Труды сорок третьего ежегодного симпозиума ACM по теории вычислений . STOC '11. Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 333–342. arXiv : 1011.3245 . doi :10.1145/1993636.1993682. ISBN 9781450306911. S2CID  681637.
  10. ^ ab Ааронсон, Скотт; Чен, Лицзе (2016-12-18). «Основы теории сложности экспериментов по квантовому превосходству». arXiv : 1612.05903 [quant-ph].
  11. ^ abcd Буланд, Адам; Фефферман, Билл; Нирке, Чинмей; Вазирани, Умеш (29.10.2018). «О сложности и проверке квантовой случайной выборки цепей». Nature Physics . 15 (2): 159–163. arXiv : 1803.04402 . doi :10.1038/s41567-018-0318-2. ISSN  1745-2473. S2CID  125264133.
  12. ^ Хангляйтер, Доминик; Эйсерт, Йенс (2023-07-20). «Вычислительное преимущество квантовой случайной выборки». Reviews of Modern Physics . 95 (3): 035001. arXiv : 2206.04079 . Bibcode : 2023RvMP...95c5001H. doi : 10.1103/RevModPhys.95.035001. S2CID  249538723.
  13. ^ Метц, Кейд (2019-10-23). ​​«Google заявляет о квантовом прорыве, который может изменить вычисления (опубликовано в 2019 году)». The New York Times . ISSN  0362-4331 . Получено 2020-12-07 .
  14. ^ Ааронсон, Скотт (2019-10-30). «Мнение | Почему важен этап квантового превосходства Google (опубликовано в 2019 году)». The New York Times . ISSN  0362-4331 . Получено 2020-12-07 .
  15. ^ ab "О "квантовом превосходстве"". Блог исследований IBM . 2019-10-22 . Получено 2019-10-24 .
  16. ^ Крейн, Лия. «IBM заявляет, что Google, возможно, так и не достиг квантового превосходства». New Scientist . Получено 2020-12-07 .
  17. ^ Тьюринг, Алан (1936). О вычислимых числах с приложением к проблеме Entscheidungsproblem .
  18. ^ Бениофф, Пол (1980-05-01). «Компьютер как физическая система: микроскопическая квантово-механическая гамильтонова модель компьютеров, представленная машинами Тьюринга». Журнал статистической физики . 22 (5): 563–591. Bibcode : 1980JSP....22..563B. doi : 10.1007/BF01011339. ISSN  1572-9613. S2CID  122949592.
  19. ^ ab Feynman, Richard P. (1982-06-01). «Моделирование физики с помощью компьютеров». International Journal of Theoretical Physics . 21 (6): 467–488. Bibcode :1982IJTP...21..467F. doi :10.1007/BF02650179. ISSN  1572-9575. S2CID  124545445.
  20. ^ «Квантовые вычисления». Стэнфордская энциклопедия философии . 30 сентября 2019 г.
  21. ^ Шор, Питер (1996). Полиномиальные алгоритмы разложения на простые множители и дискретные логарифмы на квантовом компьютере .
  22. ^ Монро, К.; Микхоф, Д.М.; Кинг, Б.Э.; Итано, В.М.; Уайнленд, Д.Дж. (1995-12-18). «Демонстрация фундаментального квантового логического вентиля». Physical Review Letters . 75 (25): 4714–4717. Bibcode : 1995PhRvL..75.4714M. doi : 10.1103/PhysRevLett.75.4714 . ISSN  0031-9007. PMID  10059979.
  23. ^ Гровер, Лов К. (1996-11-19). "Быстрый квантово-механический алгоритм поиска в базе данных". arXiv : quant-ph/9605043 .
  24. ^ Джонс, JA; Моска, M. (август 1998 г.). «Реализация квантового алгоритма для решения проблемы Дойча на квантовом компьютере ядерного магнитного резонанса». Журнал химической физики . 109 (5): 1648–1653. arXiv : quant-ph/9801027 . doi : 10.1063/1.476739. ISSN  0021-9606. S2CID  19348964.
  25. ^ Балаганур, Самир (2019-11-20). «Гонка человека к квантовому превосходству: полная хронология». Журнал Analytics India . Получено 16.11.2020 .
  26. ^ Merali, Zeeya (июнь 2011 г.). «Первая продажа квантовых вычислений». Nature . 474 (7349): 18. Bibcode :2011Natur.474...18M. doi : 10.1038/474018a . ISSN  0028-0836. PMID  21637232. S2CID  4425833.
  27. ^ Баттерсби, Стивен (13 апреля 2012 г.). «Противоречивый квантовый компьютер бьет рекорд факторизации». New Scientist . Получено 16.11.2020 .
  28. ^ Харди, Квентин (2013-05-16). «Google покупает квантовый компьютер». Блог Bits . Получено 2020-11-16 .
  29. ^ ab Courtland, Rachel (24 мая 2017 г.). «Google планирует продемонстрировать превосходство квантовых вычислений». IEEE Spectrum . Получено 11.01.2018 .
  30. ^ Хсу, Джереми (8 января 2018 г.). «CES 2018: 49-кубитный чип Intel стремится к квантовому превосходству». IEEE Spectrum . Получено 22 июля 2017 г.
  31. ^ ab Kim, Mark (20 октября 2017 г.). «Планы квантовых вычислений Google находятся под угрозой из-за мошенничества IBM». New Scientist . Получено 22 октября 2017 г.
  32. ^ Харрис, Марк (5 ноября 2018 г.). «Google привлекла NASA, чтобы помочь ей доказать квантовое превосходство в течение нескольких месяцев». MIT Technology Review . Получено 30 ноября 2018 г.
  33. ^ ab Boixo, Sergio; Isakov, Sergey V.; Smelyanskiy, Vadim N.; Babbush, Ryan; Ding, Nan; Jiang, Zhang; Bremner, Michael J.; Martinis, John M.; Neven, Hartmut (23 апреля 2018 г.). «Характеристика квантового превосходства в ближнесрочных устройствах». Nature Physics . 14 (6): 595–600. arXiv : 1608.00263 . Bibcode :2018NatPh..14..595B. doi :10.1038/s41567-018-0124-x. S2CID  4167494.
  34. ^ Хартнетт, Кевин (18 июня 2019 г.). «Новый закон для описания роста квантовых вычислений?». Журнал Quanta .
  35. ^ [1], Financial Times , сентябрь 2019 г. (требуется подписка)
  36. ^ "Google рекламирует достижение квантовых вычислений". MarketWatch . Associated Press.
  37. ^ «Демонстрация квантового превосходства» – через www.youtube.com.
  38. ^ ab «Квантовое превосходство с использованием программируемого сверхпроводящего процессора».
  39. ^ Arute, Frank; et al. (23 октября 2019 г.). «Квантовое превосходство с использованием программируемого сверхпроводящего процессора». Nature . 574 (7779): 505–510. arXiv : 1910.11333 . Bibcode :2019Natur.574..505A. doi : 10.1038/s41586-019-1666-5 . PMID  31645734.
  40. ^ «Что означают дебаты Google и IBM по поводу квантового превосходства». ZDNet .
  41. ^ Zialcita, Paolo (23 октября 2019 г.). «Google заявляет о достижении квантового превосходства — IBM отступает». NPR . Получено 24 октября 2019 г.
  42. ^ Лю, Юн (Александр); Лю, Синь (Люси); Ли, Фан (Нэнси); Фу, Хаохуань; Ян, Юйлин; Сун, Цзявэй; Чжао, Пэнпэн; Ван, Чжэнь; Пэн, Дацзя; Чэнь, Хуаронг; Го, Чу (14.11.2021). «Закрытие разрыва «квантового превосходства»». Труды Международной конференции по высокопроизводительным вычислениям, сетевым технологиям, хранению и анализу . SC '21. Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 1–12. arXiv : 2110.14502 . doi :10.1145/3458817.3487399. ISBN 978-1-4503-8442-1. S2CID  239036985.
  43. ^ Балмер, Джейкоб ФФ; Белл, Брин А.; Чедвик, Рэйчел С.; Джонс, Алекс Э.; Моисе, Диана; Ригацци, Алессандро; Торбеке, Ян; Хаус, Утц-Уве; Ван Варенберг, Томас; Патель, Радж Б.; Уолмсли, Ян А. (2022-01-28). "Граница квантового преимущества в выборке гауссовых бозонов". Science Advances . 8 (4): eabl9236. arXiv : 2108.01622 . Bibcode :2022SciA....8.9236B. doi :10.1126/sciadv.abl9236. ISSN  2375-2548. PMC 8791606 . PMID  35080972. 
  44. ^ Маккормик, Кэти (10.02.2022). «Гонка между классическими и квантовыми компьютерами не окончена». Физика . 15 : 19. Bibcode : 2022PhyOJ..15...19M. doi : 10.1103/Physics.15.19 . S2CID  246910085.
  45. ^ Пан, Фэн; Чэнь, Кейанг; Чжан, Пан (2022). «Решение проблемы выборки квантовых схем Sycamore». Physical Review Letters . 129 (9): 090502. arXiv : 2111.03011 . Bibcode : 2022PhRvL.129i0502P. doi : 10.1103/PhysRevLett.129.090502. PMID  36083655. S2CID  251755796.
  46. ^ «Обычные компьютеры все-таки могут победить квантовый компьютер Google». 2022-08-02. doi :10.1126/science.ade2364. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  47. ^ «Исследователи, использующие обычный суперкомпьютер, узурпировали «квантовое превосходство» Google». TechCrunch . Получено 07.08.2022 .
  48. ^ ab Ball, Philip (2020-12-03). «Физики в Китае бросают вызов «квантовому преимуществу» Google". Природа . 588 (7838): 380. Библиографический код :2020Natur.588..380B. doi :10.1038/d41586-020-03434-7. PMID  33273711.
  49. ^ Гаристо, Дэниел (3 декабря 2020 г.). «Квантовый компьютер на основе света превосходит самые быстрые классические суперкомпьютеры». Scientific American . Получено 07.12.2020 .
  50. ^ Коновер, Эмили (2020-12-03). «Новый квантовый компьютер на основе света Jiuzhang достиг квантового превосходства». Science News . Получено 2020-12-07 .
  51. ^ Чжун, Хан-Сен; Дэн, Ю-Хао; Цинь, Цзянь; Ван, Хуэй; Чен, Мин-Ченг; Пэн, Ли-Чао; Ло, И-Хан; Ву, Диан; Гонг, Си-Цю; Су, Хао; Ху, И (25 октября 2021 г.). «Программируемая по фазе выборка гауссовских бозонов с использованием стимулированного сжатого света». Письма о физических отзывах . 127 (18): 180502. arXiv : 2106.15534 . Бибкод : 2021PhRvL.127r0502Z. doi : 10.1103/PhysRevLett.127.180502. PMID  34767431. S2CID  235669908.
  52. ^ Джонстон, Хэмиш (26 октября 2021 г.). «Квантовое преимущество совершает гигантский скачок в оптических и сверхпроводящих системах». Physics World . Получено 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 . Bibcode : 2021PhRvL.127r0502Z. doi : 10.1103/PhysRevLett.127.180502. PMID  34767431. S2CID  235669908.
  55. ^ Сандерс, Барри К. (2021-10-25). «Квантовый скачок для квантового первенства». Физика . 14 : 147. Bibcode : 2021PhyOJ..14..147S. doi : 10.1103/Physics.14.147 . S2CID  244826882.
  56. ^ Цинлин Чжу, Сируй Цао и др. (25 октября 2021 г.). «Квантовое вычислительное преимущество с помощью 60-кубитной 24-цикловой случайной выборки схемы». Science Bulletin . 67 (3): 240–245. arXiv : 2109.03494 . doi :10.1016/j.scib.2021.10.017. ISSN  2095-9273. PMID  36546072. S2CID  237442167.
  57. ^ Брод, Дэниел Йост (1 июня 2022 г.). «Петли упрощают настройку для повышения квантового вычислительного преимущества». Nature . 606 (7912): 31–32. Bibcode :2022Natur.606...31B. doi :10.1038/d41586-022-01402-x. PMID  35650360. S2CID  249277681.
  58. ^ Мадсен, Ларс С.; Лауденбах, Фабиан; Аскарани, Мохсен Фаламарци; Рортаис, Фабьен; Винсент, Тревор; Балмер, Джейкоб Ф. Ф.; Миатто, Филиппо М.; Нойхаус, Леонхард; Хельт, Лукас Г.; Коллинз, Мэтью Дж.; Лита, Адриана Э. (1 июня 2022 г.). «Квантовое вычислительное преимущество с программируемым фотонным процессором». Nature . 606 (7912): 75–81. Bibcode :2022Natur.606...75M. doi :10.1038/s41586-022-04725-x. ISSN  1476-4687. PMC 9159949 . PMID  35650354. 
  59. ^ Король, Эндрю; Ночера, Альберто; Рамс, Марек; Дзярмага, Яцек; Виерсема, Роланд; Берноуди, Уильям; Рэймонд, Джек; Каушал, Нитин; Хайнсдорф, Никлас; Харрис, Ричард; Бутби, Келли; Альтомаре, Фабио; Беркли, Эндрю; Бошнак, Мартин; Черн, Кевин; Кристиани, Холли; Сибере, Саманта; Коннор, Джейк; Ден, Мартин; Дешпанде, Рахул; Эджтемаи, Сара; Фарре, По; Хамер, Келси; Хоскинсон, Эмиль; Хуан, Шуйюань; Джонсон, Марк; Кортас, Самуэль; Ладизинский, Эрик; Лай, Тони; Лантинг, Тревор; Ли, Райан; Макдональд, Эллисон; Марсден, Гаэлен; МакГеоч, Кэтрин; Молави, Реза; Нойфельд, Ричард; Норузпур, Мана; О, Трэвис; Пасвольский, Джоэл; Пойтрас, Патрик; Пулен-Ламар, Габриэль; Прескотт, Томас; Рейс, Маурисио; Рич, Крис; Самани, Мохаммед; Шелдан, Бенджамин; Смирнов Анатолий; Степка, Эдвард; Труллас Клавера, Берта; Цай, Николай; Фолькманн, Марк; Уитакар, Александр; Уиттакер, Джед; Уилкинсон, Уоррен; Яо, Джейсон; Йи, Ти Джей; Сандвик, Андерс; Альварес, Гонсало; Мелько, Роджер; Карраскилья, Хуан; Франц, Марсель; Амин, Мохаммед (1 марта 2024 г.). «Вычислительное превосходство в квантовом моделировании». arXiv : 2403.00910v1 .
  60. ^ Клив, Ричард (2000). «Введение в квантовую теорию сложности» (PDF) . ЦЕРН . Bibcode : 2000qcqi.book..103C.
  61. ^ ab Watrous, John (2009). «Квантовая вычислительная сложность». В Meyers, Robert A. (ред.). Encyclopedia of Complexity and Systems Science . Springer New York. стр. 7174–7201. doi :10.1007/978-0-387-30440-3_428. ISBN 9780387758886. S2CID  1380135.
  62. ^ ab Watrous, John (21 апреля 2018 г.). «Квантовая вычислительная сложность». arXiv : 0804.3401 [quant-ph].
  63. ^ Тушарова, Тереза ​​(2004). «Квантовые классы сложности». arXiv : cs/0409051 .
  64. ^ ab Lund, AP; Bremner, Michael J.; Ralph, TC (2017-04-13). "Проблемы квантовой выборки, выборка бозонов и квантовое превосходство". npj Quantum Information . 3 (1): 15. arXiv : 1702.03061 . Bibcode : 2017npjQI...3...15L. doi : 10.1038/s41534-017-0018-2. ISSN  2056-6387. S2CID  54628108.
  65. ^ Гард, Брайан Т.; Мотес, Кит Р.; Олсон, Джонатан П.; Роде, Питер П.; Доулинг, Джонатан П. (август 2015 г.). «Введение в бозонную выборку». От атомного до мезоскопического масштаба: роль квантовой когерентности в системах различной сложности . World Scientific. стр. 167–192. arXiv : 1406.6767 . doi :10.1142/9789814678704_0008. ISBN 978-981-4678-70-4. S2CID  55999387.
  66. ^ Бремнер, Майкл Дж.; Монтанаро, Эшли; Шеперд, Дэн Дж. (2016-08-18). "Сложность в среднем случае против приближенного моделирования коммутирующих квантовых вычислений". Physical Review Letters . 117 (8): 080501. arXiv : 1504.07999 . Bibcode : 2016PhRvL.117h0501B. doi : 10.1103/PhysRevLett.117.080501. ISSN  0031-9007. PMID  27588839. S2CID  8590553.
  67. ^ Джордан, Стивен. «Quantum Algorithm Zoo». math.nist.gov . Архивировано из оригинала 2018-04-29 . Получено 2017-07-29 .
  68. ^ ab Shor, P. (1999-01-01). "Алгоритмы полиномиального времени для разложения на простые множители и дискретных логарифмов на квантовом компьютере". SIAM Review . 41 (2): 303–332. arXiv : quant-ph/9508027 . Bibcode : 1999SIAMR..41..303S. doi : 10.1137/S0036144598347011. ISSN  0036-1445.
  69. ^ Рубинштейн, Майкл (19 октября 2006 г.). «Распределение решений уравнения xy = N mod a с применением к факторизации целых чисел». arXiv : math/0610612 .
  70. ^ Бабай, Ласло; Билс, Роберт; Сересс, Акош (2009). «Теория матричных групп в полиномиальном времени». Труды сорок первого ежегодного симпозиума ACM по теории вычислений . STOC '09. Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. С. 55–64. CiteSeerX 10.1.1.674.9429 . doi :10.1145/1536414.1536425. ISBN  9781605585062. S2CID  9052772.
  71. ^ Ривест, Р. Л.; Шамир, А.; Адлеман, Л. (февраль 1978 г.). «Метод получения цифровых подписей и криптосистем с открытым ключом». Commun. ACM . 21 (2): 120–126. CiteSeerX 10.1.1.607.2677 . doi :10.1145/359340.359342. ISSN  0001-0782. S2CID  2873616. 
  72. ^ Мартин-Лопес, Энрике; Лэйнг, Энтони; Лоусон, Томас; Альварес, Роберто; Чжоу, Сяо-Ци; О'Брайен, Джереми Л. (ноябрь 2012 г.). «Экспериментальная реализация алгоритма квантовой факторизации Шора с использованием рециркуляции кубитов». Nature Photonics . 6 (11): 773–776. arXiv : 1111.4147 . Bibcode :2012NaPho...6..773M. doi :10.1038/nphoton.2012.259. ISSN  1749-4893. S2CID  46546101.
  73. ^ Фаулер, Остин Г.; Мариантони, Маттео; Мартинис, Джон М.; Клеланд, Эндрю Н. (2012-09-18). «Поверхностные коды: на пути к практическим крупномасштабным квантовым вычислениям». Physical Review A. 86 ( 3): 032324. arXiv : 1208.0928 . Bibcode : 2012PhRvA..86c2324F. doi : 10.1103/PhysRevA.86.032324. S2CID  119277773.
  74. ^ Рахими-Кешари, Салех; Ральф, Тимоти К.; Кейвс, Карлтон М. (2016-06-20). «Достаточные условия для эффективного классического моделирования квантовой оптики». Physical Review X. 6 ( 2): 021039. arXiv : 1511.06526 . Bibcode : 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. ^ ab Клиффорд, Питер; Клиффорд, Рафаэль (2017-06-05). «Классическая сложность выборки бозонов». arXiv : 1706.01260 [cs.DS].
  77. ^ ab Невилл, Алекс; Воробей, Крис; Клиффорд, Рафаэль; Джонстон, Эрик; Бирчалл, Патрик М.; Монтанаро, Эшли; Лэнг, Энтони (2017-10-02). «Нет неизбежного квантового превосходства путем выборки бозонов». Nature Physics . 13 (12): 1153–1157. arXiv : 1705.00686 . Bibcode :2017arXiv170500686N. doi :10.1038/nphys4270. ISSN  1745-2473. S2CID  73635825.
  78. ^ Де Рэдт, Ханс; Цзинь, Фэнпин; Вильш, Деннис; Вильш, Мадита; Ёсиока, Наоки; Ито, Нобуясу; Юань, Шэнцзюнь; Михильсен, Кристель (ноябрь 2018 г.). «Массово-параллельный квантовый компьютерный симулятор, одиннадцать лет спустя». Computer Physics Communications . 237 : 47–61. arXiv : 1805.04708 . doi : 10.1016/j.cpc.2018.11.005 .
  79. ^ Педно, Эдвин; Джон А. Ганнелс; Джакомо Нанничини; Лиор Хореш; Томас Магерлейн; Эдгар Соломоник; Роберт Виснифф (октябрь 2017 г.). «Преодоление барьера в 49 кубитов при моделировании квантовых схем». arXiv : 1710.05867 [quant-ph].
  80. ^ "Квантовое превосходство с использованием программируемого сверхпроводящего процессора". Блог Google AI . Получено 2019-11-02 .
  81. ^ Метц, Кейд (23 октября 2019 г.). «Google заявляет о квантовом прорыве, который может изменить вычисления». The New York Times . Получено 14 января 2020 г.
  82. ^ Эдвин Педнолт; Джон Ганнелс; Джакомо Нанничини; Лиор Хореш; Роберт Висниефф (октябрь 2019 г.). «Использование вторичного хранилища для моделирования глубоких 54-кубитных схем Sycamore». arXiv : 1910.09534 [quant-ph].
  83. ^ "Google и IBM столкнулись из-за заявления о квантовом превосходстве". Журнал Quanta . 23 октября 2019 г. Получено 29 октября 2020 г.
  84. ^ ab Kalai, Gil (2011-06-02). «Как квантовые компьютеры терпят неудачу: квантовые коды, корреляции в физических системах и накопление шума». arXiv : 1106.0485 [quant-ph].
  85. ^ Шор, Питер В. (1995-10-01). «Схема снижения декогеренции в памяти квантового компьютера». Physical Review A. 52 ( 4): R2493–R2496. Bibcode : 1995PhRvA..52.2493S. doi : 10.1103/PhysRevA.52.R2493. PMID  9912632.
  86. ^ Steane, AM (1996-07-29). «Коды исправления ошибок в квантовой теории». Physical Review Letters . 77 (5): 793–797. Bibcode : 1996PhRvL..77..793S. doi : 10.1103/PhysRevLett.77.793. PMID  10062908.
  87. ^ Ааронов, Дорит; Бен-Ор, Майкл (1999-06-30). «Отказоустойчивые квантовые вычисления с постоянной частотой ошибок». arXiv : quant-ph/9906129 .
  88. ^ Книлл, Э. (2005-03-03). «Квантовые вычисления с реалистично шумными устройствами». Nature . 434 (7029): 39–44. arXiv : quant-ph/0410199 . Bibcode :2005Natur.434...39K. doi :10.1038/nature03350. ISSN  0028-0836. PMID  15744292. S2CID  4420858.
  89. ^ Калай, Гил (2016-05-03). «Квантовая компьютерная головоломка (расширенная версия)». arXiv : 1605.00992 [quant-ph].
  90. ^ Дьяконов, МИ (2007). «Действительно ли возможны отказоустойчивые квантовые вычисления?». В Luryi, S.; Xu, J.; Zaslavsky, A. (ред.). Future Trends in Microelectronics. Up the Nano Creek . Wiley. стр. 4–18. arXiv : quant-ph/0610117 . Bibcode :2006quant.ph.10117D.
  91. ↑ Board, The Editorial (17 декабря 2019 г.). «Мнение | Достижение квантового пробуждения». Wall Street Journal . Получено 21 декабря 2019 г.
  92. ^ Кнаптон, Сара (17.12.2019). «Ученые, высмеиваемые за утверждение, что «квантовое превосходство» — это расистский и колонизаторский термин». The Telegraph . ISSN  0307-1235 . Получено 21.12.2019 .
  93. ^ Паласиос-Берракеро, Кармен; Мьюек, Леони; Персо, Дивья М. (10.12.2019). «Вместо „превосходства“ используйте „квантовое преимущество“». Nature . 576 (7786): 213. doi : 10.1038/d41586-019-03781-0 . PMID  31822842.
  94. ^ Болл, Филипп (17 декабря 2020 г.). «Физики в Китае бросают вызов „квантовому преимуществу“ Google». Nature . 588 (7838): 380. Bibcode :2020Natur.588..380B. doi :10.1038/d41586-020-03434-7. PMID  33273711. S2CID  227282052 . Получено 16 декабря 2020 г. .