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

Модель квантовых вычислений

Схема, которая выполняет телепортацию кубита. ^[1] Эта схема состоит из квантовых вентилей и измерений . Измерение — это квантовое явление, которое не происходит в классических схемах .

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

Схемы записываются таким образом, что горизонтальная ось — это время, начинающееся слева и заканчивающееся справа. Горизонтальные линии — это кубиты, двойные линии — классические биты . Элементы, которые соединены этими линиями, — это операции, выполняемые над кубитами, такие как измерения или вентили. Эти линии определяют последовательность событий и обычно не являются физическими кабелями. ^{[2] [3] [4]}

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

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

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

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

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

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

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

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

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

Используя нотацию Дирака , если x ₁ , x ₂ , ..., x _n — классическая битовая строка, то

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

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

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

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

Однако структура кубитов в гильбертовом пространстве допускает множество квантовых вентилей, которые не индуцируются классическими. Например, относительный фазовый сдвиг — это 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, а не эти вероятности. Поскольку квантовые вычисления обратимы, на каждом «шаге» количество линий должно быть таким же, как и количество входных линий. Кроме того, каждая входная комбинация должна быть сопоставлена ​​с одной комбинацией на каждом «шаге». Это означает, что каждая промежуточная комбинация в квантовой схеме является биективной функцией входа. ^[6]

Теперь можно показать, что вентиль Тоффоли является универсальным вентилем. Это означает, что для любой обратимой классической 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 (биективная или нет) может быть смоделирована схемой вентилей Тоффоли. Очевидно, что если отображение не является инъективным , в какой-то момент симуляции (например, на последнем шаге) должен быть произведен некоторый "мусор".

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

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

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

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

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

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

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

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

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

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

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

Содержимое 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 .}$

Аналогично, выходное регистровое пространство связано с кубитовым регистром посредством наблюдаемой величины A со значением Y. Обратите внимание, что наблюдаемые величины в квантовой механике обычно определяются в терминах проекционных мер на R ; если переменная оказывается дискретной, проекционная мера сводится к семейству {E _λ }, индексированному по некоторому параметру λ, ранжированному по счетному множеству. Аналогично, наблюдаемая величина со значением Y может быть связана с семейством попарно ортогональных проекций {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 - ε - δ.

Это следует из применения границы Чернова .

Ускорение моделирования квантовых вычислений с помощью ПЛИС

С появлением квантовых вычислений произошел значительный всплеск как числа разработчиков, так и доступных инструментов. ^[7] Однако медленный темп технологического прогресса и высокие затраты на обслуживание, связанные с квантовыми компьютерами, ограничили более широкое участие в этой области. В ответ разработчики обратились к симуляторам, таким как Qiskit от IBM , чтобы моделировать квантовое поведение, не полагаясь исключительно на реальное квантовое оборудование. Тем не менее, симуляторы, будучи классическими компьютерами, ограничены скоростью вычислений. Фундаментальное преимущество квантовых компьютеров заключается в их способности обрабатывать кубиты, одновременно используя такие свойства, как запутанность и суперпозиция. При запуске квантовых симуляций на классических компьютерах исчезает присущий квантовым вычислениям параллелизм. Более того, по мере увеличения числа симулируемых кубитов скорость симуляции пропорционально уменьшается.

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

Основная идея ускорения моделирования квантовых вычислений заключается в том, чтобы разгрузить часть тяжелых вычислений на специальное оборудование, например ПЛИС, чтобы ускорить весь процесс моделирования. И чем больше квантовые схемы (больше кубитов и больше вентилей) мы моделируем, тем больше ускорения мы получаем от разгрузки на ПЛИС по сравнению с программным моделированием на ЦП. Поток данных моделирования поясняется ниже. Сначала пользователь вводит всю информацию о квантовой схеме, включая начальное состояние и различные вентили, через пользовательский интерфейс. Затем вся эта информация сжимается и отправляется в ПЛИС через некоторые аппаратные протоколы связи, например AXI. Затем вся информация сохраняется во встроенной памяти в ПЛИС. И моделирование начинается, когда данные считываются из памяти и отправляются в модуль умножения матриц. После того, как все вычисления выполнены, результат будет отправлен обратно в память и на ЦП.

Предположим, что мы моделируем 5-кубитные схемы, тогда нам нужно сохранить вектор, который содержит 32 (2⁵) 16-битных значения, каждое из которых представляет квадратный корень вероятности возможного существующего состояния. Нам также нужно сохранить матрицу 32x32, которая представляет вентиль. Чтобы распараллелить это вычисление, мы можем сохранить 32 строки матрицы отдельно и реплицировать 32 row_vec_mult оборудования таким образом, чтобы каждая строка могла вычислять умножение параллельно. Это значительно ускорит моделирование ценой большего использования оборудования и памяти в FPGA. ^[8]

Было обнаружено, что при тщательном проектировании оборудования можно достичь аппаратной архитектуры с временной сложностью O(n), где 'n' обозначает количество кубитов. Напротив, время выполнения Numpy приближается к O(2^2^n). Это открытие подчеркивает возможность использования ПЛИС для ускорения моделирования квантовых вычислений. ^[9]

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

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

Ссылки

1. Нильсен, Майкл А.; Чуан , Айзек (2010). Квантовые вычисления и квантовая информация. Кембридж: Cambridge University Press . С. 26–28. ISBN 978-1-10700-217-3. OCLC  43641333.
2. Колин П. Уильямс (2011). Исследования в области квантовых вычислений . Springer . С. 123–200. ISBN 978-1-84628-887-6.
3. Нильсен, Майкл А.; Чуан , Айзек (2010). Квантовые вычисления и квантовая информация. Кембридж: Cambridge University Press . С. 171–215. ISBN 978-1-10700-217-3. OCLC  43641333.
4. Ömer, Bernhard (2000-01-20). Квантовое программирование в QCL (PDF) (диссертация). Институт теоретической физики, Венский технический университет. стр. 37–38 . Получено 12 октября 2021 г.
5. Фейнман, Ричард П. (1986). «Квантовые механические компьютеры». Основы физики . 16 (6). Springer Science and Business Media LLC: 507–531. Bibcode : 1986FoPh...16..507F. doi : 10.1007/bf01886518. ISSN  0015-9018. S2CID  122076550.
6. «Введение в модель квантовой цепи» (PDF) .
7. «Ускорение квантового моделирования с помощью ПЛИС». 19 августа 2020 г.
8. «Ускорение квантового моделирования с помощью ПЛИС». 19 августа 2020 г.
9. «Ускорение квантового моделирования с помощью ПЛИС». 19 августа 2020 г.

• Бихам, Эли ; Брассар, Жиль ; Кенигсберг, Дэн; Мор, Тал (2004), «Квантовые вычисления без запутанности», Теоретическая информатика , 320 (1): 15–33, arXiv : quant-ph/0306182 , doi : 10.1016/j.tcs.2004.03.041, MR  2060181, S2CID  295103.
• Freedman, Michael H. ; Китаев, Алексей ; Larsen, Michael J. ; Wang, Zhenghan (2003), "Топологические квантовые вычисления", Bulletin of the American Mathematical Society , 40 (1): 31–38, arXiv : quant-ph/0101025 , doi :10.1090/S0273-0979-02-00964-3, MR  1943131.
• Хирвенсало, Мика (2001), Квантовые вычисления , серия «Естественные вычисления», Берлин: Springer-Verlag, ISBN 3-540-66783-0, г-н  1931238.
• Китаев, А. Ю. (1997), «Квантовые вычисления: алгоритмы и коррекция ошибок», УМН , 52 (6(318)): 53–112, Bibcode :1997RuMaS..52.1191K, doi :10.1070/RM1997v052n06ABEH002155, MR  1611329, S2CID  250816585.
• Нильсен, Майкл А.; Чуан, Айзек Л. (2000), Квантовые вычисления и квантовая информация , Кембридж: Cambridge University Press, ISBN 0-521-63235-8, г-н  1796805.

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

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