company_banner

Квантовые цепи и вентили — вводный курс

https://blogs.msdn.microsoft.com/uk_faculty_connection/2018/02/26/quantum-gates-and-circuits-the-crash-course/
  • Перевод
  • Tutorial
Мы продолжаем цикл квантовых статей. Сегодня углубимся в формулы и поймем, как можно манипулировать кубитами — элементарными вычислительными единицами. Кроме того, рассмотрим принципы цепей и алгоритмов. Подробнее под катом!



Статьи из цикла:


  1. Квантовые вычисления и язык Q# для начинающих
  2. Введение в квантовые вычисления
  3. Квантовые цепи и вентили — вводный курс
  4. Основы квантовых вычислений: чистые и смешанные состояния
  5. Квантовая телепортация на языке Q#
  6. Квантовые вычисления: справочные материалы

Введение


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

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

Основы: квантовые состояния


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



Все они являются чистыми однокубитными состояниями, поэтому их можно представить в виде точек на сфере Блоха:



Теперь — четыре состояния Белла (их еще называют парами ЭПР, в честь Эйнштейна, Подольского и Розена — именно они являются авторами идей, которые впоследствии развил Белл). Это простейшие примеры квантовой запутанности двух кубитов:



И наконец, мы будем использовать так называемые состояния ГХЦ (Гринберга — Хорна — Цайлингера). Вот их общая форма (для n кубитов) и простейшая форма (для трех кубитов):



Состояния Белла и состояния ГХЦ очень важны, потому что их поведение кардинально отличается от предсказаний классической теории из-за уровня запутанности в таких системах (этот принцип «максимальной запутанности» будет рассмотрен в одной из последующих публикаций).

Основы: радианы


Углы поворота в теории квантовых вычислений измеряются в радианах. Полная окружность (360°) соответствует 2π радиан. Углы измеряются против часовой стрелки. Ниже показаны величины важнейших углов в градусах и в радианах.



Основы: диаграммы квантовых цепей


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

  • Время на квантовой диаграмме движется слева направо.
  • Каждому кубиту соответствует одиночная горизонтальная линия.
  • Вентили обычно обозначаются квадратами. Тип вентиля обозначается буквами или другими символами в этом квадрате (бывают и исключения из этого правила. Обычно это кубитные вентили, у которых есть классические аналоги (пример — вентиль NOT)).
  • Некоторым вентилям может соответствовать несколько элементов диаграммы (пример — вентиль NOT).
  • В результате измерения кубита все суперпозиции коллапсируют, квантовые свойства кубита исчезают, и он превращается в обычный бит. Поэтому можно считать, что измерительный элемент (показанный ниже) принимает на вход кубит и выдает классический бит. Этой операции в языке Q# соответствует команда Measure(bases: Pauli[], qubits: Qubit[]) или M(qubit: Qubit) по основанию Z.

Вот обозначения важнейших элементов:



Более подробная информация приводится в документации здесь и в книге М. Нильсена и И. Чанг «Квантовая информация и квантовые вычисления».

Однокубитные вентили


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

Самые элементарные однокубитные вентили — это вентили Паули X, Y и Z:
Названия Матричное представление Обозначения Представление в Q#
Вентиль Паули X, X, NOT, переключение бита,
X(qubit: Qubit)
Вентиль Паули Y, Y, Y(qubit: Qubit)
Вентиль Паули Z, Z, переключение фазы, Z(qubit: Qubit)
Вентиль X очень похож на классический вентиль NOT: он преобразует |0〉 в |1〉, а |1〉 в |0〉. Эта операция эквивалентна повороту вектора на сфере Блоха вокруг оси x на π радиан (или 180°).

Вентиль Y ожидаемо соответствует повороту вектора вокруг оси y на π радиан. В результате такой операции вектор |0〉 превращается в i|1〉, а |1〉 — в -i|0〉.

Вентиль Z представляет собой особый случай вентиля фазового сдвига (см. ниже) при фи = π = 180°. Он соответствует повороту вектора вокруг оси z на π радиан. Вектор |0〉 он оставляет без изменений, а |1〉 преобразует в -|1〉.

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



Важно отметить, что после двукратного применения одного и того же вентиля Паули к кубиту он перейдет в исходное состояние (потому что после поворота вектора на 2π радиан или 360° вокруг любой оси он перейдет в начальное положение). Как следствие,



Поскольку и т. д.,

Здесь II — обозначение единичной матрицы: . Единичной называется матрица, результат умножения которой на произвольную матрицу M (II) равен матрице M: MII = IIM = M. Единичная матрица соответствует квантовой операции, которая не меняет квантовое состояние. На сфере Блоха это выглядит так:



Ввиду этого отношения говорят, что матрица Паули в квадрате равна единичной матрице.
Ниже приводится описание еще нескольких важных однокубитных вентилей.
Названия Матричное представление Обозначения Представление в Q#
Вентиль Адамара, H H(qubit: Qubit)
Фазовый сдвиг, R1(theta: Double, qubit: Qubit)
В более общем случае
R(pauli: Pauli, theta: Double, qubit: Qubit)
Фазовый сдвиг,, S S(qubit: Qubit)
, T T(qubit: Qubit)
Вентиль Адамара особенно важен, потому что с его помощью можно создать суперпозицию состояний |0〉 и |1〉. Эту операцию проще всего визуализировать с помощью сферы Блоха как поворот вокруг оси x на π радиан (180°) с последующим поворотом вокруг оси y (по часовой стрелке) на π/2 радиан (90°):



Вентиль фазового перехода представляет достаточно общую операцию, у которой есть множество полезных применений. Самые распространенные его вариации — вентили сдвига фазы на π/4, π/8 и Паули-вентиль Z, для которых параметр фи равен π/2, π/4 и π соответственно. Пример фазового сдвига на сфере Блоха:



Многокубитные вентили


Многокубитные вентили выполняют операции над двумя или более кубитами. Один из простейших примеров — вентиль SWAP:
Названия Матричное представление Обозначения Представление в Q#
SWAP SWAP(qubit1: Qubit, qubit2: Qubit)
Вентиль SWAP меняет местами два входных кубита. Например, SWAP|0〉|1〉 = |1〉|0〉, а SWAP|0〉|0〉 = |0〉|0〉 (полная таблица истинности приводится в шпаргалке по цепям).

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

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



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



Обычные вентили в Q# можно преобразовать в управляющие с помощью ключевого слова Controlled, как описано здесь (в разделе «Controlled» в самом низу страницы). Например, вентиль CNOT (напомним, что вентиль NOT эквивалентен X-вентилю Паули) можно получить командой

(Controlled X)([control], (target))

где [control] — массив входных управляющих кубитов.

Ниже описаны другие распространенные управляемые вентили (мы выделили единичную матрицу красным, а матрицу исходного вентиля — синим, как выше):
Названия Матричное представление Обозначения Представление в Q#
CNOT CNOT(control: Qubit, target: Qubit)
или
(Controlled X)([control], (target));
CCNOT, вентиль Тоффоли CCNOT(control1: Qubit, control2: Qubit, target: Qubit)
или
(Controlled X)([control1; control2], target);
CSWAP, вентиль Фредкина (Controlled SWAP)([control], (target));

Универсальные наборы


Как мы уже упоминали в предыдущей публикации, вне зависимости от того, с помощью какой физической системы мы имитируем квантовый компьютер, должна иметься возможность реализовать «универсальный набор» вентилей. Это значит, что любая допустимая вычислительная операция в нашей системе должна быть преобразуема к конечной последовательности известных вентилей. Вот пример такого универсального набора: вентиль Адамара, вентиль фазового сдвига, вентиль CNOT и вентиль π⁄8.

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

Нас ждет еще много интересного!


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

Дополнительные ресурсы


Microsoft

262,98

Microsoft — мировой лидер в области ПО и ИТ-услуг

Поделиться публикацией
Комментарии 36
    0
    любое преобразование можно реализовать… можно имитировать любое физическое явление...
    Напоминает рисование совы из кругов.
    Начнём с простого как представить целое число. Как поделить одно число на другое с помощью имеющегося набора универсальных вентилей?
    quantumexperience.ng.bluemix.net/qx/editor
      +1
      1. Квантовый компьютер бессмыслено использовать для обычных вычислений. Это скорее сопроцессор к обычному компьютеру.
      2. Это цикл статей, а не одна статья, которая должна дать ответ на все вопросы.
      3. Но если это именно вопрос, то вот в этой статье можно найти частичный ответ arxiv.org/abs/1609.01241 и здесь arxiv.org/pdf/1609.01241.pdf
      0
      Начнем с основ — с обозначений некоторых распространенных...


      Похоже рано я обрадовался, что появилась статья, которая позволит мне быстро разобраться в квантовых вычислениях))
      0
      нда, квантовые вычисления это самое «понятное» что я вообще видел в ИТ.
      Вопрос — эти кубиты ведь нельзя реализовать обычной микроэлектроникой когда в микросхеме есть 2 ячейки связанные так что если одна 1 а другая 0, это было слишком легко, в чём тогда разница????
        +1
        Реализовать нельзя, смоделитьровать можно. Смысл в том, что кубиты подчиняются законам квантовой механики, что позволяет, используя специализирванные алгоритмы, существенно ускорять некторые типы задач. Собственно, когда Фейнман предложил идею квантового компьютера, одна из проблем, которую он должен решить — моделирование квантовых систем.

        Моделирование состояния N кубит на обычном компьютере требует 2^N обычных бит. Плюс требуется моделирование вентилей.

        Реальный прорыв теоретически должен наступить при доступности квантовых компьютеорв с 100+ вычислительных кубит. Притом, что на текущий моент для реализации 1 вычислительного кубита требуется 5-10 физических кубит, так как необходима коррекция ошибок.
          0
          Моделирование состояния N кубит на обычном компьютере требует 2^N обычных бит. Плюс требуется моделирование вентилей.

          откуда там 2^n битов когда все эти вентили ~ n?
          Почему это не эквивалентно обычным ячейкам на микросхеме соединённым всеми этими вентилями?
          И если там всё вероятностно, как снимается выход квантовой системы для получении точного результата, и не получается ли что результат вероятностный, то есть не факторизация числа а «вероятность» что числа так факторизированы?
            +1
            Состояние кубита описывается вероятностным распределением. До измерения он может находтся с определённой вероятностью в каждом из состояний. Поэтому 2^N коэффициентов — байт/слов, + какое-то количество на ветеля.

            Кубит ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D1%82

            1 кубит описываются состоянием -> a|0> + b|1>, где a и b — комплексные числа и |a|^2+|b|^2=1, 2 числа
            И да, результат измерения состояния кубита — вероятностный. |a|^2 — вероятность |0>, |b|^2 — вероятность |1>.

            2 кубита описываются состоянием -> a|00> + b|01> + c|10> + d|11> — 4 числа
            3 кубита -> a|000> + b|100>… + x|111> — 8 чисел

            Прочитайте начало серии habrahabr.ru/company/microsoft/blog/351622, возможно, появится понимание

            И требуются специальный алгоритмы для получения пользы от квантового компьютера, см. например, алгоритм Шора ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A8%D0%BE%D1%80%D0%B0
        0
        Полезная серия, спасибо за работу! Есть одна проблема — три сферы Блоха не масштабируются, как бы их увидеть крупнее? Может есть ссылка?!
        Вот под этим текстом: «Ниже работа этих преобразований проиллюстрирована с помощью сферы Блоха (ось вращения в каждом случае выделена красным; на картинку можно нажать, чтобы увеличить ее)»
        0
        А можно какие нибудь жизненные примеры, а не голую математику? Например: вот так эта задача решается классическими вычислениями, а вот так квантовыми, при этом вижно такие то преимущества.
          0

          Факторизации чисел на обычном компьютере и квантовой алгоритм Шора.

            0

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


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

              0

              Чтобы разложить число М на простые множители, используя количество кубиков О(log M), необходимо время О(log^3 M)

                +1
                Вот так ИИ, захвативший системы автокоррекции, даёт кубитам неожиданные ласковые имена…
                0

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

              0
              Для того чтобы составить матрицу любого управляющего вентиля, нужно дописать единичную матрицу в левом верхнем углу матрицы нужного вентиля, а все остальные ячейки заполнить нулями.
              Это называется тензорного домножить слева на I^n
                0
                Вот пример такого универсального набора: вентиль Адамара, вентиль фазового сдвига, вентиль CNOT и вентиль π⁄8.

                Поправьте плз, вроде достаточно генераторов SU(2) и любого запутывающего преобразования

                  0
                  Спасибо за комментарий! Но, это же пример, а не минимально достаточный набор.
                    0
                    Да, прошу извинить просто, хотелось бы услышать про выбор этого набора, м.б. его проще физически реализовать(про то что cnot уже физически реализован в различных моделях я слышал). Или может гейты высоких порядков через них проще выражать? Или просто проще для понимания в рамках этой серии статей?
                      0
                      Так как мы говорим о квантовом компьютере в отрыве от его физической реализации, так что здесь скорее речь идёт о понимании в рамках этой серии статей.
                  0
                  Да, в принципе если бы Microsoft предлагал какие-нибудь инстансы с Q# в azure или HPC бэкенд к нему сделал какой, то в принципе это сильно бы упростило жизнь людям которые занимаются квант-вычем ибо такое ощущение что сейчас каждая группа под каждую задачу пилят свою версию элементарных преобразований/моделей зашумления/кодов коррекции
                    0
                    Он уже анонсирован. Так что будет Azure симулятор.
                    0

                    Первое что смущает это оператор CNOT(q0,q1)


                    |q0.a|    | 1 0 0 0 |   | q0.a |
                    |q0.b|  = | 0 1 0 0 | * | q0.b |
                    |q1.a|    | 0 0 0 1 |   | q1.a |
                    |q1.b|    | 0 0 1 0 |   | q1.b |

                    Как получается (Controlled X)([control], (target)) в матрице этого нет.
                    получается q0=q0; q1=X(q1)
                    откуда controlled X


                    Вобщем смотрю hello world на 3 кубита https://www.youtube.com/watch?v=v7b4J2INq9c&t=88 и что-то не сростается. Чую подвох, но пока не могу сказать где.

                      +1
                      Посмотрите действие оператора на базовые состояния:
                      CNOT|00> = |00>
                      CNOT|01> = |01>
                      CNOT|10> = |11>
                      CNOT|11> = |10>
                      Теперь посмотрите на матрицу оператора, можно заметить что для состояния где контрольный кубит в 0, оператор действует как единичный.
                      Таким образом у оператора с контролем n кубитов идет блок I^n а в нижней клетке матрицы — собственно сам действующий оператор
                        0
                        Собственно это и не срастается. Нижний блок в матрице зависит от состояния первого вектора. И такая матрица не описывает оператор CNOT
                          0
                          Где не срастается? В нижней клетке матрицы описывается оператор действующий на неконтрольные кубиты в данном случае это оператор not он же sigma X именно его матрица и описана внизу, что там зависит от входного вектора. Почему вам кажется что такая матрица не описывается CNOT?
                        0
                        Вы неправильно трактуете матрицу. Это не «квадратики», применяемые последовательно к двум кубитам, как у вас нарисовано, а полная перепись всех возможных состояний. Двухкубитный вентиль — очень неудачный пример, ибо 2*2=2^2, и разница не сразу очевидна. Но обратите внимание на матрицу CCNOT: она имеет размер 8, а не 6, потому что применяется не к вектору (q0.a, q0.b, q1.a, q1.b, q2.a, q2.b), а к вектору (000, 001, 010, 011, 100, 101, 110, 111) — то есть перечисляются все базовые состояния всего многокубитного (трёхкубитного в данном случае) набора как единого целого, и матрица действует уже на этот комплект состояний.
                          0
                          Спасибо за комментарий. Теперь я вообще запутался.
                          Берём 3 кубита 8 состояний s0..s7 на базисе из 6 векторов.
                          s0 = |000> = {1,0,1,0,1,0}
                          s1 = |001> = {1,0,1,0,0,1}
                          s2 = |010> = {1,0,0,1,1,0}
                          s3 = |011> = {1,0,0,1,0,1}
                          s4 = |100> = {0,1,1,0,1,0}
                          s5 = |101> = {0,1,1,0,0,1}
                          s6 = |110> = {0,1,0,1,1,0}
                          s7 = |111> = {0,1,0,1,0,1}
                          Получается что половина состояний зависимые т.е.
                          s5= -s2+s3+s4
                          s7=-s0 +s3+s4
                          s6=-s0+s2 +s4
                          s1= s0-s2+s3
                          Как мы применяем матрицу CСNOT к зависимым состояниям s?
                            +1
                            Disclamer
                            Поскольку я «не волшебник, а только учусь», я могу в чём-то здорово наврать, в каковом случае нижайше прошу более подкованных товарищей растолковать, что и как.

                            Дело в том, что запись |000> — это не «состыковка» трёх «нулевых» векторов, а тензорное произведение, сокращённая запись для |0>⊗|0>⊗|0>. Тензорное произведение двух векторов (для трёх аналогично) переводит нас в пространство высшей размерности, в котором задаётся совершенно новый базис, построенный на основе всевозможных попарных комбинаций базисов исходных пространств. То есть из двух векторов размерности 2 мы получаем вектор размерности 4, следующего вида: (a, b) ⊗ (c, d) = (ac, ad, bc, bd). И прежние единичные векторы (1, 0) и (0, 1) из первого пространства плюс такая же пара из второго пространства будут задавать нам базис нашего нового пространства по следующим правилам (возможны перестановки, но суть не меняется):
                            (1,0)1 ⊗ (1,0)2 = (1,0,0,0)
                            (1,0)1 ⊗ (0,1)2 = (0,1,0,0)
                            (0,1)1 ⊗ (1,0)2 = (0,0,1,0)
                            (0,1)1 ⊗ (0,1)2 = (0,0,0,1)
                            Мы обозначаем эти четыре единичных вектора нового пространства как |00>, |01>, |10>, |11> исключительно для удобства и наглядности, чтобы было видно, какой вектор как был получен. Но это лишь один из вариантов обозначения, никто не мешает назвать их, скажем, |0>, |1>, |2>, |3>. Или |ψ1>, |ψ2>, |ψ3>, |ψ4>.

                            Так что никаких зависимостей нет, все эти 8 векторов — это самый что ни на есть полноценный ортонормированный базис трёхкубитного пространства состояний.
                              0
                              Спасибо. Теперь пазл сходится. Я брал Ψ=a0*φ0+b0*ψ0 + a1*φ1+b1*ψ1 + a2*φ2+b2*ψ2,
                              а надо было брать Ψ=(a0*φ0+b0*ψ0) * (a1*φ1+b1*ψ1) * (a2*φ2+b2*ψ2).
                              Но тогда возникает другой вопрос: Если эти состояния сидят в некоторых потенциальных ямах то эти частицы должны находиться рядом (в некоторой окрестности, в ядре например) иначе тензорное произведение будет экспоненциально стремиться к 0.
                                0
                                Здесь прокомментировать, увы, не смогу. Ничего не знаю о связи тензорного произведения и физического местоположения. Из общих соображений мне кажется, что в такой ситуации само местоположение должно тогда входить в описание состояния частицы, иначе откуда вообще возьмётся эта зависимость? А если его там нет — то это уже не наша головная боль, как там практическая реализация нам обеспечит взаимодействие.
                        0
                        Спасибо! А нейроночку еще никто не пробовал на кубитах делать? Чувствуется, по своей природе они где-то рядом. Это же идеально, а то чо мы эти матрицы перемножаем.

                        Как бы это могло выглядеть? В такой сети не будет «вычислений»? Т.е достаточно произвести измерение, и это будет результатом работы нейронки в этот момент?
                        0
                        Я пытался разобраться, как они в примерах переходят от гамильтонианов к вентилям. Это для моделирования всяких физических систем полезно, и не только. Пока не особо получается. С этим Q# ещё проблема, что там часть closed source и не всегда понятно какая.

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

                        Самое читаемое