Квантовый компьютер — это компьютер , который использует преимущества квантово-механических явлений.
В малых масштабах физическая материя проявляет свойства как частиц, так и волн , и квантовые вычисления используют это поведение, в частности квантовую суперпозицию и запутанность, используя специализированное оборудование, которое поддерживает подготовку и манипулирование квантовыми состояниями .
Классическая физика не может объяснить работу этих квантовых устройств, а масштабируемый квантовый компьютер может выполнять некоторые вычисления экспоненциально быстрее (относительно масштабирования входных данных) [2] , чем любой современный «классический» компьютер . В частности, крупномасштабный квантовый компьютер мог бы взламывать широко используемые схемы шифрования и помогать физикам выполнять физическое моделирование ; однако нынешний уровень техники в значительной степени экспериментальный и непрактичный, что затрудняет его полезное применение. Более того, масштабируемые квантовые компьютеры бесперспективны для решения многих практических задач, а для многих важных задач квантовое ускорение оказывается невозможным.
Основной единицей информации в квантовых вычислениях является кубит , аналогичный биту в традиционной цифровой электронике. В отличие от классического бита, кубит может существовать в суперпозиции двух своих «базисных» состояний. При измерении кубита результатом является вероятностный результат классического бита, что делает квантовые компьютеры в целом недетерминированными. Если квантовый компьютер манипулирует кубитом определенным образом, эффекты волновой интерференции могут усилить желаемые результаты измерений. Разработка квантовых алгоритмов предполагает создание процедур, которые позволяют квантовому компьютеру выполнять вычисления эффективно и быстро.
Физическая разработка высококачественных кубитов оказалась сложной задачей. Если физический кубит недостаточно изолирован от своего окружения, он страдает от квантовой декогеренции , вносящей шум в вычисления. Парадоксально, но идеальная изоляция кубитов также нежелательна, поскольку для квантовых вычислений обычно требуется инициализировать кубиты, выполнять контролируемые взаимодействия кубитов и измерять результирующие квантовые состояния. Каждая из этих операций вносит ошибки и страдает от шума, и такие неточности накапливаются.
В принципе, неквантовый (классический) компьютер может решать те же вычислительные задачи, что и квантовый компьютер, если дать ему достаточно времени. Квантовое преимущество проявляется в форме временной сложности , а не в вычислимости , а теория квантовой сложности показывает, что некоторые квантовые алгоритмы для тщательно выбранных задач требуют экспоненциально меньшего количества вычислительных шагов, чем самые известные неквантовые алгоритмы. Такие задачи теоретически могут быть решены на крупномасштабном квантовом компьютере, тогда как классические компьютеры не завершат вычисления за разумное время. Однако квантовое ускорение не является универсальным или даже типичным для вычислительных задач, поскольку доказано, что базовые задачи, такие как сортировка , не допускают какого-либо асимптотического квантового ускорения. Заявления о квантовом превосходстве привлекли значительное внимание к этой дисциплине, но были продемонстрированы на надуманных задачах, в то время как варианты практического использования в краткосрочной перспективе остаются ограниченными.
На протяжении многих лет области квантовой механики и информатики формировали отдельные академические сообщества. [3] Современная квантовая теория была разработана в 1920-х годах для объяснения корпускулярно-волнового дуализма , наблюдаемого на атомных масштабах, [4] и в последующие десятилетия появились цифровые компьютеры , которые заменили человеческие компьютеры для утомительных вычислений. [5] Обе дисциплины имели практическое применение во время Второй мировой войны ; компьютеры сыграли важную роль в криптографии военного времени [6] , а квантовая физика была важна для ядерной физики, используемой в Манхэттенском проекте . [7]
Когда физики применили квантово-механические модели к вычислительным задачам и заменили цифровые биты на кубиты , области квантовой механики и информатики начали сближаться. В 1980 году Пол Бениофф представил квантовую машину Тьюринга , которая использует квантовую теорию для описания упрощенного компьютера. [8] Когда цифровые компьютеры стали быстрее, физики столкнулись с экспоненциальным увеличением накладных расходов при моделировании квантовой динамики , [9] что побудило Юрия Манина и Ричарда Фейнмана независимо предположить, что аппаратное обеспечение, основанное на квантовых явлениях, может быть более эффективным для компьютерного моделирования. [10] [11] [12] В статье 1984 года Чарльз Беннетт и Жиль Брассар применили квантовую теорию к протоколам криптографии и продемонстрировали, что квантовое распределение ключей может повысить информационную безопасность . [13] [14]
Затем появились квантовые алгоритмы для решения задач оракула , такие как алгоритм Дойча в 1985 году, [15] алгоритм Бернштейна -Вазирани в 1993 году, [16] и алгоритм Саймона в 1994 году . [17] Эти алгоритмы не решали практические проблемы, но демонстрировали математически что можно получить больше информации, запросив черный ящик с квантовым состоянием в суперпозиции , что иногда называют квантовым параллелизмом . [18] Питер Шор опирался на эти результаты в своих алгоритмах взлома широко используемых протоколов шифрования RSA и Диффи-Хеллмана в 1994 году , [19] которые привлекли значительное внимание к области квантовых вычислений. [20] В 1996 году алгоритм Гровера установил квантовое ускорение для широко применимой задачи неструктурированного поиска. [21] [22] В том же году Сет Ллойд доказал, что квантовые компьютеры могут моделировать квантовые системы без экспоненциальных накладных расходов, присутствующих в классическом моделировании, [23] подтвердив гипотезу Фейнмана 1982 года. [24]
За прошедшие годы экспериментаторы создали небольшие квантовые компьютеры, используя захваченные ионы и сверхпроводники . [25] В 1998 году двухкубитный квантовый компьютер продемонстрировал осуществимость этой технологии, [26] [27] и последующие эксперименты увеличили количество кубитов и снизили частоту ошибок. [25] В 2019 году Google AI и НАСА объявили, что они достигли квантового превосходства с помощью 54-кубитной машины, выполняющей вычисления, невозможные для любого классического компьютера. [28] [29] [30] Однако обоснованность этого утверждения все еще активно исследуется. [31] [32]
Пороговая теорема показывает, как увеличение количества кубитов может уменьшить количество ошибок, [33] однако полностью отказоустойчивые квантовые вычисления остаются «довольно далекой мечтой». [34] По мнению некоторых исследователей, шумные квантовые машины промежуточного масштаба ( NISQ ) могут найти специализированное применение в ближайшем будущем, но шум в квантовых вентилях ограничивает их надежность. [34]
Инвестиции в исследования в области квантовых вычислений увеличились в государственном и частном секторах. [35] [36] Как резюмировала одна консалтинговая фирма, [37]
... инвестиционные доллары текут потоком, а стартапы в области квантовых вычислений множатся. ... Хотя квантовые вычисления обещают помочь предприятиям решать проблемы, которые находятся за пределами досягаемости и скорости обычных высокопроизводительных компьютеров , на этой ранней стадии варианты использования в основном носят экспериментальный и гипотетический характер.
С точки зрения управления бизнесом, потенциальные применения квантовых вычислений можно разделить на четыре основные категории: кибербезопасность, анализ данных и искусственный интеллект, оптимизация и моделирование, а также управление данными и поиск. [38]
В декабре 2023 года физики впервые сообщили о запутанности отдельных молекул, которая может иметь важные применения в квантовых вычислениях. [39] Также в декабре 2023 года ученые из Гарварда успешно создали «квантовые схемы», которые исправляют ошибки более эффективно, чем альтернативные методы, что потенциально может устранить серьезное препятствие для практических квантовых компьютеров. [40] [41] Исследовательскую группу из Гарварда поддерживали Массачусетский технологический институт , QuEra Computing , Калифорнийский технологический институт и Принстон , а также финансировала программа DARPA «Оптимизация с помощью квантовых устройств промежуточного масштаба с шумом» (ONISQ) . [42] [43] Продолжаются исследования, направленные на запуск квантовых вычислений с помощью топологических и фотонных подходов. [44]
Компьютерные инженеры обычно описывают работу современного компьютера с точки зрения классической электродинамики . В этих «классических» компьютерах некоторые компоненты (например, полупроводники и генераторы случайных чисел ) могут полагаться на квантовое поведение, но эти компоненты не изолированы от окружающей среды, поэтому любая квантовая информация быстро декогерируется . Хотя программисты могут полагаться на теорию вероятностей при разработке рандомизированных алгоритмов , квантово-механические понятия, такие как суперпозиция и интерференция , в значительной степени не имеют значения для анализа программ .
Квантовые программы , напротив, полагаются на точный контроль когерентных квантовых систем. Физики описывают эти системы математически, используя линейную алгебру . Комплексные числа моделируют амплитуды вероятности , векторы моделируют квантовые состояния , а матрицы моделируют операции, которые можно выполнять над этими состояниями. В таком случае программирование квантового компьютера — это вопрос составления операций таким образом, чтобы полученная программа выдавала полезный результат в теории и была реализуема на практике.
Как физик Чарли Беннетт описывает взаимосвязь между квантовыми и классическими компьютерами, [45]
Классический компьютер — это квантовый компьютер... поэтому нам не следует задаваться вопросом: «Откуда берется квантовое ускорение?» Мы должны сказать: «Ну, все компьютеры квантовые… Откуда берутся классические замедления?»
Подобно тому, как бит является основной концепцией классической теории информации, кубит является фундаментальной единицей квантовой информации . Тот же термин «кубит» используется для обозначения абстрактной математической модели и любой физической системы, представленной этой моделью. Классический бит, по определению, существует в любом из двух физических состояний, которые можно обозначить 0 и 1. Кубит также описывается состоянием, и два состояния, часто обозначаемые |0⟩ и |1⟩ , служат квантовыми аналогами классические состояния 0 и 1. Однако квантовые состояния |0⟩ и |1⟩ принадлежат векторному пространству , а это означает, что их можно умножать на константы и складывать вместе, и результатом снова является допустимое квантовое состояние. Такая комбинация известна как суперпозиция | 0⟩ и |1⟩ . [46] [47]
Двумерный вектор математически представляет состояние кубита. Физики обычно используют обозначение Дирака для квантовомеханической линейной алгебры , записывая | ψ ⟩ ' ket psi ' для вектора с меткой ψ . Поскольку кубит представляет собой систему с двумя состояниями, любое состояние кубита принимает форму α |0⟩ + β |1⟩ , где |0⟩ и |1⟩ — стандартные базисные состояния , [a] и α и β — вероятности амплитуды , которые, как правило, являются комплексными числами . [47] Если либо α , либо β равно нулю, кубит фактически является классическим битом; когда оба не равны нулю, кубит находится в суперпозиции. Такой вектор квантового состояния действует аналогично (классическому) вектору вероятности , с одним ключевым отличием: в отличие от вероятностей, амплитуды вероятности не обязательно являются положительными числами. [49] Отрицательные амплитуды допускают деструктивную интерференцию волн.
Когда кубит измеряется в стандартном базисе , результатом является классический бит. Правило Борна описывает соответствие между амплитудами и вероятностями в квадрате нормы : при измерении кубита α |0⟩ + β |1⟩ состояние коллапсирует до |0⟩ с вероятностью | α | 2 или |1⟩ с вероятностью | β | 2 . Любое допустимое состояние кубита имеет коэффициенты α и β такие, что | α | 2 + | β | 2 = 1 . Например, измерение кубита1/√2|0⟩ +1/√2|1⟩ с равной вероятностью даст либо |0⟩ , либо |1⟩ .
Каждый дополнительный кубит удваивает размерность пространства состояний . [48] Например, вектор1/√2|00⟩ +1/√2|01⟩ представляет собой двухкубитное состояние, тензорное произведение кубита |0⟩ на кубит1/√2|0⟩ +1/√2|1⟩ . Этот вектор обитает в четырехмерном векторном пространстве , натянутом на базисные векторы |00⟩ , |01⟩ , |10⟩ и |11⟩ . Штат Белла 1/√2|00⟩ +1/√2|11⟩ невозможно разложить на тензорное произведение двух отдельных кубитов — два кубита запутаны, поскольку их амплитуды вероятности коррелируют . В общем, векторное пространство для системы из n -кубитов является 2n - мерным, и это усложняет классическому компьютеру моделирование квантового: для представления системы из 100 кубитов требуется хранить 2100 классических значений.
Состоянием этой однокубитной квантовой памяти можно манипулировать, применяя квантовые логические элементы , аналогично тому, как классической памятью можно манипулировать с помощью классических логических элементов . Одним из важных вентилей как для классических, так и для квантовых вычислений является вентиль НЕ, который может быть представлен матрицей
Математику однокубитных вентилей можно расширить для работы с многокубитной квантовой памятью двумя важными способами. Один из способов — просто выбрать кубит и применить этот вентиль к целевому кубиту, оставив остальную часть памяти незатронутой. Другой способ — применить гейт к цели, только если другая часть памяти находится в желаемом состоянии. Эти два варианта можно проиллюстрировать на другом примере. Возможные состояния двухкубитной квантовой памяти:
Подводя итог, квантовые вычисления можно описать как сеть квантовых логических элементов и измерений. Однако любое измерение можно отложить до конца квантовых вычислений, хотя эта отсрочка может потребовать вычислительных затрат, поэтому большинство квантовых схем изображают сеть, состоящую только из квантовых логических элементов и без каких-либо измерений.
Квантовый параллелизм — это эвристика, согласно которой квантовые компьютеры можно рассматривать как оценку функции для нескольких входных значений одновременно. Этого можно достичь, подготовив квантовую систему в суперпозиции входных состояний и применив унитарное преобразование, которое кодирует функцию, подлежащую оценке. Результирующее состояние кодирует выходные значения функции для всех входных значений в суперпозиции, что позволяет одновременно вычислять несколько выходных значений. Это свойство является ключом к ускорению многих квантовых алгоритмов. Однако «параллелизма» в этом смысле недостаточно для ускорения вычислений, поскольку измерение в конце вычислений дает только одно значение. Чтобы быть полезным, квантовый алгоритм должен также включать в себя какой-то другой концептуальный компонент. [50] [51]
Существует ряд моделей вычислений для квантовых вычислений, отличающихся основными элементами, на которые разлагаются вычисления.
Массив квантовых вентилей разлагает вычисления на последовательность квантовых вентилей размером в несколько кубитов . Квантовые вычисления можно описать как сеть квантовых логических элементов и измерений. Однако любое измерение можно отложить до конца квантовых вычислений, хотя эта отсрочка может потребовать вычислительных затрат, поэтому большинство квантовых схем изображают сеть, состоящую только из квантовых логических элементов и без каких-либо измерений.
Любое квантовое вычисление (которое в приведенном выше формализме представляет собой любую унитарную матрицу размера над кубитами) может быть представлено как сеть квантовых логических элементов из довольно небольшого семейства элементов. Выбор семейства вентилей, обеспечивающий такую конструкцию, известен как универсальный набор вентилей , поскольку компьютер, который может запускать такие схемы, является универсальным квантовым компьютером . Один общий такой набор включает в себя все однокубитные вентили, а также вентиль CNOT сверху. Это означает, что любые квантовые вычисления могут быть выполнены путем выполнения последовательности однокубитных вентилей вместе с вентилями CNOT. Хотя этот набор вентилей бесконечен, его можно заменить конечным набором вентилей, обратившись к теореме Соловея-Китаева .
Квантовый компьютер, основанный на измерениях, разлагает вычисления на последовательность измерений состояния Белла и однокубитных квантовых вентилей , применяемых к сильно запутанному начальному состоянию ( состоянию кластера ), используя метод, называемый телепортацией квантовых вентилей .
Адиабатический квантовый компьютер , основанный на квантовом отжиге , разлагает вычисления на медленное непрерывное преобразование начального гамильтониана в окончательный гамильтониан, основные состояния которого содержат решение. [52]
Топологический квантовый компьютер разлагает вычисления на сплетение анионов в двумерную решетку. [53]
Квантовая машина Тьюринга — это квантовый аналог машины Тьюринга . [8] Все эти модели вычислений — квантовые схемы, [54] односторонние квантовые вычисления, [55] адиабатические квантовые вычисления, [56] и топологические квантовые вычисления [57] — как было показано, эквивалентны квантовому квантовому вычислению Тьюринга. машина; при идеальной реализации одного такого квантового компьютера он может моделировать все остальные с не более чем полиномиальными издержками. Эта эквивалентность не обязательно справедлива для практических квантовых компьютеров, поскольку накладные расходы на моделирование могут быть слишком большими, чтобы быть практичными.
Квантовая криптография открывает новые способы безопасной передачи данных; например, квантовое распределение ключей использует запутанные квантовые состояния для создания безопасных криптографических ключей . [58] Когда отправитель и получатель обмениваются квантовыми состояниями, они могут гарантировать, что злоумышленник не перехватит сообщение, поскольку любой несанкционированный перехватчик нарушит хрупкую квантовую систему и внесет заметные изменения. [59] Таким образом, с помощью соответствующих криптографических протоколов отправитель и получатель могут установить общую частную информацию, устойчивую к подслушиванию. [13] [60]
Современные оптоволоконные кабели способны передавать квантовую информацию на относительно короткие расстояния. Продолжающиеся экспериментальные исследования направлены на разработку более надежного оборудования (например, квантовых повторителей) в надежде масштабировать эту технологию для квантовых сетей на большие расстояния со сквозной запутанностью. Теоретически это может позволить реализовать новые технологические приложения, такие как распределенные квантовые вычисления и расширенное квантовое зондирование . [61] [62]
Прогресс в поиске квантовых алгоритмов обычно сосредоточен на этой модели квантовой схемы, хотя существуют исключения, такие как квантовый адиабатический алгоритм . Квантовые алгоритмы можно грубо классифицировать по типу ускорения, достигнутого по сравнению с соответствующими классическими алгоритмами. [63]
Квантовые алгоритмы, которые предлагают более чем полиномиальное ускорение по сравнению с самым известным классическим алгоритмом, включают алгоритм Шора для факторизации и связанные с ним квантовые алгоритмы для вычисления дискретных логарифмов , решения уравнения Пелля и, в более общем плане, решения проблемы скрытой подгруппы для абелевых конечных групп. [63] Эти алгоритмы зависят от примитива квантового преобразования Фурье . Не было найдено математического доказательства того, что столь же быстрый классический алгоритм невозможно найти, но данные свидетельствуют о том, что это маловероятно. [64] Определенные задачи оракула, такие как проблема Саймона и проблема Бернштейна-Вазирани, действительно дают доказуемое ускорение, хотя это относится к модели квантовых запросов , которая является ограниченной моделью, где нижние границы гораздо легче доказать и не обязательно приводят к ускорению. для практических задач.
Другие задачи, включая моделирование квантово-физических процессов из химии и физики твердого тела, аппроксимацию некоторых полиномов Джонса и квантовый алгоритм для линейных систем уравнений , имеют квантовые алгоритмы, которые, по-видимому, дают суперполиномиальное ускорение и являются BQP -полными. Поскольку эти задачи являются BQP-полными, столь же быстрый классический алгоритм для них будет означать, что ни один квантовый алгоритм не даст суперполиномиального ускорения, что считается маловероятным. [65]
Некоторые квантовые алгоритмы, такие как алгоритм Гровера и усиление амплитуды , дают полиномиальное ускорение по сравнению с соответствующими классическими алгоритмами. [63] Хотя эти алгоритмы дают сравнительно скромное квадратичное ускорение, они широко применимы и, таким образом, дают ускорение для широкого круга задач. [22]
Поскольку химия и нанотехнологии полагаются на понимание квантовых систем, а такие системы невозможно эффективно смоделировать классическим способом, квантовое моделирование может стать важным применением квантовых вычислений. [66] Квантовое моделирование также можно использовать для моделирования поведения атомов и частиц в необычных условиях, таких как реакции внутри коллайдера . [67] В июне 2023 года ученые IBM сообщили, что квантовый компьютер дает лучшие результаты при решении физических задач, чем обычный суперкомпьютер. [68] [69]
Около 2% годового мирового производства энергии используется для фиксации азота с целью производства аммиака для процесса Габера в промышленности сельскохозяйственных удобрений (хотя естественные организмы также производят аммиак). Квантовое моделирование может быть использовано для понимания этого процесса и повышения энергоэффективности производства. [70] Ожидается, что к середине 2020-х годов [72] одним из первых применений квантовых вычислений станет моделирование, которое повысит эффективность процесса Габера-Боша [71] , хотя некоторые предсказывают, что это займет больше времени. [73]
Заметным применением квантовых вычислений являются атаки на используемые в настоящее время криптографические системы. Факторизация целых чисел , лежащая в основе безопасности криптографических систем с открытым ключом , считается невозможной с вычислительной точки зрения на обычном компьютере для больших целых чисел, если они являются произведением нескольких простых чисел (например, произведения двух простых чисел по 300 цифр). [74] Для сравнения: квантовый компьютер мог бы решить эту проблему экспоненциально быстрее, используя алгоритм Шора для поиска ее факторов. [75] Эта способность позволила бы квантовому компьютеру взломать многие из используемых сегодня криптографических систем, в том смысле, что для решения проблемы будет существовать полиномиальный по времени (по числу цифр целого числа) алгоритм. В частности, большинство популярных шифров с открытым ключом основаны на сложности факторизации целых чисел или задаче дискретного логарифма , обе из которых могут быть решены с помощью алгоритма Шора. В частности, могут быть нарушены алгоритмы RSA , Диффи-Хеллмана и эллиптической кривой Диффи-Хеллмана . Они используются для защиты безопасных веб-страниц, зашифрованной электронной почты и многих других типов данных. Нарушение этих правил будет иметь серьезные последствия для электронной конфиденциальности и безопасности.
Идентификация криптографических систем, которые могут быть защищены от квантовых алгоритмов, является активно исследуемой темой в области постквантовой криптографии . [76] [77] Некоторые алгоритмы с открытым ключом основаны на проблемах, отличных от проблем целочисленной факторизации и задач дискретного логарифма, к которым применяется алгоритм Шора, например, криптосистема МакЭлиса , основанная на проблеме теории кодирования . [76] [78] Также неизвестно, что криптосистемы на основе решеток могут быть взломаны квантовыми компьютерами, и поиск алгоритма с полиномиальным временем для решения проблемы двугранных скрытых подгрупп , который сломал бы многие криптосистемы на основе решетки, является хорошо изученной открытой проблемой. . [79] Было доказано, что применение алгоритма Гровера для взлома симметричного алгоритма (секретного ключа) методом грубой силы требует времени, равного примерно 2 n /2 вызовов базового криптографического алгоритма, по сравнению с примерно 2 n в классическом случае, [79] 80], что означает, что длина симметричного ключа фактически уменьшается вдвое: AES-256 будет иметь ту же защиту от атаки с использованием алгоритма Гровера, что и AES-128 от классического поиска методом перебора (см. Размер ключа ).
Самый известный пример задачи, позволяющей добиться полиномиального квантового ускорения, — это неструктурированный поиск , который предполагает поиск отмеченного элемента из списка элементов в базе данных. Эту проблему можно решить с помощью алгоритма Гровера, используя запросы к базе данных, квадратично меньшие, чем запросы, необходимые для классических алгоритмов. В этом случае преимущество не только доказуемо, но и оптимально: было показано, что алгоритм Гровера дает максимально возможную вероятность найти искомый элемент при любом количестве поисков оракула. Многие примеры доказуемого квантового ускорения задач запросов основаны на алгоритме Гровера, включая алгоритм Брассара, Хойера и Тэппа для поиска коллизий в функциях «два к одному» [81] и алгоритм Фари, Голдстоуна и Гутмана для оценки NAND-деревьев. [82]
Проблемы, которые можно эффективно решить с помощью алгоритма Гровера, обладают следующими свойствами: [83] [84]
Для задач со всеми этими свойствами время работы алгоритма Гровера на квантовом компьютере масштабируется как квадратный корень из числа входных данных (или элементов в базе данных), в отличие от линейного масштабирования классических алгоритмов. Общий класс задач, к которым может быть применен алгоритм Гровера [85] , — это булева проблема выполнимости , где база данных , через которую работает алгоритм, представляет собой базу данных всех возможных ответов. Примером и возможным применением этого является взломщик паролей , который пытается угадать пароль. Взлом симметричных шифров с помощью этого алгоритма представляет интерес для государственных органов. [86]
Квантовый отжиг основан на адиабатической теореме для проведения расчетов. Система помещается в основное состояние для простого гамильтониана, который медленно развивается к более сложному гамильтониану, основное состояние которого представляет собой решение рассматриваемой проблемы. Адиабатическая теорема утверждает, что если эволюция достаточно медленная, система будет оставаться в своем основном состоянии на протяжении всего процесса.Адиабатическая оптимизация может быть полезна для решения задач вычислительной биологии . [87]
Поскольку квантовые компьютеры могут выдавать результаты, которые классические компьютеры не могут эффективно производить, и поскольку квантовые вычисления по своей сути являются линейными алгебраическими, некоторые выражают надежду на разработку квантовых алгоритмов, которые могут ускорить задачи машинного обучения . [34] [88]
Например, считается, что алгоритм HHL , названный в честь его первооткрывателей Харроу, Хасидима и Ллойда, обеспечивает ускорение по сравнению с классическими аналогами. [34] [89] Некоторые исследовательские группы недавно изучили возможность использования оборудования квантового отжига для обучения машин Больцмана и глубоких нейронных сетей . [90] [91] [92]
Модели глубокой генеративной химии становятся мощными инструментами для ускорения открытия лекарств . Однако огромный размер и сложность структурного пространства всех возможных молекул, подобных лекарствам, создают серьезные препятствия, которые в будущем могут быть преодолены с помощью квантовых компьютеров. Квантовые компьютеры, естественно, хороши для решения сложных квантовых задач многих тел [23] и, таким образом, могут оказаться полезными в приложениях, связанных с квантовой химией. Следовательно, можно ожидать, что генеративные модели с квантовым усилением [93] , включая квантовые GAN [94], в конечном итоге могут быть развиты в совершенные алгоритмы генеративной химии.
По состоянию на 2023 год [обновлять]классические компьютеры превзойдут квантовые компьютеры во всех реальных приложениях. Хотя современные квантовые компьютеры могут ускорить решение конкретных математических задач, они не дают никаких вычислительных преимуществ для практических задач. Для многих задач не существует никакого обещания полезного квантового ускорения, а некоторые задачи доказуемо запрещают любое квантовое ускорение в том смысле, что любое ускорение исключается доказанными теоремами. Ученые и инженеры изучают множество технологий для аппаратного обеспечения квантовых вычислений и надеются разработать масштабируемые квантовые архитектуры, но остаются серьезные препятствия. [95] [96]
При создании крупномасштабного квантового компьютера существует ряд технических проблем. [97] Физик Дэвид ДиВинченцо перечислил эти требования к практическому квантовому компьютеру: [98]
Поиск запчастей для квантовых компьютеров также очень сложен. Сверхпроводящие квантовые компьютеры , подобные тем, что созданы Google и IBM , нуждаются в гелии-3 , побочном продукте ядерных исследований, и специальных сверхпроводящих кабелях, производимых только японской компанией Coax Co. [99]
Управление многокубитными системами требует генерации и координации большого количества электрических сигналов с жестким и детерминированным временным разрешением. Это привело к разработке квантовых контроллеров, которые позволяют взаимодействовать с кубитами. Масштабирование этих систем для поддержки растущего числа кубитов является дополнительной проблемой. [100]
Одной из самых больших проблем, связанных с созданием квантовых компьютеров, является контроль или устранение квантовой декогеренции . Обычно это означает изоляцию системы от окружающей среды, поскольку взаимодействие с внешним миром приводит к декогерентности системы. Однако существуют и другие источники декогеренции. Примеры включают квантовые вентили, колебания решетки и фоновый термоядерный спин физической системы, используемый для реализации кубитов. Декогеренция необратима, поскольку она фактически не унитарна, и обычно ее следует строго контролировать, если не избегать. Время декогеренции для систем-кандидатов, в частности, время поперечной релаксации T 2 (для технологий ЯМР и МРТ , также называемое временем дефазировки ), обычно находится в диапазоне от наносекунд до секунд при низкой температуре. [101] В настоящее время некоторые квантовые компьютеры требуют охлаждения своих кубитов до 20 милликельвинов (обычно с использованием холодильника разбавления [102] ), чтобы предотвратить значительную декогеренцию. [103] Исследование 2020 года утверждает, что ионизирующее излучение , такое как космические лучи, тем не менее может привести к декогеренции определенных систем в течение миллисекунд. [104]
В результате трудоемкие задачи могут привести к неработоспособности некоторых квантовых алгоритмов, поскольку попытка поддерживать состояние кубитов в течение достаточно длительного времени в конечном итоге приведет к повреждению суперпозиций. [105]
Эти проблемы более сложны для оптических подходов, поскольку временные рамки на порядки короче, а часто упоминаемым подходом к их преодолению является формирование оптического импульса . Частота ошибок обычно пропорциональна отношению времени работы ко времени декогеренции, поэтому любая операция должна быть завершена гораздо быстрее, чем время декогеренции.
Как описано в пороговой теореме , если частота ошибок достаточно мала, считается возможным использовать квантовую коррекцию ошибок для подавления ошибок и декогеренции. Это позволяет общему времени расчета превышать время декогеренции, если схема исправления ошибок может исправлять ошибки быстрее, чем их вносит декогерентность. Часто цитируемое значение требуемой частоты ошибок в каждом вентиле для отказоустойчивых вычислений составляет 10 -3 , при условии, что шум является деполяризующим.
Выполнение этого условия масштабируемости возможно для широкого спектра систем. Однако использование исправления ошибок приводит к значительному увеличению количества необходимых кубитов. Число, необходимое для факторизации целых чисел с использованием алгоритма Шора, по-прежнему полиномиально и считается между L и L 2 , где L — количество цифр в числе, подлежащем факторизации; алгоритмы исправления ошибок увеличили бы эту цифру на дополнительный коэффициент L. Для 1000-битного числа это подразумевает необходимость около 10 4 бит без коррекции ошибок. [106] С коррекцией ошибок эта цифра увеличится примерно до 10 7 бит. Время расчета составляет около L 2 или около 10 7 шагов и при частоте 1 МГц около 10 секунд. Однако накладные расходы на кодирование и исправление ошибок увеличивают размер настоящего отказоустойчивого квантового компьютера на несколько порядков. Тщательные оценки [107] [108] показывают, что по крайней мере 3 миллиона физических кубитов будут учитывать 2048-битное целое число за 5 месяцев на квантовом компьютере с полностью исправленными ошибками. С точки зрения количества физических кубитов, на сегодняшний день это остается самой низкой оценкой [109] для практически полезной задачи факторизации целых чисел размером 1024 бита или больше.
Другой подход к проблеме стабильности-декогеренции заключается в создании топологического квантового компьютера с анионами , квазичастицами, используемыми в качестве потоков, и использовании теории кос для формирования стабильных логических элементов. [110] [111]
Физик Джон Прескилл придумал термин «квантовое превосходство» , чтобы описать инженерный подвиг, демонстрирующий, что программируемое квантовое устройство может решить проблему, выходящую за рамки возможностей современных классических компьютеров. [112] [113] [114] Проблема не обязательно должна быть полезной, поэтому некоторые рассматривают тест квантового превосходства только как потенциальный будущий ориентир. [115]
В октябре 2019 года Google AI Quantum при поддержке НАСА стал первым, кто заявил, что достиг квантового превосходства, выполняя вычисления на квантовом компьютере Sycamore более чем в 3 000 000 раз быстрее, чем это можно было бы сделать на Summit , обычно считающемся самым быстрым в мире. компьютер. [29] [116] [117] Это утверждение впоследствии было оспорено: IBM заявила, что Summit может выполнять выборки намного быстрее, чем заявлено, [118] [119] и с тех пор исследователи разработали лучшие алгоритмы для решения проблемы выборки, используемые для утверждения квантовых превосходство, существенно сокращая разрыв между Sycamore и классическими суперкомпьютерами [120] [121] [122] и даже превосходя его. [123] [124] [125]
В декабре 2020 года группа из USTC реализовала тип выборки бозонов на 76 фотонах с помощью фотонного квантового компьютера Jiuzhang , чтобы продемонстрировать квантовое превосходство. [126] [127] [128] Авторы утверждают, что классическому современному суперкомпьютеру потребуется вычислительное время в 600 миллионов лет, чтобы сгенерировать количество выборок, которое их квантовый процессор может сгенерировать за 20 секунд. [129]
Заявления о квантовом превосходстве вызвали ажиотаж вокруг квантовых вычислений, [130] но они основаны на надуманных тестовых задачах, которые напрямую не подразумевают полезных реальных приложений. [95] [131]
Несмотря на большие надежды на квантовые вычисления, значительный прогресс в аппаратном обеспечении и оптимизм в отношении будущих приложений, в статье Nature в 2023 году современные квантовые компьютеры резюмировались как «На данный момент [годны] абсолютно ни для чего». [95] В статье уточняется, что квантовые компьютеры в любом случае еще не стали более полезными и эффективными, чем обычные компьютеры, хотя также утверждается, что в долгосрочной перспективе такие компьютеры, вероятно, будут полезны. В статье Communications of the ACM за 2023 год [96] было обнаружено, что нынешние алгоритмы квантовых вычислений «недостаточны для практического квантового преимущества без значительных улучшений в программно-аппаратном комплексе». В нем утверждается, что наиболее многообещающими кандидатами на достижение ускорения с помощью квантовых компьютеров являются «проблемы малых данных», например, в химии и материаловедении. Однако в статье также делается вывод, что широкий спектр рассмотренных потенциальных приложений, таких как машинное обучение, «не удастся достичь квантового преимущества с помощью существующих квантовых алгоритмов в обозримом будущем», и определены ограничения ввода-вывода, которые делают ускорение маловероятным. «Проблемы больших данных, неструктурированные линейные системы и поиск в базе данных на основе алгоритма Гровера».
Такое положение дел можно объяснить несколькими текущими и долгосрочными соображениями.
В частности, создание компьютеров с большим количеством кубитов может быть бесполезным, если эти кубиты недостаточно хорошо связаны и не могут поддерживать достаточно высокую степень запутанности в течение длительного времени. Пытаясь превзойти обычные компьютеры, исследователи квантовых вычислений часто ищут новые задачи, которые можно решить на квантовых компьютерах, но это оставляет возможность того, что в ответ будут разработаны эффективные неквантовые методы, как это видно на примере демонстрации квантового превосходства . Поэтому желательно доказать нижние границы сложности наилучших возможных неквантовых алгоритмов (которые могут быть неизвестны) и показать, что некоторые квантовые алгоритмы бессимптомно улучшают эти границы.
Некоторые исследователи выразили скептицизм по поводу возможности создания масштабируемых квантовых компьютеров, как правило, из-за проблемы поддержания согласованности в больших масштабах, но также и по другим причинам.
Билл Унру усомнился в практичности квантовых компьютеров в статье, опубликованной в 1994 году. [134] Пол Дэвис утверждал, что 400-кубитный компьютер даже вступит в конфликт с космологической информацией, связанной с голографическим принципом . [135] Скептики, такие как Гил Калаи, сомневаются, что квантовое превосходство когда-либо будет достигнуто. [136] [137] [138] Физик Михаил Дьяконов выразил скептицизм по поводу квантовых вычислений следующим образом:
Практический квантовый компьютер должен использовать физическую систему в качестве программируемого квантового регистра. [141] Исследователи изучают несколько технологий в качестве кандидатов на надежную реализацию кубитов. [142] Сверхпроводники и захваченные ионы являются одними из наиболее разработанных предложений, но экспериментаторы рассматривают и другие аппаратные возможности. [143]
Любая вычислительная задача, решаемая классическим компьютером, также может быть решена и квантовым компьютером. [144] Интуитивно это происходит потому, что считается, что все физические явления, включая работу классических компьютеров, можно описать с помощью квантовой механики , которая лежит в основе работы квантовых компьютеров.
И наоборот, любая задача, решаемая квантовым компьютером, также может быть решена и классическим компьютером. Можно смоделировать как квантовые, так и классические компьютеры вручную, используя всего лишь бумагу и ручку, если уделить достаточно времени. Более формально, любой квантовый компьютер можно смоделировать с помощью машины Тьюринга . Другими словами, квантовые компьютеры не предоставляют никаких дополнительных возможностей по сравнению с классическими компьютерами с точки зрения вычислительности . Это означает, что квантовые компьютеры не могут решать неразрешимые проблемы, такие как проблема остановки , и существование квантовых компьютеров не опровергает тезис Чёрча-Тьюринга . [145]
Хотя квантовые компьютеры не могут решить проблемы, которые уже не могут решить классические компьютеры, есть подозрение, что они могут решать некоторые проблемы быстрее, чем классические компьютеры. Например, известно, что квантовые компьютеры могут эффективно факторизовать целые числа , хотя считается, что это не относится к классическим компьютерам.
Класс задач , которые могут быть эффективно решены с помощью квантового компьютера с ограниченной ошибкой, называется BQP , что означает «ограниченная ошибка, квантовое, полиномиальное время». Более формально, BQP — это класс задач, которые могут быть решены с помощью квантовой машины Тьюринга с полиномиальным временем и вероятностью ошибки не более 1/3. Как класс вероятностных задач, BQP является квантовым аналогом BPP («ограниченная ошибка, вероятностное, полиномиальное время»), класса проблем, которые могут быть решены вероятностными машинами Тьюринга с полиномиальным временем и ограниченной ошибкой. [146] Это известно, и многие подозревают , что это интуитивно означает, что квантовые компьютеры более мощны, чем классические компьютеры, с точки зрения временной сложности . [147]
Точная связь BQP с P , NP и PSPACE неизвестна. Однако известно, что ; то есть все проблемы, которые могут быть эффективно решены с помощью детерминированного классического компьютера, также могут быть эффективно решены с помощью квантового компьютера, и все проблемы, которые могут быть эффективно решены с помощью квантового компьютера, также могут быть решены с помощью детерминированного классического компьютера с полиномиальными пространственными ресурсами. . Кроме того, предполагается, что BQP является строгим надмножеством P, а это означает, что существуют проблемы, которые эффективно решаются квантовыми компьютерами, но не могут быть эффективно решены детерминированными классическими компьютерами. Например, известно, что факторизация целых чисел и задача дискретного логарифма входят в BQP и предположительно находятся за пределами P. О взаимосвязи BQP и NP мало что известно, кроме того факта, что некоторые задачи NP, которые, как полагают, не входят в число P. P также находятся в BQP (например, целочисленная факторизация и задача дискретного логарифма находятся в NP). Есть подозрение, что ; то есть считается, что существуют эффективно проверяемые проблемы, которые невозможно эффективно решить с помощью квантового компьютера. Как прямое следствие этого убеждения также предполагается, что BQP не пересекается с классом NP-полных задач (если бы NP-полная задача находилась в BQP, то из NP-трудности следовало бы , что все задачи в NP находятся в БКП). [148]