Необратимые квантовые вычисления.

История:

На протяжении многих лет области квантовой механики и информатики формировали отдельные академические сообщества. Современная квантовая теория была разработана в 1920–х годах для объяснения корпускулярно-волнового дуализма, наблюдаемого в атомных масштабах, а цифровые компьютеры появились в последующие десятилетия, чтобы заменить человеческие компьютеры для утомительных вычислений. Обе дисциплины имели практическое применение во время Второй мировой войны; компьютеры играли важную роль в криптографии военного времени, а квантовая физика имела важное значение для ядерной физики, используемой в Манхэттенском проекте.

Когда физики применили квантово-механические модели к вычислительным задачам и заменили цифровые биты на кубиты, области квантовой механики и информатики начали сближаться. В 1980 году Пол Бениофф представил квантовую машину Тьюринга, которая использует квантовую теорию для описания упрощенного компьютера. Когда цифровые компьютеры стали быстрее, физики столкнулись с экспоненциальным увеличением накладных расходов при моделировании квантовой динамики, что побудило Юрия Манина и Ричарда Фейнмана независимо предположить, что аппаратное обеспечение, основанное на квантовых явлениях, может быть более эффективным для компьютерного моделирования. В статье 1984 года Чарльз Беннет и Жиль Брассар применили квантовую теорию к протоколам криптографии и продемонстрировали, что квантовое распределение ключей может повысить информационную безопасность.

Питер Шор.

Затем появились квантовые алгоритмы для решения задач Oracle, такие как алгоритм Дойча в 1985 году, алгоритм Бернштейна–Вазирани в 1993 году, и алгоритм Саймона в 1994 году. Эти алгоритмы не решали практических задач, но математически продемонстрировали, что можно получить больше информации, запросив черный ящик с квантовым состоянием в суперпозиции, иногда называемый квантовым параллелизмом. Питер Шор разработал на основе этих результатов свои алгоритмы 1994 года для взлома широко используемых протоколов шифрования RSA и Диффи–Хеллмана, которые привлекли значительное внимание к области квантовых вычислений. В 1996 году алгоритм Гровера обеспечил квантовое ускорение для широко применимой задачи неструктурированного поиска. В том же году Сет Ллойд доказал, что квантовые компьютеры могут моделировать квантовые системы без экспоненциальных накладных расходов, присущих классическому моделированию, подтвердив гипотезу Фейнмана 1982 года.

На протяжении многих лет экспериментаторы конструировали небольшие квантовые компьютеры, используя захваченные ионы и сверхпроводники. В 1998 году двухкубитный квантовый компьютер продемонстрировал осуществимость технологии, и последующие эксперименты увеличили количество кубитов и снизили частоту ошибок.В 2019 году Google AI и NASA объявили, что они достигли квантового превосходства с помощью машины с 54 кубитами, выполняющей вычисления, которые невозможны для любого классического компьютера. Однако обоснованность этого утверждения все еще активно исследуется.

Теорема о пороге показывает, как увеличение числа кубитов может уменьшить количество ошибок, однако полностью отказоустойчивые квантовые вычисления остаются "довольно далекой мечтой". По мнению некоторых исследователей, зашумленные квантовые машины среднего масштаба (NISQ) могут найти специализированное применение в ближайшем будущем, но шум в квантовых вентилях ограничивает их надежность.

Инвестиции в исследования в области квантовых вычислений увеличились в государственном и частном секторах. Как резюмировала одна консалтинговая фирма,

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

Квантовая обработка информации:

Компьютерные инженеры обычно описывают работу современного компьютера в терминах классической электродинамики. В этих "классических" компьютерах некоторые компоненты (такие как полупроводники и генераторы случайных чисел) могут полагаться на квантовое поведение, но эти компоненты не изолированы от окружающей среды, поэтому любая квантовая информация быстро декогерируется. В то время как программисты могут полагаться на теорию вероятностей при разработке рандомизированного алгоритма, квантово-механические понятия, такие как суперпозиция и интерференция, в значительной степени не имеют отношения к анализу программ.

Квантовые программы, напротив, полагаются на точное управление когерентными квантовыми системами. Физики описывают эти системы математически, используя линейную алгебру. Комплексные числа моделируют амплитуды вероятности, векторы моделируют квантовые состояния, а матрицы моделируют операции, которые могут быть выполнены над этими состояниями. Таким образом, программирование квантового компьютера - это вопрос составления операций таким образом, чтобы результирующая программа вычисляла полезный результат в теории и была осуществима на практике.

Преобладающая модель квантовых вычислений описывает вычисления в терминах сети квантовых логических элементов. Эта модель представляет собой сложное линейно-алгебраическое обобщение булевых схем.

Квантовая информация.

Кубит служит базовой единицей квантовой информации. Они представляют собой систему с двумя состояниями, точно так же, как классический бит, за исключением того, что он может существовать в суперпозиции своих двух состояний. В каком-то смысле суперпозиция подобна распределению вероятностей по двум значениям. Однако на квантовые вычисления могут влиять сразу оба значения, необъяснимые любым состоянием по отдельности. В этом смысле "наложенный" кубит хранит оба значения одновременно.

Двумерный вектор математически представляет состояние кубита. Физики обычно используют обозначения Дирака по квантовой механике линейной алгебры, письма |ψ⟩ 'Кэт пси' на вектор с надписью ψ. Поскольку кубит представляет собой систему с двумя состояниями, любое состояние кубита принимает вид α|0⟩ + β|1⟩, где |0⟩ и |1⟩ являются стандартными базовыми состояниями, а α и β - амплитуды вероятности. Если α или β равны нулю, кубит фактически является классическим битом; когда оба отличны от нуля, кубит находится в суперпозиции. Такой вектор квантового состояния действует аналогично (классическому) вектору вероятности, с одним ключевым отличием: в отличие от вероятностей, амплитуды вероятности не обязательно являются положительными числами. Отрицательные амплитуды допускают разрушительную интерференцию волн.

Когда кубит измеряется на стандартной основе, результатом является классический бит. У рожденных правило, описываются нормы в квадрате соответствие между амплитуд и вероятностей—при измерении кубита α|0⟩ + β|1⟩, государство рушится в |0⟩ с вероятностью |α|2или |1⟩ с вероятностью |β|2. Любое допустимое состояние кубита имеет коэффициенты α и β такие, что |α|2 + |β|2 = 1. В качестве примера, измерение кубита |0⟩√2/1 + |1⟩√2/1 с равной вероятностью выдаст либо |0⟩, либо |1⟩.

Каждый дополнительный кубит удваивает размерность пространства состояний. В качестве примера, вектор |00⟩√2/1 + |01⟩√2/1 представляет собой двухкубитовое состояние, тензорное произведение кубита |0⟩ на кубит |0⟩√2/1 + |1⟩√2/1. Этот вектор обитает в четырехмерном векторном пространстве, охватываемом базисными векторами |00⟩, |01⟩, |10⟩ и |11⟩. Состояние Белла |00⟩√2/1 + |11⟩√2/1 невозможно разложить на тензорное произведение двух отдельных кубитов — два кубита запутаны, потому что их амплитуды вероятности коррелированы. В общем случае векторное пространство для n-кубитной системы является 2-n-мерным, и это затрудняет классическому компьютеру имитацию квантовой системы: представление 100-кубитной системы требует хранения 2100 классических значений.

Унитарные операторы.

Состоянием этой однокубитной квантовой памяти можно управлять, применяя квантовые логические элементы, аналогично тому, как классической памятью можно управлять с помощью классических логических элементов. Одним из важных элементов как для классических, так и для квантовых вычислений является элемент НЕ, который может быть представлен матрицей

$X:={\begin{pmatrix}0&1\\1&0\ end{pmatrix}}.$

Математически применение такого логического элемента к вектору квантового состояния моделируется с помощью

матричного умножения. Таким образом

$X|0\rangle =|1\rangle$ и $X|1\rangle =|0\rangle$ .

Математика однокубитных вентилей может быть расширена для работы с многокубитной квантовой памятью двумя важными способами. Один из способов - просто выбрать кубит и применить этот элемент управления к целевому кубиту, оставив оставшуюся часть памяти незатронутой. Другой способ - применить вентиль к его цели, только если другая часть памяти находится в желаемом состоянии. Эти два варианта можно проиллюстрировать на другом примере. Возможными состояниями двухкубитной квантовой памяти являются

$|00\rangle :={\begin{pmatrix}1\\0\\0\\0\ end{pmatrix}};\quad |01\rangle :={\begin{pmatrix}0\\1\\0\\0\ конец {pmatrix}};\quad |10\rangle :={\begin{pmatrix}0\\0\\1\\0\ конец{pmatrix}};\quad |11\rangle :={\begin{pmatrix}0\\0\\0\\1\ конец{pmatrix}}.$

Элемент CNOT затем может быть представлен с использованием следующей матрицы:

$\operatorname {CNOT} :={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\ end{pmatrix}}.$

Как математическое следствие этого определения, ${\textstyle \operatorname {CNOT} |00\rangle =|00\rangle }$ , ${\textstyle \operatorname {CNOT} |01\rangle =|01\rangle }$ ${\textstyle \operatorname {CNOT} |10\rangle =|11\rangle }$ , ${\textstyle \operatorname {CNOT} |11\rangle =|10\rangle }$ и другими словами, CNOT применяет элемент НЕ ( ${\textstyle X}$ из предыдущего) ко второму кубиту тогда и только тогда, когда первый кубит находится в состоянии ${\textstyle |1\rangle_ }$ . Если первый кубит ${\textstyle |0\rangle_ }$ , то ни с одним из кубитов ничего не делается.

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

Квантовый параллелизм.

Квантовый параллелизм относится к способности квантовых компьютеров вычислять функцию для нескольких входных значений одновременно. Этого можно достичь, подготовив квантовую систему в виде суперпозиции входных состояний и применив унитарное преобразование, которое кодирует оцениваемую функцию. Результирующее состояние кодирует выходные значения функции для всех входных значений в суперпозиции, позволяя вычислять несколько выходных данных одновременно. Это свойство является ключевым для ускорения многих квантовых алгоритмов.

Квантовое программирование.

Существует ряд моделей вычислений для квантовых вычислений, отличающихся базовыми элементами, на которые разложены вычисления.

Массив вентилей.

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

Любое квантовое вычисление (которое в приведенном выше формализме представляет собой любую унитарную матрицу размером $2^{n}\умножить на 2^{n}$ более $n$ кубитов) может быть представлено в виде сети квантовых логических элементов из довольно небольшого семейства элементов. Выбор семейства вентилей, который позволяет использовать эту конструкцию, известен как универсальный набор вентилей, поскольку компьютер, который может запускать такие схемы, является универсальным квантовым компьютером. Один общий такой набор включает в себя все однокубитные элементы управления, а также элемент CNOT сверху. Это означает, что любое квантовое вычисление может быть выполнено путем выполнения последовательности однокубитных элементов управления вместе с элементами CNOT. Хотя этот набор элементов бесконечен, его можно заменить конечным набором элементов, обратившись к теореме Соловея-Китаева.

Квантовые вычисления, основанные на измерениях.

Квантовый компьютер, основанный на измерениях, разлагает вычисления на последовательность измерений состояния Белла и однокубитных квантовых вентилей, применяемых к сильно запутанному начальному состоянию (кластерному состоянию), используя технику, называемую телепортацией квантовых вентилей.

Адиабатические квантовые вычисления.

Адиабатический квантовый компьютер, основанный на квантовом отжиге, разлагает вычисления на медленное непрерывное преобразование начального гамильтониана в конечный гамильтониан, основные состояния которого содержат решение.

Топологические квантовые вычисления.

Топологический квантовый компьютер разлагает вычисления на объединение любых элементов в двумерной решетке.

Квантовая машина Тьюринга.

Квантовая машина Тьюринга является квантовым аналогом машины Тьюринга. Было показано, что все эти модели вычислений — квантовые схемы, односторонние квантовые вычисления, адиабатические квантовые вычисления и топологические квантовые вычисления - эквивалентны квантовой машине Тьюринга; при идеальной реализации одного такого квантового компьютера он может имитировать все остальные с затратами не более полинома. Эта эквивалентность не обязательно должна выполняться для практических квантовых компьютеров, поскольку накладные расходы на моделирование могут быть слишком большими, чтобы быть практичными.

Информационные материалы:

Квантовая криптография открывает новые способы безопасной передачи данных; например, квантовое распределение ключей использует запутанные квантовые состояния для установления безопасных криптографических ключей. Когда отправитель и получатель обмениваются квантовыми состояниями, они могут гарантировать, что злоумышленник не перехватит сообщение, поскольку любое несанкционированное прослушивание нарушило бы хрупкую квантовую систему и внесло бы заметные изменения. С помощью соответствующих криптографических протоколов отправитель и получатель могут, таким образом, устанавливать общую личную информацию, устойчивую к перехвату.

Современные волоконно-оптические кабели могут передавать квантовую информацию на относительно короткие расстояния. Текущие экспериментальные исследования направлены на разработку более надежного оборудования (такого как квантовые повторители) в надежде масштабировать эту технологию до квантовых сетей на большие расстояния со сквозной запутанностью. Теоретически это могло бы обеспечить новые технологические приложения, такие как распределенные квантовые вычисления и улучшенное квантовое зондирование.

Алгоритмы:

Прогресс в поиске квантовых алгоритмов обычно фокусируется на этой модели квантовой схемы, хотя существуют исключения, такие как квантовый адиабатический алгоритм. Квантовые алгоритмы можно грубо классифицировать по типу ускорения, достигнутого по сравнению с соответствующими классическими алгоритмами.

Квантовые алгоритмы, которые предлагают более чем полиномиальное ускорение по сравнению с наиболее известным классическим алгоритмом, включают алгоритм Шора для разложения на множители и связанные с ним квантовые алгоритмы для вычисления дискретных логарифмов, решения уравнения Пелла и, в более общем плане, решения проблемы скрытых подгрупп для абелевых конечных групп. Эти алгоритмы зависят от примитива квантового преобразования Фурье. Не было найдено математического доказательства того, что столь же быстрый классический алгоритм не может быть обнаружен, но факты свидетельствуют о том, что это маловероятно. Некоторые задачи Oracle, такие как задача Саймона и задача Бернштейна–Вазирани, дают доказуемое ускорение, хотя это в модели квантовых запросов, которая является ограниченной моделью, где нижние границы гораздо проще доказать и не обязательно приводит к ускорению решения практических задач.

В других задачах, включая моделирование квантовых физических процессов из химии и физики твердого тела, аппроксимацию некоторых полиномов Джонса и квантовый алгоритм для линейных систем уравнений, квантовые алгоритмы, по-видимому, дают суперполиномиальные ускорения и являются BQP-полными. Поскольку эти задачи являются BQP-полными, одинаково быстрый классический алгоритм для них подразумевал бы, что ни один квантовый алгоритм не дает суперполиномиального ускорения, что считается маловероятным.

Некоторые квантовые алгоритмы, такие как алгоритм Гровера и амплитудное усиление, дают полиномиальное ускорение по сравнению с соответствующими классическими алгоритмами. Хотя эти алгоритмы дают сравнительно скромное квадратичное ускорение, они широко применимы и, таким образом, ускоряют решение широкого круга задач.

Постквантовая криптография.

Заметным применением квантовых вычислений являются атаки на криптографические системы, которые используются в настоящее время. Факторизация целых чисел, которая лежит в основе безопасности криптографических систем с открытым ключом, считается вычислительно неосуществимой с помощью обычного компьютера для больших целых чисел, если они являются произведением нескольких простых чисел (например, произведений двух 300-значных простых чисел). Для сравнения, квантовый компьютер мог бы решить эту проблему экспоненциально быстрее, используя алгоритм Шора для нахождения его факторов. Эта способность позволила бы квантовому компьютеру взломать многие из криптографических систем, используемых сегодня, в том смысле, что для решения задачи использовался бы алгоритм за полиномиальное время (по числу цифр целого числа). В частности, большинство популярных шифров с открытым ключом основаны на сложности разложения целых чисел на множители или на задаче дискретного логарифмирования, обе из которых могут быть решены с помощью алгоритма Шора. В частности, алгоритмы RSA, Диффи–Хеллмана и эллиптической кривой Диффи–Хеллмана могут быть нарушены. Они используются для защиты защищенных веб-страниц, зашифрованной электронной почты и многих других типов данных. Их взлом будет иметь значительные последствия для конфиденциальности и безопасности электронной почты.

Идентификация криптографических систем, которые могут быть защищены от квантовых алгоритмов, является активно исследуемой темой в области постквантовой криптографии. Некоторые алгоритмы с открытым ключом основаны на задачах, отличных от задач целочисленной факторизации и дискретного логарифмирования, к которым применяется алгоритм Шора, например, криптосистема Макэлиса основана на задаче из теории кодирования. криптосистемы на основе решетки, как также известно, не могут быть взломаны квантовыми компьютерами, и поиск алгоритма за полиномиальное время для решения двугранной скрытых подгруппах, которая сломала бы многие криптосистемы на основе решетки, является хорошо изученной открытой проблемой. Было доказано, что применение алгоритма Гровера для взлома симметричного алгоритма (секретный ключ) методом грубой силы требует времени, равного примерно 2n/ 2 вызова базового криптографического алгоритма, по сравнению с примерно 2n в классическом случае, что означает, что длины симметричных ключей эффективно сокращаются вдвое: AES-256 будет иметь такую же защиту от атаки с использованием алгоритма Гровера, какую AES-128 имеет против классического перебора методом грубой силы.

Проблемы поиска.

Наиболее известным примером задачи, допускающей полиномиальное квантовое ускорение, является неструктурированный поиск, который включает в себя поиск помеченного элемента из списка $n$ элементов в базе данных. Это может быть решено с помощью алгоритма Гровера, использующего $O({\sqrt {n}})$ запросы к базе данных, которые в квадратичном размере меньше, чем $\Omega (n)$ запросы, требуемые для классических алгоритмов. В этом случае преимущество не только доказуемо, но и оптимально: было показано, что алгоритм Гровера дает максимально возможную вероятность нахождения нужного элемента при любом количестве запросов oracle. Многие примеры доказуемого квантового ускорения задач с запросами основаны на алгоритме Гровера, включая алгоритм Брассара, Хейера и Таппа для поиска коллизий в функциях два к одному и алгоритм Фархи, Голдстоуна и Гутмана для оценки деревьев NAND.

Проблемы, которые могут быть эффективно решены с помощью алгоритма Гровера, обладают следующими свойствами:

В коллекции возможных ответов нет структуры с возможностью поиска,
Количество возможных ответов для проверки совпадает с количеством входных данных в алгоритм, и
Существует булева функция, которая оценивает каждый входной сигнал и определяет, является ли он правильным ответом

Для задач со всеми этими свойствами время выполнения алгоритма Гровера на квантовом компьютере измеряется как квадратный корень из числа входных данных (или элементов в базе данных), в отличие от линейного масштабирования классических алгоритмов. Общий класс задач, к которым может быть применен алгоритм Гровера, - это булева задача о выполнимости, где база данных, через которую выполняется итерация алгоритма, содержит все возможные ответы. Примером и возможным применением этого является взломщик паролей, который пытается угадать пароль. Взлом симметричных шифров с помощью этого алгоритма представляет интерес для правительственных учреждений.

Моделирование квантовых систем.

Поскольку химия и нанотехнологии основаны на понимании квантовых систем, а такие системы невозможно эффективно моделировать классическим способом, квантовое моделирование может быть важным приложением квантовых вычислений. Квантовое моделирование также может быть использовано для моделирования поведения атомов и частиц в необычных условиях, таких как реакции внутри коллайдера. В июне 2023 года компьютерные ученые IBM сообщили, что квантовый компьютер дает лучшие результаты при решении физических задач, чем обычный суперкомпьютер.

Около 2% годовой мировой выработки энергии используется для азотфиксации с получением аммиака для процесса Хабера в промышленности сельскохозяйственных удобрений (хотя встречающиеся в природе организмы также производят аммиак). Квантовое моделирование может быть использовано для понимания этого процесса и повышения энергоэффективности производства. Ожидается, что ранним применением квантовых вычислений будет моделирование, повышающее эффективность процесса Хабера–Боша к середине 2020-х годов, хотя некоторые предсказывали, что это займет больше времени.

Квантовый отжиг.

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

Машинное обучение.

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

Например, квантовый алгоритм для линейных систем уравнений, или "Алгоритм HHL", названный в честь его первооткрывателей Харроу, Хасидима и Ллойда, как полагают, обеспечивает ускорение по сравнению с классическими аналогами. Недавно некоторые исследовательские группы изучили использование аппаратных средств квантового отжига для обучения машин Больцмана и глубоких нейронных сетей.

Модели глубокой генеративной химии становятся мощными инструментами для ускорения открытия лекарств. Однако огромные размеры и сложность структурного пространства всех возможных молекул, подобных лекарственным средствам, создают значительные препятствия, которые в будущем могут быть преодолены с помощью квантовых компьютеров. Квантовые компьютеры, естественно, хороши для решения сложных квантовых задач со многими телами и, таким образом, могут сыграть важную роль в приложениях, связанных с квантовой химией. Следовательно, можно ожидать, что квантово-расширенные генеративные модели, включая квантовые GAN, в конечном итоге могут быть развиты в окончательные генеративные химические алгоритмы.

Инженерия:

По состоянию на 2023 год классические компьютеры превосходят квантовые компьютеры во всех реальных приложениях. Хотя современные квантовые компьютеры могут ускорить решение конкретных математических задач, они не дают никаких вычислительных преимуществ для практических задач. Ученые и инженеры изучают множество технологий для аппаратного обеспечения квантовых вычислений и надеются разработать масштабируемые квантовые архитектуры, но остается несколько препятствий.

Проблемы.

При создании крупномасштабного квантового компьютера возникает ряд технических проблем. Физик Дэвид ДиВинченцо перечислил эти требования к практическому квантовому компьютеру:

Физически масштабируемые для увеличения числа кубитов

Кубиты, которые могут быть инициализированы произвольными значениями

Квантовые вентили, которые быстрее времени декогеренции

Набор универсальных вентилей

Кубиты, которые можно легко прочитать.

Найти запчасти для квантовых компьютеров также очень сложно. Для сверхпроводящих квантовых компьютеров, подобных тем, что созданы Google и IBM, необходим гелий-3, побочный продукт ядерных исследований, и специальные сверхпроводящие кабели, производимые только японской компанией Coax Co.

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

Декогеренция.

Одной из самых больших проблем, связанных с созданием квантовых компьютеров, является контроль или устранение квантовой декогеренции. Обычно это означает изоляцию системы от ее окружения, поскольку взаимодействие с внешним миром приводит к декогеренции системы. Однако существуют и другие источники декогеренции. Примеры включают квантовые вентили, а также колебания решетки и фоновое термоядерное вращение физической системы, используемой для реализации кубитов. Декогеренция необратима, поскольку она фактически неунитарна и обычно является чем-то, что следует строго контролировать, если не избегать. Время декогеренции для систем-кандидатов, в частности, время поперечной релаксации T2 (для технологий ЯМР и МРТ, также называемое временем дефазирования), обычно составляет от наносекунд до секунд при низкой температуре. В настоящее время некоторые квантовые компьютеры требуют, чтобы их кубиты охлаждались до 20 милликельвинов (обычно с использованием холодильника для разбавления), чтобы предотвратить значительную декогеренцию. Исследование 2020 года утверждает, что ионизирующее излучение, такое как космические лучи, тем не менее, может привести к декогеренции определенных систем в течение миллисекунд.

В результате трудоемкие задачи могут привести к неработоспособности некоторых квантовых алгоритмов, поскольку попытки поддерживать состояние кубитов в течение достаточно длительного времени в конечном итоге приведут к повреждению суперпозиций.

Эти проблемы сложнее для оптических подходов, поскольку временные рамки на порядки короче, и часто упоминаемым подходом к их преодолению является оптическое формирование импульсов. Частота ошибок обычно пропорциональна отношению времени работы ко времени декогеренции, следовательно, любая операция должна быть завершена намного быстрее, чем время декогеренции.

Как описано в теореме о пороге, если частота ошибок достаточно мала, считается возможным использовать квантовую коррекцию ошибок для подавления ошибок и декогеренции. Это позволяет общему времени вычисления превышать время декогеренции, если схема исправления ошибок может исправлять ошибки быстрее, чем их вносит декогеренция. Часто приводимая цифра для требуемого уровня ошибок в каждом элементе для отказоустойчивых вычислений составляет 10-3, предполагая, что шум деполяризуется.

Выполнение этого условия масштабируемости возможно для широкого спектра систем. Однако использование исправления ошибок влечет за собой стоимость значительно увеличенного количества требуемых кубитов. Число, необходимое для факторизации целых чисел с использованием алгоритма Шора, по-прежнему является полиномиальным и, как считается, находится между L и L2, где L - количество цифр в числе, подлежащем факторизации; алгоритмы исправления ошибок увеличили бы это число на дополнительный коэффициент L. Для 1000-битного числа это подразумевает необходимость примерно 104 бита без исправления ошибок. С исправлением ошибок это число увеличилось бы примерно до 107 бит. Время вычисления составляет около L2 или около 107 шагов, а частота 1 МГц - около 10 секунд. Однако накладные расходы на кодирование и исправление ошибок увеличивают размер реального отказоустойчивого квантового компьютера на несколько порядков. Тщательные оценки показывают, что по крайней мере 3 миллиона физических кубитов будут составлять 2048-битное целое число за 5 месяцев на квантовом компьютере с полностью исправленными ошибками на захваченных ионах. Что касается количества физических кубитов, то на сегодняшний день это остается наименьшей оценкой для практически полезной задачи целочисленной факторизации размером 1024 бита или больше.

Другой подход к проблеме стабильности-декогеренции заключается в создании топологического квантового компьютера с анионами, квазичастицами, используемыми в качестве потоков и опирающимися на теорию кос для формирования стабильных логических элементов.

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

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

В октябре 2019 года Google AI Quantum с помощью НАСА стал первым, кто заявил, что достиг квантового превосходства, выполнив вычисления на квантовом компьютере Sycamore более чем в 3 000 000 раз быстрее, чем их можно было бы выполнить на Summit, который обычно считается самым быстрым компьютером в мире. Впоследствии это утверждение было оспорено: IBM заявила, что Summit может выполнять выборки намного быстрее, чем заявлено,, и с тех пор исследователи разработали более совершенные алгоритмы для задачи выборки, используемые для утверждения о квантовом превосходстве, что существенно сокращает разрыв между Sycamore и классическими суперкомпьютерами и даже превосходит его.

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

Скептицизм.

Несмотря на большие надежды на квантовые вычисления, значительный прогресс в аппаратном обеспечении и оптимизм в отношении будущих приложений, по состоянию на 2023 год квантовые компьютеры "ни на что не годны", согласно статье в spotlight от Nature. Другими словами, обычные компьютеры в настоящее время более эффективны для практического использования. В статье 2023 Communications of the ACM от 2023 года делаются аналогичные выводы. Такое положение дел можно объяснить несколькими текущими и долгосрочными соображениями.

Обычные компьютерные аппаратные средства и алгоритмы не только оптимизированы для практических задач, но и продолжают быстро совершенствоваться, особенно ускорители на GPU.

Современное оборудование для квантовых вычислений создает лишь ограниченное количество запутанности, прежде чем его перегружает шум, и не исключает практического моделирования на обычных компьютерах, возможно, за исключением надуманных случаев.

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

Некоторые многообещающие алгоритмы были "деквантованы", то есть были найдены их неквантовые аналоги с аналогичной сложностью.

Если квантовая коррекция ошибок используется для масштабирования квантовых компьютеров до практических применений, ее накладные расходы могут подорвать ускорение, предлагаемое многими квантовыми алгоритмами.

Анализ сложности алгоритмов иногда приводит к абстрактным предположениям, которые не выполняются в приложениях. Например, входные данные могут быть еще недоступны, закодированные в квантовых состояниях, а "функции Oracle", используемые в алгоритме Гровера, часто имеют внутреннюю структуру, которую можно использовать для более быстрых алгоритмов.

В частности, построение компьютеров с большим количеством кубитов может оказаться бесполезным, если эти кубиты недостаточно хорошо связаны и не могут поддерживать достаточно высокую степень запутанности в течение длительного времени. Пытаясь превзойти обычные компьютеры, исследователи квантовых вычислений часто ищут новые задачи, которые могут быть решены на квантовых компьютерах, но это оставляет возможность того, что в ответ будут разработаны эффективные неквантовые методы, как видно из демонстраций квантового превосходства. Поэтому желательно доказать нижние границы сложности наилучших возможных неквантовых алгоритмов (которые могут быть неизвестны) и показать, что некоторые квантовые алгоритмы асимптоматически улучшают эти границы.

Некоторые исследователи выражают скептицизм в отношении возможности создания масштабируемых квантовых компьютеров, как правило, из-за проблемы поддержания согласованности в больших масштабах, но также и по другим причинам.

Билл Унру усомнился в практичности квантовых компьютеров в статье, опубликованной в 1994 году. Пол Дэвис утверждал, что компьютер с 400 кубитами даже вступит в конфликт с космологической информацией, связанной с голографическим принципом. Такие скептики, как Гил Калаи, сомневаются, что квантовое превосходство когда-либо будет достигнуто. Физик Михаил Дьяконов выразил скептицизм по поводу квантовых вычислений следующим образом:

"Таким образом, количество непрерывных параметров, описывающих состояние такого полезного квантового компьютера в любой данный момент, должно составлять ... около 10300... Сможем ли мы когда-нибудь научиться управлять более чем 10300 непрерывно изменяющимися параметрами, определяющими квантовое состояние такой системы? Мой ответ прост. Нет, никогда"

Кандидаты на физическую реализацию.

Практический квантовый компьютер должен использовать физическую систему в качестве программируемого квантового регистра. Исследовательские группы изучают несколько технологий в качестве кандидатов на высококачественную реализацию кубитов.

Сверхпроводящие квантовые вычисления (кубит, реализуемый состоянием нелинейных резонансных сверхпроводящих цепей, содержащих джозефсоновские переходы)

Квантовый компьютер с захваченными ионами (кубит, реализуемый внутренним состоянием захваченных ионов)

Нейтральные атомы в оптических решетках (кубит, реализуемый внутренними состояниями нейтральных атомов, захваченных в оптической решетке)

Компьютер на квантовых точках, основанный на вращении (например, квантовый компьютер Лосса-Дивинченцо) (кубит, заданный спиновыми состояниями захваченных электронов)

Компьютер на квантовых точках, основанный на пространстве (кубит определяется положением электрона в двойной квантовой точке)

Квантовые вычисления с использованием спроектированных квантовых ям, которые в принципе могли бы позволить построить квантовый компьютер, работающий при комнатной температуре

Связанный квантовый провод (кубит, реализованный парой квантовых проводов, соединенных квантовым точечным контактом)

Квантовый компьютер с ядерным магнитным резонансом (NMRQC), основанный на ядерном магнитном резонансе молекул в растворе, где кубиты создаются ядерными спинами внутри растворенной молекулы и зондируются радиоволнами

Твердотельный ЯМР-квантовый компьютерКейна (кубит, реализованный в ядерном спиновом состоянии доноров фосфора в кремнии, в котором он находится)

Вибрационный квантовый компьютер (кубиты, реализованные путем вибрационных суперпозиций в холодных молекулах)

Квантовый компьютер с электронами на гелии (кубит - это спин электрона)

Квантовая электродинамика резонаторов (CQED) (кубит, определяемый внутренним состоянием захваченных атомов, соединенных с высокоточными резонаторами)

Молекулярный магнит (кубит, заданный спиновыми состояниями)

Квантовый компьютер на основе ЭПР на основе фуллеренов (кубит, основанный на электронном вращении атомов или молекул, заключенных в фуллерены) В fullerenes

Нелинейно-оптический квантовый компьютер (кубиты, реализуемые путем обработки состояний различных мод света как с помощью линейных, так и с помощью нелинейных элементов)

Линейный оптический квантовый компьютер (LOQC) (кубиты, реализуемые путем обработки состояний различных режимов света с помощью линейных элементов, например

зеркал, светоделителей и фазовращателей). Стал возможным квантовый микропроцессор на основе лазерной фотоники при комнатной температуре.

Квантовый компьютер на основе алмаза (кубит, реализованный электронным или ядерным спином азотно-вакантных центров в алмазе)

Квантовый компьютер на основе конденсата Бозе-Эйнштейна

Квантовый компьютер на основе транзисторов (струнные квантовые компьютеры с захватом положительных дырок с использованием электростатической ловушки)

Квантовый компьютер на основе неорганических кристаллов, легированных ионами редкоземельных металлов (кубит, реализуемый внутренним электронным состоянием примесей в оптических волокнах)

Квантовый компьютер на основе металло-подобных углеродных наносфер

Теория:

Вычислимость.

Любая вычислительная задача, решаемая классическим компьютером, также разрешима квантовым компьютером. Интуитивно это объясняется тем, что считается, что все физические явления, включая работу классических компьютеров, могут быть описаны с помощью квантовой механики, которая лежит в основе работы квантовых компьютеров.

И наоборот, любая задача, решаемая квантовым компьютером, также решаема классическим компьютером. Можно смоделировать как квантовые, так и классические компьютеры вручную, используя только бумагу и ручку, если дать им достаточно времени. Более формально, любой квантовый компьютер может быть смоделирован машиной Тьюринга. Другими словами, квантовые компьютеры не предоставляют дополнительных возможностей по сравнению с классическими компьютерами с точки зрения вычислимости. Это означает, что квантовые компьютеры не могут решать неразрешимые проблемы, такие как проблема остановки, и существование квантовых компьютеров не опровергает тезис Черча–Тьюринга.

Сложность.

Хотя квантовые компьютеры не могут решить никаких проблем, которые классические компьютеры уже не могут решить, есть подозрение, что они могут решать определенные проблемы быстрее, чем классические компьютеры. Например, известно, что квантовые компьютеры могут эффективно множить целые числа, в то время как считается, что это не относится к классическим компьютерам.

Класс задач, которые могут быть эффективно решены квантовым компьютером с ограниченной погрешностью, называется BQP, что означает "ограниченная ошибка, квантовое, полиномиальное время". Более формально, BQP - это класс задач, которые могут быть решены с помощью квантовой машины Тьюринга за полиномиальное время с вероятностью ошибки не более 1/3. Как класс вероятностных задач, BQP является квантовым аналогом BPP ("ограниченная ошибка, вероятностное, полиномиальное время"), класса задач, которые могут быть решены с помощью вероятностных машин Тьюринга за полиномиальное время с ограниченной ошибкой. Это известно ${\mathsf {BPP\subseteq BQP}}$ и широко распространено подозрение, что ${\mathsf {BQP\subsetneq BPP}}$ , что интуитивно означало бы, что квантовые компьютеры более мощные, чем классические компьютеры с точки зрения временной сложности.

Точная связь BQP с P, NP и PSPACE неизвестна. Однако известно, что ${\mathsf {P\subseteq BQP\subseteq PSPACE}}$ ; то есть все проблемы, которые могут быть эффективно решены детерминированным классическим компьютером, также могут быть эффективно решены квантовым компьютером, и все проблемы, которые могут быть эффективно решены квантовым компьютером, также могут быть решены детерминированным классическим компьютером с ресурсами полиномиального пространства. Далее предполагается, что BQP является строгим надмножеством P, что означает, что существуют проблемы, которые эффективно решаются квантовыми компьютерами и которые неэффективны для детерминированных классических компьютеров. Например, известно, что задача о целочисленной факторизации и задача о дискретном логарифме относятся к BQP и предположительно находятся за пределами P. О связи BQP с NP известно мало, кроме того факта, что некоторые NP-задачи, которые, как считается, не относятся к P, также относятся к BQP (например, целочисленная факторизация и задача о дискретном логарифме относятся к NP). Предполагается, что ${\mathsf {NP\nsubseteq BQP}}$ ; то есть считается, что существуют эффективно проверяемые задачи, которые не могут быть эффективно решены квантовым компьютером. Как прямое следствие этого убеждения, также предполагается, что BQP не пересекается с классом NP-полных задач (если бы NP-полная задача была в BQP, то из NP-твердости следовало бы, что все задачи в NP находятся в BQP).

Предполагалось, что дальнейшие достижения в физике могут привести к созданию еще более быстрых компьютеров. Например, было показано, что квантовый компьютер с нелокальной скрытой переменной, основанный на механике Бома, может реализовать поиск в базе данных из N элементов не более чем за $O({\sqrt[{3}]{N}})$ несколько шагов, что является небольшим ускорением по сравнению с алгоритмом Гровера, который выполняется $O({\sqrt {N}})$ поэтапно. Обратите внимание, однако, что ни один из методов поиска не позволил бы квантовым компьютерам решать NP-полные задачи за полиномиальное время. Теории квантовой гравитации, такие как М-теория и петлевая квантовая гравитация, могут позволить создавать еще более быстрые компьютеры. Однако определение вычислений в этих теориях является открытой проблемой из-за проблемы времени; то есть в рамках этих физических теорий в настоящее время нет очевидного способа описать, что значит для наблюдателя отправлять входные данные в компьютер в один момент времени, а затем получать выходные данные в более поздний момент времени.

2005 год — Необратимые квантовые вычисления.