Квантовые гейты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Таблица различных обозначений квантовых гейтов)
(Демонстрация действия гейта на кубит)
Строка 23: Строка 23:
 
Для демонстрации действия гейта на кубиты используют матричную запись гейта или таблицу истинности.  
 
Для демонстрации действия гейта на кубиты используют матричную запись гейта или таблицу истинности.  
  
Матрица гейта действует на столбец весовых коэффициентов регистра и получается новый столбец, соответствующий новому состоянию регистра. В случае, если в действии гейта не участвуют некоторые кубиты, то их и не включают в матрицу, т.e. в матрице записано только реальное действие кубитов.  
+
Матрица гейта умножается на столбец весовых коэффициентов регистра и получается новый столбец, соответствующий новому состоянию регистра. В случае, если в действии гейта не участвуют некоторые кубиты, то их и не включают в матрицу, т.e. в матрице записано только реальное действие кубитов.  
  
 
Таблица истинности отражает действие гейта на базисные состояния. Ее структура имеет следующий вид: по горизонтали записывается слева начальные состояния входящих кубитов, а справа — соответствующие конечные. По вертикали записываются все базисные состояния. Пример матричной записи кубита и таблиц истинности будет дан в таблице ниже.
 
Таблица истинности отражает действие гейта на базисные состояния. Ее структура имеет следующий вид: по горизонтали записывается слева начальные состояния входящих кубитов, а справа — соответствующие конечные. По вертикали записываются все базисные состояния. Пример матричной записи кубита и таблиц истинности будет дан в таблице ниже.

Версия 18:09, 22 декабря 2014

Идея квантового компьютера, высказанная Фейнманом (Richard Phillips Feynman) в 1982 году, достаточно проста. Она состоит в построении компьютера на основе квантовых, а не классических элементарных ячеек. Законы квантовой механики, определяющие поведение таких квантовых битов (quantum bit) – кубитов, обеспечивают огромные преимущества (скорость и параллелизм вычислений) квантового компьютера по сравнению с классическим компьютером.

Классический компьютер состоит из элементарных ячеек – битов, двум состояниям которых приписываются значения [math]1[/math] или [math]0[/math]. В наборе битов (регистре) записывается и перерабатывается информация в виде двоичных чисел. Один бит имеет два базисных состояния [math]0[/math] и [math]1[/math]. Система из [math]N[/math] битов имеет [math]2N[/math] базисных состояний. В квантовом компьютере элементарными ячейками для записи информации являются квантовые биты – кубиты. Кубит – это квантовая система, которая, как и бит, имеет два базисных состояния [math]\mid0\bigr\rangle[/math] и [math]\mid 1\bigr\rangle[/math], но в отличие от бита, кубит может находиться в любом суперпозиционном состоянии [math]\mid q\bigr\rangle=a\mid0\bigr\rangle+b\mid 1\bigr\rangle[/math]. Набор [math]N[/math] кубитов составляет квантовый регистр.

Наиболее важным отличием кубитов от классических битов является не непрерывная природа суперпозиционных состояний, а возможность квантового перепутывания состояний в системе кубитов. В квантовой механике размерность пространства состояний системы в целом есть произведение (а не сумма) размерностей пространств состояний отдельных подсистем. Система из [math]N[/math] кубитов имеет [math]2^N[/math], а не [math]2N[/math] базисных состояний.


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


По числу задействованных кубитов гейты делятся на одно- и многокубитные. Гейт переводит одно состояние регистра в другое. Действие гейта на регистр можно записать так: [math]G\mid R\bigr\rangle=\mid R^\prime\bigr\rangle[/math].

Гейты – линейные операции: [math]G(\mid p\bigr\rangle+\mid g\bigr\rangle)=G\mid p\bigr\rangle+G\mid g\bigr\rangle[/math].

Демонстрация действия гейта на кубит

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

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

Таблица истинности отражает действие гейта на базисные состояния. Ее структура имеет следующий вид: по горизонтали записывается слева начальные состояния входящих кубитов, а справа — соответствующие конечные. По вертикали записываются все базисные состояния. Пример матричной записи кубита и таблиц истинности будет дан в таблице ниже.

Описание используемых гейтов

В квантовом случае, как и в теории классических вычислений, любую обратимую унитарную операцию на кубитах можно представить как совокупность базовых операций. Базисом квантовой логики может служить один трехкубитный гейт (например Тоффоли [math](CCNOT)[/math] или Фредкина [math](CSWAP)[/math]) или один однокубитный и один двукубитный гейт (например [math]NOT[/math] и [math]CNOT[/math])

Однокубитный гейт [math]NOT[/math]

Однокубитная логическая операция [math]NOT[/math] переводит [math]\mid q\bigr\rangle=a\mid0\bigr\rangle+b\mid 1\bigr\rangle[/math] в [math]\mid q^\prime\bigr\rangle=b\mid0\bigr\rangle+a\mid 1\bigr\rangle[/math].

т.e. переставляет весовые коэффициенты кубита местами. В классическом случае ей соответствует обычный [math]NOT[/math], т.к. один из коэффициентов равен нулю.

Двукубитный гейт [math]CNOT[/math]

Двубитный гейт [math]CNOT[/math] (Controlled NOT), действующий на двукубитное состояние в общем виде записывается так: [math]CNOT(R_{00} \left | \ 00\right \rangle +R_{01} \left | \ 01\right \rangle +R_{10} \left | \ 10\right \rangle +R_{11} \left | \ 11\right \rangle) = R_{00} \left | \ 00\right \rangle +R_{01} \left | \ 01\right \rangle[/math] [math]+R_{11}\left | \ 10\right \rangle +R_{10} \left | \ 11\right \rangle[/math]

В классическом случае это просто [math]XOR[/math].

Другие используемые гейты

Кроме упомянутых выше гейтов [math]NOT[/math] и [math]CNOT[/math] в квантовых вычислениях используются также некоторые другие гейты. Их применение не необходимо, но запись алгоритма с их помощью намного проще. На практике часто используются такие гейты: однобитный [math]H[/math] (Hadamard), двубитный [math]S[/math] (swap), трехбитные [math]CCNOT[/math] (гейт Тоффоли), [math] CSWAP[/math] (гейт Фредкина).

Гейт Тоффоли инвертирует кубит [math]B[/math] при условии что значение кубитов [math]A[/math] и [math]C[/math] равны [math]1[/math].

Гейт Фредкина устроен следующим образом: он осуществляет перестановку кубитов [math]B[/math] и [math]C[/math] при условии, что значение кубита [math]A[/math] равно [math]0[/math].

Таблица различных обозначений квантовых гейтов

название гейта графическое обозначение матричная запись таблица истинности
[math]NOT[/math] [math]\begin{pmatrix} 0& 1 \\ 1 & 0 \end{pmatrix}[/math] [math] \begin{array}{|c|c|} 0 & 1 \\ 1 & 0 \\ \end{array}[/math]
[math]CNOT[/math] [math]\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 1 & 0& 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}[/math] [math] \begin{array}{|c c|c c|} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ \end{array}[/math]
[math]H[/math] (Hadamard) [math]\frac{1}{\sqrt{2}}\begin{pmatrix} 1& 1 \\ 1 & -1 \end{pmatrix}[/math] [math] \begin{array}{|c|c|} 0 &\frac{1}{\sqrt{2}} \\ 1 & \frac{-1}{\sqrt{2}}\\ \end{array}[/math]
[math]S[/math] (swap) [math]\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}[/math] [math] \begin{array}{|c c|c c|} 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ \end{array}[/math]
[math]CCNOT[/math] (Toffoli) [math]\begin{pmatrix} 1 & 0 & 0 &0 & 0 & 0 &0 &0 \\ 0 & 1 & 0& 0& 0 &0 & 0 & 0 \\ 0 & 0 & 1 & 0& 0 &0 & 0 & 0 \\0 & 0 & 0& 1& 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\0 & 0 & 0 & 0& 0 & 1 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\end{pmatrix}[/math]

[math] \begin{array}{|c c c ||c c c|} A & B & C & A' & B' & C'\\ \hline 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 \\ \end{array}[/math]

[math]CSWAP[/math] (гейт Фредкина) [math]\begin{pmatrix} 1 & 0 & 0 &0 & 0 & 0 &0 &0 \\ 0 & 1 & 0& 0& 0 &0 & 0 & 0 \\ 0 & 0 & 1 & 0& 0 &0 & 0 & 0 \\0 & 0 & 0& 1& 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\0 & 0 & 0 & 0& 0 & 0 & 1 & 0\\0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\end{pmatrix}[/math] [math] \begin{array}{|c c c ||c c c|} A & B & C & A' & B' & C'\\ \hline 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array}[/math]