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

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

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

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

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

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

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

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

Определять квантовые ворота, нам сначала нужно указать квантовую замену п-битовые данные. В квантованная версия классических п-битовое пространство {0,1}^п это Гильбертово пространство

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

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

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

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

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

Квантовые логические вентили, в отличие от классических логических вентилей, всегда обратимы. Требуется особый вид обратимой функции, а именно унитарный отображение, т. е. линейное преобразование комплексного внутреннее пространство продукта что сохраняет Эрмитский внутренний продукт. An п-кубит (обратимый) квантовый вентиль является унитарное отображение U из космоса ЧАС_{QB (п)} из п-кубиты на себя.

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

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

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

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

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

Однако структура кубитов в гильбертовом пространстве допускает множество квантовых вентилей, которые не индуцируются классическими. Например, относительный фазовый сдвиг - это вентиль в 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.}$

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

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

Чтобы объяснить этот процесс сборки, предположим, что у нас есть обратимый п-битовые ворота ж и обратимый м-битовые ворота грамм. Соединение их вместе означает создание новой схемы путем соединения некоторого набора k результаты ж к некоторому набору k вклады грамм как на рисунке ниже. На этом рисунке п=5, k= 3 и м= 7. Полученная схема также обратима и работает на п+м−k биты.

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

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

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

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

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

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

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

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

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

Это также теоремы универсальности для определенных комплектов знаменитых ворот; такая теорема универсальности существует, например, для пары, состоящей из одного фазового элемента кубита U_θ упомянутого выше (для подходящего значения θ) вместе с 2-кубитом CNOT ворота W_CNOT. Однако теорема универсальности для квантового случая несколько слабее, чем для классического случая; он утверждает только, что любой обратимый п-кубитовая схема может быть приблизительный произвольно хорошо схемами, собранными из этих двух элементарных вентилей. Обратите внимание, что есть бесчисленно множество возможных фазовых вентилей с одним кубитом, по одному для каждого возможного угла θ, поэтому все они не могут быть представлены конечной схемой, построенной из {U_θ, W_CNOT}.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Учитывая смешанное состояние S, соответствует вероятностная мера на Yданный

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

Функция F:Икс → Y вычисляется схемойU:ЧАС_{QB (р)} → ЧАС_{QB (р)} с точностью до ε тогда и только тогда, когда для всех битовых цепочек Икс длины м

${ 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(Икс) со сколь угодно малой вероятностью ошибки при мажоритарной выборке для достаточно большого размера выборки. В частности, возьмите k независимых выборок из распределения вероятностей Pr на Y и выберите значение, с которым согласны более половины образцов. Вероятность того, что значение F(Икс) отбирается более чем k/ 2 раза не менее

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

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

Это следует, применяя Граница Чернова.

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

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

Рекомендации

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

внешняя ссылка

• Q-цепь - это пакет макросов для рисования квантовых схем в LaTeX.
• Симулятор квантовой схемы (Дэви Вибирал) редактор и симулятор квантовых схем на основе браузера.
• Площадка для квантовых вычислений среда квантового написания сценариев на основе браузера.
• Причуда - Игрушка квантовой схемы редактор и симулятор квантовых схем на основе браузера.