Квантовая схема

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

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

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

Элементарные логические элементы классического компьютера, кроме элемента НЕ , необратимы . Таким образом, например, для логического элемента И нельзя всегда восстановить два входных бита из выходного бита; например, если выходной бит равен 0, из этого мы не можем сказать, являются ли входные биты 0,1, 1,0 или 0,0.

Однако обратимые вентили в классических компьютерах легко создаются для битовых строк любой длины; более того, они действительно представляют практический интерес, поскольку необратимые ворота всегда должны увеличивать физическую энтропию . Обратимый вентиль - это обратимая функция для 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 U _ {\ theta} = {\ begin {bmatrix} e ^ {i \ theta} & 0 \\ 0 & 1 \ end {bmatrix}},}$

так

${\displaystyle U_{\theta }|0\rangle =e^{i\theta }|0\rangle \quad U_{\theta }|1\rangle =|1\rangle .}$

Обратимые логические схемы [ править ]

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

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

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

Теперь можно показать, что ворота Тоффоли - универсальные ворота . Это означает, что для любой обратимой классической 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 - ε - δ.

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

См. Также [ править ]

Викискладе есть медиафайлы по теме квантовой схемы .

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

Ссылки [ править ]

• Бихам, Эли ; Брассар, Жиль ; Кенигсберг, Дан; Мор, Таль (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 - редактор и симулятор квантовых схем на основе браузера.