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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Применение квантовых гейтов)
(Демонстрация действия гейта на кубит)
Строка 17: Строка 17:
 
== Демонстрация действия гейта на кубит ==
 
== Демонстрация действия гейта на кубит ==
  
Состояния квантовой системы и их преобразования можно описать используя компактные бра/кет обозначения, введённые Дираком. Кет-векторами  <tex>\mid x\bigr\rangle</tex> обозначают вектор-столбцы и обычно используют для описания квантовых состояний. Парными бра-векторами  <tex>\langle  y\mid</tex> обозначают сопряжение и транспонирование кет-векторов.
+
Состояния квантовой системы и их преобразования можно описать используя компактные бра/кет обозначения, введённые Дираком. Кет-векторами  <tex>\mid x\bigr\rangle</tex> обозначают вектор-столбцы и обычно используют для описания квантовых состояний.
  
 
Для демонстрации действия гейта на кубиты используют матричную запись гейта или таблицу истинности.  
 
Для демонстрации действия гейта на кубиты используют матричную запись гейта или таблицу истинности.  

Версия 17:08, 24 декабря 2014

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


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


По числу задействованных кубитов гейты делятся на одно- и многокубитные. Набор [math]N[/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].

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

Состояния квантовой системы и их преобразования можно описать используя компактные бра/кет обозначения, введённые Дираком. Кет-векторами [math]\mid x\bigr\rangle[/math] обозначают вектор-столбцы и обычно используют для описания квантовых состояний.

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

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

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

Также используется графическая форма записи квантовых алгоритмов. Гейты обозначаются некоторыми символами (часто это кружок или квадрат с цифрой или буквой внутри). Кубиты представлены горизонтальными нитями. Действие гейта на кубит показывается путем "нанизывания" гейта на нужный кубит (или несколько кубитов, если это не однобитный гейт). Квантовый алгоритм представляется в виде сети таких гейтов и называется квантовой сетью. Слева в такой сети находятся начальные состояния кубитов, справа — конечные. Действие алгоритма заключается в прохождении кубитов по своим нитям через гейты слева направо.

Отличие кубитов от классических битов

Классический компьютер состоит из элементарных ячеек – битов, двум состояниям которых приписываются значения [math]1[/math] или [math]0[/math]. В наборе битов (регистре) записывается и обрабатывается информация в виде двоичных чисел. Один бит имеет два базисных состояния [math]0[/math] и [math]1[/math]. Система из [math]N[/math] битов имеет [math]2N[/math] базисных состояний. Перебирая эти базисные состояния, можно закодировать двоичное число длиной [math]N[/math]. Например, в системе из трех битов можно записать одну из восьми последовательностей нулей и единиц [math]000, 001, 011, 010, 100, 101, 110, 111[/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]\left| {a^2} \right|[/math]) ложно и "немного" (с вероятностью [math]\left| {b^2} \right|[/math] ) истинно.

Наиболее важным отличием кубитов от классических битов является не непрерывная природа суперпозиционных состояний, а возможность квантового перепутывания состояний в системе кубитов. В квантовой механике размерность пространства состояний системы в целом есть произведение (а не сумма) размерностей пространств состояний отдельных подсистем. Система из [math]N[/math] кубитов имеет [math]2^N[/math], а не [math]2N[/math] базисных состояний. Произвольное состояние N кубитов [math] (a_1\mid0\bigr\rangle+b_1\mid 1\bigr\rangle)(a_2\mid0\bigr\rangle+b_2\mid 1\bigr\rangle)...(a_n\mid0\bigr\rangle+b_n\mid 1\bigr\rangle)[/math] содержит все возможные бинарные строки (комбинации из нулей и единиц) длиной [math]N[/math]. В приведенном выше примере для [math]N=3[/math] все [math]8[/math] двоичных чисел могут быть закодированы в трех кубитах одновременно.


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

В квантовом случае, как и в теории классических вычислений, любую обратимую унитарную операцию на кубитах можно представить как совокупность базовых операций. Базисом квантовой логики может служить один трехкубитный гейт (например Тоффоли [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] Not2.png [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] Cnot2.jpg [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) H.png [math]\frac{1}{\sqrt{2}}\begin{pmatrix} 1& 1 \\ 1 & -1 \end{pmatrix}[/math] [math] \begin{array}{|c|c|} 1 &\frac{1}{\sqrt{2}} \\ 0 & \frac{1}{\sqrt{2}}\\ \end{array}[/math]
[math]S[/math] (swap) S.jpg [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) Тоффоли.png [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] (гейт Фредкина) Фредкин.jpg [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]

Применение квантовых гейтов

Квантовая модель вычислений позволяет:

  • Разложить число на множители за [math]n^2[/math]. Постановка задачи разложения числа на множители выглядит следующим образом: на вход подается составное число [math]N[/math] в двоичной записи, на выход должны быть выданы два числа [math]p, q,[/math] такие что [math]N = pq[/math]. Типичный размер [math]N[/math] порядка [math]2^{2000}[/math]. Мотивацией для решения данной задачи является отсутствие на данный момент полиномиального классического алгоритма. Решение этой задачи позволит, например, взломать систему RSA. Лучший из известных классических алгоритмов имеет [math]O(2^{\sqrt[3]{n}})[/math] в качестве оценки времени работы. Уже сегодня существует квантовый алгоритм, который решает эту задачу за [math]O(n^2)[/math] [Питер Шор, 1994].
  • Сделать полный перебор за [math]{\sqrt{n}}[/math] [1]
  • Осуществить дискретный алгоритм нахождения логарифма за полиномиальное время[2]
  • Создать стойкую криптосистему: если "подслушать" квантовый бит, то он изменится [3]

Построение квантового компьютера в виде реального физического прибора является фундаментальной задачей физики XXI века. В настоящее время построены только ограниченные его варианты (в пределах 512 кубит).

В 2005 году группой Ю. Пашкина при помощи японских специалистов был построен двухкубитный квантовый процессор на сверхпроводящих элементах.

В ноябре 2009 года физикам из Национального института стандартов и технологий в США впервые удалось собрать программируемый квантовый компьютер, состоящий из двух кубит.

11 мая 2011 года представлен компьютер D-Wave One, созданный на базе 128-кубитного процессора.

В декабре 2012 года представлен новый процессор Vesuvius, который объединяет 512 кубит.

См.также

Источники информации

Примечания