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

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

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

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

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

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

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

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

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

Точнее: 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 _θ (для подходящего значения θ) вместе с 2-кубитным вентилем 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} ^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 – ε – δ.

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

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

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

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

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

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

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

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

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

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

1. Нильсен, Майкл А .; Чуанг, Исаак (2010). Квантовые вычисления и квантовая информация. Кембридж: Издательство Кембриджского университета . стр. 26–28. ISBN 978-1-10700-217-3. ОСЛК  43641333.
2. Колин П. Уильямс (2011). Исследования в области квантовых вычислений . Спрингер . стр. 123–200. ISBN 978-1-84628-887-6.
3. Нильсен, Майкл А .; Чуанг, Исаак (2010). Квантовые вычисления и квантовая информация. Кембридж: Издательство Кембриджского университета . стр. 171–215. ISBN 978-1-10700-217-3. ОСЛК  43641333.
4. Омер, Бернхард (20 января 2000 г.). Квантовое программирование в QCL (PDF) (Диссертация). Институт теоретической физики Венского технического университета. стр. 37–38 . Проверено 12 октября 2021 г.
5. Фейнман, Ричард П. (1986). «Квантово-механические компьютеры». Основы физики . 16 (6). Springer Science and Business Media LLC: 507–531. Бибкод : 1986FoPh...16..507F. дои : 10.1007/bf01886518. ISSN  0015-9018. S2CID  122076550.
6. «Введение в модель квантовой схемы» (PDF) .
7. https://medium.com/@josephmeng96/accelerating-quantum-simulations-w-fpgas-84b09569ad0f
8. https://medium.com/@josephmeng96/accelerating-quantum-simulations-w-fpgas-84b09569ad0f
9. https://medium.com/@josephmeng96/accelerating-quantum-simulations-w-fpgas-84b09569ad0f

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

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

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