Квантовая схема - Quantum circuit

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

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

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

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

Обратимые классические логические ворота

Большинство элементарных логических вентилей классического компьютера необратимы. Таким образом, например, для логического элемента И нельзя всегда восстановить два входных бита из выходного бита; например, если выходной бит равен 0, из этого мы не можем сказать, являются ли входные биты 01, 10 или 00.

Однако обратимые вентили в классических компьютерах легко создаются для битовых цепочек любой длины; более того, они действительно представляют практический интерес, поскольку необратимые ворота всегда должны увеличивать физическую энтропию . Обратимый вентиль - это обратимая функция для n- битных данных, которая возвращает n- битные данные, где n- битные данные представляют собой строку битов x ₁ , x ₂ , ..., x _n длины n . Набор n- битных данных - это пространство {0,1} ⁿ , которое состоит из 2 ⁿ строк , состоящих из нулей и единиц.

Более точно: п -разрядных обратимый ворот является взаимно однозначным отображением F из множества {0,1} ^п из п битовых данных на себя. Примером такого обратимого элемента f является отображение, которое применяет фиксированную перестановку к его входам. Из соображений практической инженерии обычно изучаются вентили только для малых значений n , например, n = 1, n = 2 или n = 3. Эти ворота легко описываются таблицами.

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

Квантовые вентили - это обратимые унитарные преобразования по крайней мере на одном кубите. Несколько кубитов, взятые вместе, называются квантовыми регистрами . Чтобы определить квантовые вентили , нам сначала нужно указать квантовую замену n- битных данных. Квантуется версия классического п битовое пространства {0,1} ^п является гильбертово пространство

${\ displaystyle H _ {\ operatorname {QB} (n)} = \ ell ^ {2} (\ {0,1 \} ^ {n}).}$

Это по определению пространство комплекснозначных функций на {0,1} ⁿ и, естественно, внутреннее пространство произведения . Это пространство также можно рассматривать как состоящее из линейных суперпозиций классических битовых строк. Обратите внимание, что H _{QB ( n )} - векторное пространство над комплексными числами размерности 2 ⁿ . Элементы этого пространства называются n -кубитами.

Используя Дирак кет обозначение, если х ₁ , х ₂ , ..., х _п являются классической битовой строкой, то

${\ displaystyle | x_ {1}, x_ {2}, \ cdots, x_ {n} \ rangle \ quad}$

- специальный n -кубит, соответствующий функции, которая отображает эту классическую битовую строку в 1 и отображает все остальные битовые строки в 0; эти 2 ⁿ специальных n -кубитов называются вычислительными базисными состояниями . Все n -кубиты представляют собой сложные линейные комбинации этих вычислительных базисных состояний.

Квантовые логические вентили, в отличие от классических логических вентилей, всегда обратимы. Требуется особый вид обратимой функции, а именно унитарное отображение, то есть линейное преобразование комплексного внутреннего продукта пространства, которое сохраняет эрмитово внутреннее произведение . П -qubit (обратим) квантовый вентиль является унитарным отображением U из пространства Н _{QB ( п )} из п -qubits на себя.

Обычно нас интересуют только вентили для малых значений n .

Обратимый n- битный классический логический вентиль приводит к обратимому n- битному квантовому вентилю следующим образом: каждому обратимому n- битному логическому элементу f соответствует квантовый вентиль W _f, определяемый следующим образом:

${\ Displaystyle W_ {f} (| x_ {1}, x_ {2}, \ cdots, x_ {n} \ rangle) = | f (x_ {1}, x_ {2}, \ cdots, x_ {n} ) \ rangle.}$

Обратите внимание, что W _f переставляет вычислительные базисные состояния.

Особое значение имеет управляемый вентиль НЕ (также называемый вентилем CNOT ) W _CNOT, определенный на квантованном 2 кубите. Другие примеры квантовых логических производных от классических являются воротами Toffoli и ворота Фредкина .

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

${\ Displaystyle P (\ varphi) = {\ begin {bmatrix} 1 & 0 \\ 0 & e ^ {i \ varphi} \ end {bmatrix}},}$

так

${\ Displaystyle P (\ varphi) | 0 \ rangle = | 0 \ rangle \ quad P (\ varphi) | 1 \ rangle = e ^ {i \ varphi} | 1 \ rangle.}$

Обратимые логические схемы

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

Чтобы объяснить этот процесс сборки, предположим, что у нас есть обратимый n- битный вентиль f и обратимый m- битный вентиль g . Объединение их вместе означает создание новой схемы путем подключения некоторого набора из k выходов f к некоторому набору из k входов g, как показано на рисунке ниже. На этом рисунке n = 5, k = 3 и m = 7. Результирующая схема также обратима и работает с n + m - k битами.

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

Обратите внимание, что каждая горизонтальная линия на изображении выше представляет либо 0, либо 1, но не эти вероятности. Поскольку квантовые вычисления обратимы, на каждом «шаге» количество строк должно совпадать с количеством входных строк. Кроме того, каждая входная комбинация должна быть сопоставлена ​​с одной комбинацией на каждом «шаге». Это означает, что каждая промежуточная комбинация в квантовой схеме является биективной функцией входа.

Теперь можно показать, что ворота Тоффоли - универсальные ворота . Это означает, что для любой обратимой классической n- битной схемы h мы можем построить классическую сборку вентилей Тоффоли указанным выше способом, чтобы создать ( n + m ) -битную схему f такую, что

${\ displaystyle f (x_ {1}, \ ldots, x_ {n}, \ underbrace {0, \ dots, 0}) = (y_ {1}, \ ldots, y_ {n}, \ underbrace {0, \ ldots, 0})}$

где имеется m обнуленных с недостаточным усилением входов и

${\ displaystyle (y_ {1}, \ ldots, y_ {n}) = h (x_ {1}, \ ldots, x_ {n})}$.

Обратите внимание, что конечный результат всегда имеет строку из m нулей в качестве вспомогательных битов. Никакого «мусора» никогда не производится, и поэтому это вычисление действительно является одним из тех, которые в физическом смысле не генерируют энтропию. Этот вопрос подробно освещен в статье Китаева.

В более общем смысле, любая функция f (биективная или нет) может быть смоделирована схемой вентилей Тоффоли. Очевидно, что если отображение не может быть инъективным , в какой-то момент моделирования (например, на последнем этапе) должен быть произведен какой-то «мусор».

Для квантовых схем может быть определен аналогичный состав вентилей кубитов. То есть, связанный с какой - либо классической сборки , как указано выше, мы можем производить обратимое квантовое цепь , когда вместо е мы имеем п -qubit ворота U и вместо г мы имеем м -qubit затвора W . См. Иллюстрацию ниже:

Тот факт, что соединение гейтов таким образом приводит к унитарному отображению на пространстве кубитов n + m - k , легко проверить. В реальном квантовом компьютере физическая связь между воротами является серьезной инженерной проблемой, поскольку это одно из мест, где может произойти декогеренция .

Существуют также теоремы универсальности для некоторых наборов хорошо известных вентилей; такая теорема универсальности существует, например, для пары, состоящей из одного кубитового фазового элемента U _θ, упомянутого выше (для подходящего значения θ), вместе с двухкубитным вентилем _CNOT W _CNOT . Однако теорема универсальности для квантового случая несколько слабее, чем для классического случая; он утверждает только, что любая обратимая схема на n- кубитах может быть сколь угодно хорошо аппроксимирована схемами, собранными из этих двух элементарных вентилей. Обратите внимание, что существует бесчисленное множество возможных фазовых вентилей с одним кубитом, по одному для каждого возможного угла θ, поэтому все они не могут быть представлены конечной схемой, построенной из { U _θ , W _CNOT }.

Квантовые вычисления

До сих пор мы не показали, как квантовые схемы используются для выполнения вычислений. Поскольку многие важные численные задачи сводятся к вычислению унитарное преобразование U на конечномерном пространстве (знаменитый дискретное преобразование Фурье является ярким примером), можно было бы ожидать , что некоторые квантовая схема может быть спроектирована для выполнения преобразования U . В принципе, нужно только подготовить n- кубитное состояние ψ как соответствующую суперпозицию вычислительных базисных состояний для входа и измерить выход U ψ. К сожалению, здесь есть две проблемы:

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

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

Теперь мы предлагаем математическую модель того, как квантовые схемы могут моделировать вероятностные, но классические вычисления. Рассмотрим схему U с r- кубитами и регистровым пространством H _{QB ( r )} . Таким образом, U - унитарное отображение

${\ displaystyle H _ {\ operatorname {QB} (r)} \ rightarrow H _ {\ operatorname {QB} (r)}.}$

Чтобы связать эту схему с классическим отображением на битовых строках, мы указываем

• Входной регистр X = {0,1} ^м от м (классические) бит.
• Выходной регистр Y = {0,1} ^п о л (классические) битов.

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

${\ displaystyle | {\ vec {x}}, 0 \ rangle = | x_ {1}, x_ {2}, \ cdots, x_ {m}, \ underbrace {0, \ dots, 0} \ rangle,}$

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

${\ displaystyle \ operatorname {Tr} \ left ({\ big |} | {\ vec {x}}, 0 \ rangle \ langle {\ vec {x}}, 0 | -S {\ big |} \ right) \ leq \ delta.}$

Аналогичным образом , выходной регистр пространство связано с регистром кубита путем направления Y оценивается наблюдаемой A . Обратите внимание, что наблюдаемые в квантовой механике обычно определяются в терминах проекционно-значных мер на R ; если переменная оказывается дискретной, проекционно-значная мера сводится к семейству {E _λ }, индексированному по некоторому параметру λ в пределах счетного множества. Аналогичным образом , Y оценивается наблюдаемой, может быть связан с семейством попарно ортогональных проекторов {Е _у } , индексированных элементами Y . такой, что

${\ displaystyle I = \ sum _ {y \ in Y} \ operatorname {E} _ {y}.}$

Данному смешанному состоянию S соответствует вероятностная мера на Y, заданная формулой

${\ displaystyle \ operatorname {Pr} \ {y \} = \ operatorname {Tr} (S \ operatorname {E} _ {y}).}$

Функция F : X → Y вычисляется схемой U : H _{QB ( r )} → H _{QB ( r )} с точностью до ε тогда и только тогда, когда для всех битовых цепочек x длины m

${\ displaystyle \ left \ langle {\ vec {x}}, 0 {\ big |} U ^ {*} \ operatorname {E} _ {F (x)} U {\ big |} {\ vec {x} }, 0 \ right \ rangle = \ left \ langle \ operatorname {E} _ {F (x)} U (| {\ vec {x}}, 0 \ rangle) {\ big |} U (| {\ vec {x}}, 0 \ rangle) \ right \ rangle \ geq 1- \ epsilon.}$

Теперь

${\ displaystyle \ left | \ operatorname {Tr} (SU ^ {*} \ operatorname {E} _ {F (x)} U) - \ left \ langle {\ vec {x}}, 0 {\ big |} U ^ {*} \ operatorname {E} _ {F (x)} U {\ big |} {\ vec {x}}, 0 \ right \ rangle \ right | \ leq \ operatorname {Tr} ({\ big |} | {\ vec {x}}, 0 \ rangle \ langle {\ vec {x}}, 0 | -S {\ big |}) \ | U ^ {*} \ operatorname {E} _ {F ( x)} U \ | \ leq \ delta}$

так что

${\ displaystyle \ operatorname {Tr} (SU ^ {*} \ operatorname {E} _ {F (x)} U) \ geq 1- \ epsilon - \ delta.}$

Теорема . Если ε + δ <1/2, то распределение вероятностей

${\ displaystyle \ operatorname {Pr} \ {y \} = \ operatorname {Tr} (SU ^ {*} \ operatorname {E} _ {y} U)}$

по Y может использоваться для определения F ( x ) с произвольно малой вероятностью ошибки путем мажоритарной выборки для достаточно большого размера выборки. В частности, возьмите k независимых выборок из распределения вероятностей Pr по Y и выберите значение, с которым согласны более половины выборок. Вероятность того, что значение F ( x ) будет выбрано более k / 2 раз, не менее

${\ displaystyle 1-e ^ {- 2 \ gamma ^ {2} k},}$

где γ = 1/2 - ε - δ.

Это следует из оценки Чернова .

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

• Обозначение абстрактного индекса
• Диаграммы углового момента (квантовая механика)
• Сложность схемы и BQP
• Матрица состояния продукта использует графическое обозначение Пенроуза.
• Спиновые сети
• Диаграмма трассировки

использованная литература

• Бихам, Эли ; Брассар, Жиль ; Кенигсберг, Дан; Мор, Таль (2004), "Квантовое вычисление без запутывания", Теоретическая информатика , 320 (1): 15-33, Arxiv : колич-фот / 0306182 , DOI : 10.1016 / j.tcs.2004.03.041 , МР  2060181.
• Фридман, Майкл Х .; Китаев, Алексей ; Ларсен, Майкл Дж .; Ван, Чжэнхань (2003), «Топологические квантовые вычисления», Бюллетень Американского математического общества , 40 (1): 31–38, arXiv : Quant-ph / 0101025 , doi : 10.1090 / S0273-0979-02-00964-3 , MR  1943131.
• Хирвенсало, Мика (2001), квантовые вычисления , серия Natural Computing, Берлин: Springer-Verlag, ISBN 3-540-66783-0, MR  1931238.
• Китаев, А.Ю. (1997), «Квантовые вычисления: алгоритмы и коррекция ошибок», УМН. Наук , 52 (6 (318)): 53–112, Bibcode : 1997RuMaS..52.1191K , doi : 10.1070 / RM1997v052n06ABEH002155 , MR  1611329.
• Нильсен, Майкл А .; Чуанг, Исаак Л. (2000), Квантовые вычисления и квантовая информация , Кембридж: Издательство Кембриджского университета, ISBN 0-521-63235-8, Руководство по ремонту  1796805.

внешние ссылки

• Q-circuit - это макро-пакет для рисования квантовых схем в LaTeX.
• Quantum Circuit Simulator (Davy Wybiral) - редактор и симулятор квантовых схем на основе браузера.
• Quantum Computing Playground - среда создания квантовых сценариев на основе браузера.
• Quirk - Quantum Circuit Toy - редактор и симулятор квантовых схем на основе браузера.