Квантовое вычисление для начинающих

Квантовые вычисления понятный старт для новичков

Руководство по основам квантовых вычислений без необходимости предварительных знаний

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

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

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

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

• Центры обработки данных могут работать также хорошо с меньшим охлаждением
• Сокращение размерности с помощью Scikit-Learn теория и реализация метода главных компонент (PCA)
• 6 Волшебных команд для Jupyter Notebook в Python для науки о данных

Квантовые явления и квантовая информация

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

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

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

Спин часто определяется как присущий момент импульса. Вспомним, что в классической механике сила определена как изменение импульса. Кроме того, энергия системы определена в терминах движения или скорости изменения движения, что предполагает массу. В отличие от классической механики, особая теория относительности Эйнштейна приписывает внутреннюю энергию покоя массе через равенство E = mc². Подобно этому, внутренний момент импульса тесно связан с внутренним энергетическим состоянием субатомной частицы. Фактически, это свойство, которым обладают элементарные частицы, независимо от того, вращаются ли они или нет, то есть независимо от внешних факторов, таких как импульс и положение, отсюда и квалификатор “внутренний”. Как и классический момент импульса, квантовый спин меняется при вращениях. Однако, в отличие от классического момента импульса, спин квантуется, что означает, что он принимает только дискретный набор значений.

Максимальный спин элементарной частицы определяется произведением n (любого целого или полуцелого значения n/2) и приведенной постоянной Планка ℏ (h/2π). Все обычные частицы, называемые фермионами, имеют сверхполуцелый (1/2) спин, в то время как частицы-носители силы, известные как бозоны, такие как фотон, имеют целый (1) спин. И электроны, и фотоны имеют два возможных состояния спина: “вверх” или “вниз”. В математических терминах электроны будут иметь максимальный спин 1/2ℏ или -1/2ℏ, то есть спин в положительном или отрицательном “поворотах”. Фотон будет иметь максимальный спин 1ℏ и -1ℏ, так как он принимает целые значения спина. Несмотря на то, что мы используем слово “поворот”, лучше не думать об этом в терминах пространственных преобразований.

Теперь давайте рассмотрим странные квантовые свойства, которые будут использоваться для квантовых вычислений. Мы отметили ранее, что электрон может находиться в двух возможных состояниях спина, но в каком состоянии он находится в данный момент? В этом случае полезно провести различие между состоянием системы и измерением. В классической механике состояние и измерение совпадают полностью: состояние системы – это то, что вы измеряете. Но не в квантовой механике. Состояние системы без измерения задается когерентной суперпозицией волновых функций 𝛹i . После измерения состояние системы будет задано либо 𝛹↓, либо 𝛹↑, если мы измеряем одну частицу. Это различие между состоянием и измерением позволяет квантовым компьютерам выполнять операции, которые могут принимать бесконечные значения в двумерных комплексных векторных пространствах.

Наконец, измерения подчиняются определенным правилам относительно способа проведения измерения. В частности, направление измерения имеет значение для результата. Допустим, у нас есть два направления: вертикальное и горизонтальное. Если мы измеряем спин электрона в вертикальном направлении, мы получим состояние спина “вверх” или “вниз”. Если мы выполняем точно такое же измерение, то есть снова измеряем спин в вертикальном направлении, мы получим такой же результат. Это показывает, что есть экспериментальная установка, которая дает предсказуемые результаты. Однако, если мы сначала измерим спин электрона в вертикальном направлении, а затем в горизонтальном и повторим измерение, результаты будут случайной последовательностью спина “вверх” или “вниз”, равномерно распределенной между ними при достаточном количестве попыток. Это означает, что, если мы не будем осторожны, квантовые измерения могут давать случайные результаты. Целью квантовых алгоритмов будет контролировать операции так, чтобы мы получали желаемые результаты.

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

От квантовых явлений к квантовым вычислениям

Фундаментальная информационная единица классического компьютера называется битом, который имеет два дискретных состояния, обычно обозначаемых как 0 или 1. Поскольку компьютер – это физическая машина, эта математическая абстракция должна быть отображена на некоторое физическое явление. Классические компьютеры отображают эти дискретные состояния на потоки тока или напряжения. Когда напряжение низкое или близко к нулю, мы используем его для представления состояния 0, а когда напряжение выше, мы используем его для представления 1. Другими словами, модуляции амплитуд напряжения позволяют нам механически реализовать двоичную систему представления. Последовательности этих состояний с низким напряжением и высоким напряжением затем упорядочиваются в электрических схемах, которые моделируют логические операции, такие как AND, XOR и т. д., называемые логическими вентилями. Комбинации логических операций через электрические схемы затем используются для выполнения любого вычислимого алгоритма.

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

Это имеет своеобразное последствие: субатомные частицы нельзя описать как имеющие фиксированные положения и импульсы. Хотя мы можем попытаться одновременно описать эти переменные, есть физический масштаб, при котором точность нарушается таким образом, что знание импульса означает потерю информации о положении и наоборот. Этот физический масштаб называется планковским масштабом, обозначается символом h: 6.626070 · 10⁻³⁴ м²кг/с и представляет собой физический порог между классическими и квантовыми явлениями. На этом масштабе, опять же по всем экспериментальным данным, субатомные частицы занимают все свои возможные состояния одновременно. Из-за этого свойства мы можем описывать субатомные частицы только как вероятностные распределения всех их возможных состояний, описываемых уравнением Шредингера. Как мы уже указывали ранее, существует второе описание, называемое измерением. Перед измерением частица существует в состоянии суперпозиции, описываемом волновой функцией Шредингера. После измерения частица переходит к дискретному состоянию – одному положению или другому. Квантовые вычисления используют это особое свойство квантовой механики для выполнения вычислений, то есть пользуясь и состояниями суперпозиции, и состояниями измерения. (Если вы хотите более ясно разобраться в экспериментальных основах объективности суперпозиции, прочитайте это.)

Итак, если классический компьютер строит вычисления из двух возможных дискретных состояний, то мы можем считать квантовый компьютер также строящим вычисления из дискретных состояний, а также из суперпозиций. Кубит может находиться в состоянии 0 или 1 при измерении. Однако перед измерением кубит находится в суперпозиции 0 и 1. Во время суперпозиции кубит может занимать бесконечное количество состояний. Используя законы квантовой механики, квантовые вычисления превосходят вычислительные возможности классических вычислений, чье пространство состояний ограничено 2^n. Чтобы быть уверенными, измерение сокращает квантовые состояния до классических состояний, а именно, до того же пространства состояний 2^n. Тогда в чем заключается преимущество квантовых вычислений перед классическими вычислениями?

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

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

Представление кубитов: линейная алгебра

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

Мы представляем кубиты двумерными единичными векторами.

Что такое вектор?

Вектор представляет собой величину, выраженную как минимум двумя значениями: магнитудой и направлением. Магнитуда вектора определяется евклидовым расстоянием, а направление определяется начальной точкой. (1, -3), например, представляет собой двумерный вектор с длиной 3,162 и направлением, заданным значением x.

Что такое единичный вектор?

Единичный вектор – это вектор длиной или магнитудой, равной 1. Например, < 0,1 > – единичный вектор, потому что если мы вычислим евклидово расстояние, используя теорему Пифагора, мы получим значение 1.

Почему двумерные единичные векторы?

Поскольку существует два возможных значения измерения спина электрона, двумерное векторное пространство, обозначенное через ℝ², будет подходить. Мы используем единичные векторы, потому что мы хотим ограничить варианты измерения до двух возможных значений: 0 или 1. Как мы увидим, операции, которые мы будем выполнять над кубитами, приведут к вращениям на унитарной плоскости. Однако пространство возможных результатов должно включать все возможные вращения на трехмерной сфере, базовое пространство которой по-прежнему двумерно, обозначая два возможных значения измерений. Для этого мы представляем векторы в виде комплексных чисел, а не действительных чисел, обозначаемых комплексным векторным пространством ℂ². (Комплексные числа – это любые операции, включающие действительные числа и мнимые числа, где мнимое число i равно √-1) Для простоты мы пока ограничимся ℝ² и откажемся от комплексных чисел.

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

Ортогональность: Два вектора ортогональны, если и только если их произведение равно нулю: < a | b > = 0.

Мы можем убедиться, что любая n-мерная кета является ортонормированным базисом, если произведение матрицы A и ее транспонирования A^T равно единичной матрице In.

Обозначение скобкой

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

Столбцовые векторы называются бразами, а строковые векторы называются кетами, обозначаются следующим образом: <a| & |b>, где:

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

Внутреннее произведение выражается символом <a|b> и обозначает:

Однако, векторы одного и того же типа (браз или кет) и одинаковой размерности могут быть сложены.

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

Существует три ортонормальных базиса для спина:

При умножении бразов и кетов одного и того же спина мы получаем значение 1:

Наоборот, при умножении бразов и кетов противоположных спинов мы получаем значение 0:

Как видите, ортонормальные скобки-произведения дают нам измерения, которые моделируют двоичные результаты.

Первый базис, представленный стрелками вверх и вниз, называется стандартным базисом и соответствует вертикальному измерению спина, то есть измерению вдоль оси y. Второй базис, представленный стрелками вправо и влево, соответствует горизонтальному измерению спина, а именно измерению вдоль оси x. В общем случае, упорядоченные ортонормальные базисы представляют измерение спина в определенном направлении. Фактически, мы можем измерять спин под любым углом или в любом направлении 𝛳, и результаты будут сворачиваться в дискретный исход “спин вверх” или “спин вниз” в этом направлении, так как состояния спина могут быть только дискретными.

Квантовое состояние одного или нескольких кубитов будет представлено линейной комбинацией этих базисов. Векторы базиса, следовательно, будут представлять возможные результаты квантового состояния. Как мы уже сказали, состояние кубита может быть запрограммировано на основе спина электрона или фотона. До измерения частица или квантовое состояние будет находиться в суперпозиции, представленной линейной комбинацией базисов |b1> и |b2>, которая принимает форму c1|b1> + c2|b2>, где c1 и c2 – амплитуды вероятности. В силу возможности отрицательных амплитуд вероятности, только их квадратные значения используются для представления вероятностей результатов, где c1² + c2² = 1. В суперпозиции c1² и c2² будут иметь вероятность 0,5 каждый.

После измерения спин-состояние коллапсирует в одно из ортонормальных баз |b1> или |b2>. Вероятность коллапса в базис |b1> определяется как c1², а вероятность коллапса в базис |b2> определяется как c2². Если измерение коллапсирует в |b1>, то c1² будет равно 1 и c2² будет равно 0, и наоборот. Проще говоря, вектор базиса, умноженный на вероятность 1, будет представлять результат измерения.

В классическом вычислении несколько битов представлены тензорным произведением этих битов, обозначаемым следующим символом: ⊗

Мы сказали, что кеты [1,0] и [0,1] представляют стандартные базисы и, следовательно, являются аналогами 0 и 1 соответственно в классических битах. Мы также сказали, что любое квантовое состояние должно сохранять следующее равенство: c1² + c2² = 1. Мы называли это ограничение единичной меры (вторая аксиома теории вероятности), что означает, что все кеты должны быть единичными векторами в ℝ². Однако, поскольку реальные квантовые состояния частиц представлены комплексными числами, фактическое пространство состояний задается ℂ². Поэтому фактическое ограничение единичной меры задается равенством: ‖𝛼‖² + ‖β‖² = 1, где 𝛼 и β – комплексные числа и представляют вероятностные амплитуды.

Для представления состояний нескольких кубитов мы берем тензорное произведение наших стандартных базисов |0> и |1>. Обратите внимание, что произведение сохраняет ограничение единичной меры, независимо от количества объединенных кубитов.

Поскольку мы работаем в ℝ², мы можем эвристически представить пространство состояний кубита в двух измерениях (x,y) с помощью единичной окружности. Помните, что все операции будут выполняться над ортонормальными базисами, которые мы перечислили выше. Кроме того, все квантовые логические вентили будут представлены унитарными и, следовательно, ортогональными матрицами. Почему? Потому что умножение вектора на ортогональные матрицы производит повороты, сохраняя внутреннее произведение векторов. Это приводит к изометрическим преобразованиям в евклидовом пространстве.

Обратите внимание также на отрицательные знаки для каждого поворота на 180⁰. Отрицательные знаки помогают отличить эквивалентные выходы таким образом, что каждая операция в принципе может быть обратимой или обратимой. Все квантовые вычисления должны быть обратимыми для использования вычислительных возможностей квантовых состояний, а именно состояний суперпозиции и запутанности перед измерением. Как мы увидим позже, состояние суперпозиции (а также запутанность) наделяют квантовые вычисления преимуществами, которые ускользают от классического вычисления. В состоянии суперпозиции произвольное количество кубитов N одновременно занимает все возможные состояния. Если у нас есть 4 кубита, то образец будет иметь 2⁴ возможных состояний, но в суперпозиции все эти состояния будут получены одновременно. Вероятность коллапса в одно из этих состояний при измерении будет равномерно распределена по линейному сочетанию базисных векторов.

Линии на единичной окружности ниже представляют изменение состояния от входа к выходу с помощью операцией с вентилем Хадамара, который помещает кубиты в состояние суперпозиции и обратно. Из-за следующего равенства ‖𝛼‖² + ‖β‖² = 1, измерение всегда будет коллапсировать систему в отдельное классическое состояние, которое в нашем случае соответствует спину электрона или фотона. Операции с квантовыми вентилями, однако, изменяют состояние одного или нескольких кубитов, не коллапсируя волновую функцию.

Если мы применяем оператор инверсии бита, эквивалентный оператору NOT в классических вычислениях, это инвертирует значение состояния ввода. Например, кет |1> перевернется в кет |0>, указанный ниже переходом состояния от (0,1) к (1,0).

В то же время, ворота Хадамарда берут (0,1) на входе и выводят (1/√2,−1/√2), перемножая вход с следующей ортогональной или унитарной матрицей:

Если вас интересует, как именно меняется состояние, вот явное иллюстрирование умножения матрицы с использованием ворот Хадамарда на вход |1>:

Как работают ворота Хадамарда и в чем их особенность?

Обратите внимание, что операция инверсии бита соответствует повороту на 90⁰ на единичном круге, в то время как ворота Хадамарда соответствуют повороту на 180⁰. Важно помнить, что все квантовые ворота выполняются с помощью ортогональных или унитарных матриц, которые создают повороты вокруг начала координат. Ворота Хадамарда конкретно создают полу-повороты между осями x и y, которые соответствуют вероятностным амплитудам 0.5.

Заметьте также, что векторный вывод является вектором единичной длины, так как (1/√2, −1/√2) удовлетворяет следующей формуле ‖𝛼‖² + ‖β‖² = 1. Попробуйте произвести вычисление сами, подставив значения вывода вместо 𝛼 и β.

Представьте состояние кубита в некоторой точке на единичном круге как распределение вероятностных амплитуд от аналогов 0 и 1 к набору значений между ними, сохраняющих сумму равной единице. Ворота Хадамарда устанавливают это распределение точно в 50/50 исход. Иными словами, есть 50/50 шанс, что измерение приведет кубит к векторам состояния |0> или |1>. Это математический аналог состояния суперпозиции. Позже мы увидим, как суперпозицию можно использовать в вычислениях.

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

Квантовые логические ворота

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

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

Поэтому, есть два свойства, которые наиболее важны, когда речь идет о квантовых логических воротах: а) обратимость и б) универсальность. Универсальность относится к типу логического ворота, который может вычислять все возможные операции с битами. Самым известным универсальным воротом в классических вычислениях является NAND (НЕ И) представленный в таблице ниже:

Обратите внимание, что NAND является логическим дополнением для И. В самом деле, для выражения всех возможных логических утверждений, включая теоремы логики, достаточно двух логических операторов. Это известно как функциональная полнота. Поскольку NAND объединяет в себе НЕ и И в одну операцию, он соответствует функционально полному и, следовательно, универсальному логическому оператору и вороту. Для сравнения, давайте посмотрим на таблицу истинности для И:

В классических вычислениях большинство операций являются необратимыми. Например, если мы вводим последовательность 010011110 в большинство логических ворот и получаем другую двоичную последовательность на выходе, мы не сможем восстановить входную последовательность только по выходной последовательности. XOR и NAND являются необратимыми. Однако существуют ворота, позволяющие восстановить вход по выходу, такие как ворота CNOT (эквивалентные XOR, но обратимые), Hadamard и TOFFOLI. Среди них Hadamard и TOFFOLI отвечают критериям обратимости и универсальности. Однако существуют и другие ворота, которые отвечают этим условиям, например ворота FRIEDKIN. Мы сосредоточимся на первой тройке.

Теперь давайте рассмотрим два ворота, необходимые для большинства квантовых вычислений: CNOT и Hadamard. CNOT действует на два или более кубитов, связывая их. Ворота Hadamard действуют на один или более кубитов, помещая их в суперпозицию. Мы также рассмотрим третье ворота, ворота TOFFOLI, также известные как управляемые управляемым НЕ, которые являются универсальной версией ворот CNOT.

Для чего нужны ворота CNOT? Они позволяют связывать два входных кубита, выполняя обратимые операции инверсии бита. Ворота CNOT состоят из двух входов: управляющего и целевого. Когда управляющий бит равен 1, ворота CNOT инвертируют целевой вход. Когда управляющий бит равен 0, ворота CNOT ничего не делают. Таким образом, каждая комбинация выходных данных может быть прослежена только к одной и только одной комбинации входных данных.

В каком смысле ворота CNOT эквивалентны связыванию?

Давайте рассмотрим операцию, выполняемую воротами CNOT над кубитами |1> и |0>. Мы берем тензорное произведение двух кубитов и умножаем его на матрицу унитарного преобразования ворот CNOT, что приводит к преобразованию входного тензорного произведения из |10> в |11>. Почему? Потому что ворота CNOT инвертируют значение целевого кубита только тогда, когда управляющий кубит равен |1>.

Следовательно, если наш целевой кубит равен |1> вместо |0>, ворота CNOT предсказуемо инвертируют значение обратно в |0>:

Другими словами, CNOT является обратимым классическим эквивалентом XOR (исключающее ИЛИ).

Как мы упоминали ранее, ворота Хадамарда дают идеальное суперпозиционное состояние. Как они это делают? Взгляните на ортогональную матрицу ниже:

Если мы умножим матрицу на стандартную базу |0>, то получим следующее состояние: (1/√2, 1/√2), что эквивалентно (|0>+|1>)/√2. Наоборот, если мы умножим ее на |1>, получим (1/√2,−1/√2), что эквивалентно (|0>−|1>)/√2. Несмотря на то, что каждый вход конвертирует выход в равное распределение амплитуд вероятности, отрицательный знак позволяет нам различать входы (будь то |0> или |1>) и тем самым обеспечивает обратимую операцию.

В классическом мире каждое значение имеет 50/50 шанс на исход. Обратите внимание, что в нашем примере мы выполнили операцию на одном кубите. Как мы помещаем несколько кубитов в суперпозицию?

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

Ниже вы можете увидеть операцию на одном кубите, умножая |1> стандартной базы на матрицу Хадамарда:

Наконец, давайте взглянем на ворота TOFFOLI, также известные как ворота контролируемого-контролируемого НЕ (CCNOT). Ворота TOFFOLI идентичны воротам CNOT за исключением наличия дополнительной управляющей переменной. С двумя управляющими переменными ворота TOFFOLI используют 8×8 ортогональную матрицу для операций над тремя входными кубитами. Как CNOT, TOFFOLI создает квантовое запутывание и может использоваться для запутывания и развития кубитов.

Таблицы входов-выходов ворот TOFFOLI:

Зачем нам нужны ворота TOFFOLI, если у нас уже есть CNOT?

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

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

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

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

Классические биты – это частные случаи кубитов

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

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

Однако до сих пор мы ничего не сказали о квантовых алгоритмах. Как мы можем создать один?

Квантовые алгоритмы: Дойчев оракул

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

Первый алгоритм, который доказательно достигает этого, был разработан Дэвидом Дойчем в 1985 году и называется Дойчевым оракулом.

Предположим, у нас есть четыре функции f₀-f₃. Для каждого входа 0 или 1, f₀ выводит 0. Для каждого входа 0 или 1, f₁ выводит 0, если вход равен 0, и 1, если вход равен 1. Для каждого входа 0 или 1, f₂ выводит 1, если вход равен 0, и 0, если вход равен 1. Для каждого входа 0 или 1, f₃ выводит 1.

Мы можем называть функции f₀ и f₃ постоянными, поскольку они производят одинаковый вывод независимо от входа. И мы называем функции f₁-f₂ сбалансированными, так как они распределяют выводы взаимно обратным способом.

Тогда вопрос, который мы задаем, такой: если нам дается одна из этих функций случайным образом, сколько раз мы должны запросить алгоритм, чтобы определить, является ли функция постоянной или сбалансированной?

Ответ заключается в том, что классическое вычисление не может определить правильный ответ менее, чем за два запроса. Посмотрим, как это работает. У нас есть выбор из 0 или 1 в качестве входа. Если мы подаем вход 0, мы можем получить 0 или 1 в качестве вывода. Аналогично, если вход 1, мы можем получить 0 или 1 в качестве вывода. В обоих случаях мы не узнаем, был ли вывод произведен постоянной или сбалансированной функцией. Поэтому нам нужно запросить алгоритм второй раз, чтобы сделать правильное определение.

С помощью квантового алгоритма Дойча мы можем узнать правильный ответ с одним запросом. Для достижения этого мы используем вентиль Хадамара и управляющий кубит в дополнение к входному кубиту. Мы пропускаем наши входы через вентиль Хадамара. Помните, что H помещает кубит в состояние суперпозиции. Поэтому, если мы подаем пару |0> и |1>, мы получим следующие соответствующие состояния: (1/√2, 1/√2), (1/√2, −1/√2). Затем мы передаем целевой вентиль через случайную fₓ.

Поскольку Хадамара является обратимым, fₓ должен поместить наш кубит в одно из следующих состояний:

(1/√2) (|0>+|1>); (1/√2) (|0>−|1>); (−1/√2) (|0>−|1>); (−1/√2) (|0>+|1>)

Мы снова пропускаем контрольный кубит через Хадамара, чтобы развернуть суперпозицию. Поскольку операции обратимы, у нас есть следующие возможные результаты:

f₀ →|0>; f₁ →|1>; f₂ → −|1>; f₃ →−|0>

Это означает, что когда мы измеряем кубит в конце, если вывод является |0>, функция является постоянной, а если вывод является |1>, функция сбалансированная. Несмотря на то, что Дойчев оракул не имеет практического применения, он представляет собой мощный пример преимуществ квантовых перед классическими вычислениями.

Алгоритм Дойча-Йозы

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

Алгоритм Шора

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

Для работы алгоритма Шора требуется два регистра с 1024 и 2048 кубитами соответственно для факторизации числа из 1024 бит с 309 цифрами. Самое большое число, которое удалось факторизовать на данный момент, имеет длину 48 бит, что не удовлетворяет милестоуну RSA с полусоставным числом из 100 цифр. До сих пор ни один квантовый компьютер не справился с задачами чисел RSA, которые состоят из списка определенных больших чисел, имеющих только два простых множителя. Числа RSA используются в криптографии открытого ключа для защищенной передачи данных правительствами и финансовыми учреждениями.

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

Квантовое превосходство и будущее

Как мы сказали ранее, понятие квантового превосходства относится к способности квантовых компьютеров решать задачи, которые классически неразрешимы в разумные сроки. В принципе, классические компьютеры могут решать любые теоретически вычислимые алгоритмы. Проблема заключается в практике: ограниченная вычислительная мощность не позволяет им решать определенные задачи в полезный промежуток времени. И здесь квантовые компьютеры обещают сократить эту разницу. В 2019 году Google объявил, что смог достичь квантового превосходства своим компьютером Sycamore, имеющим 53 кубита. В своей статье в Nature под названием Квантовое превосходство с использованием программируемого сверхпроводящего процессора они утверждают, что Sycamore затратил 200 секунд на выполнение одного экземпляра квантовой схемы миллион раз, что, по их словам, займет классическому суперкомпьютеру 10000 лет. IBM ответил на последнее утверждение, заявив, что один из их суперкомпьютеров может выполнить эту задачу за 2,5 дня, подрывая претензии Google к финишной черте.

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

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

Литература

Bernhardt, Chris. Квантовые вычисления для всех. The MIT Press, 2020.

IBM представляет квантовый процессор с 400 кубитами и квантовую систему IBM Quantum System Two нового поколения. IBM Newsroom. (б.д.). https://newsroom.ibm.com/2022-11-09-IBM-Unveils-400-Qubit-Plus-Quantum-Processor-and-Next-Generation-IBM-Quantum-System-Two

Kaye, P., Laflamme, R., & Mosca, M. (2020). Введение в квантовые вычисления. Oxford University Press.

“Подавление шума” кубиты могут минимизировать ошибки в квантовых компьютерах. University of Chicago News. (н.д.). https://news.uchicago.edu/story/noise-cancelling-qubits-can-minimize-errors-quantum-computers#:~:text=As%20existing%20quantum%20computers%20are,to%20high%20rates%20of%20error.

Roush, W. (2020, 13 июля). Конфликт между Google и IBM о “квантовом превосходстве”. MIT Technology Review. https://www.technologyreview.com/2020/02/26/905777/google-ibm-quantum-supremacy-computing-feud/

Zubairy, Muhammad Suhail. Квантовая механика для начинающих: с применением квантовой коммуникации и квантовых вычислений. Oxford University Press, 2020.