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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 59 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
Идея квантового компьютера, высказанная Фейнманом (англ. ''Richard Phillips Feynman'') в 1982 году, достаточно проста. Она состоит в построении компьютера на основе квантовых, а не классических элементарных ячеек. Законы квантовой механики, определяющие поведение таких '''квантовых битов''' (англ.  ''quantum bit'') – кубитов, обеспечивают огромные преимущества (скорость и параллелизм вычислений) квантового компьютера по сравнению с классическим компьютером.
 
Идея квантового компьютера, высказанная Фейнманом (англ. ''Richard Phillips Feynman'') в 1982 году, достаточно проста. Она состоит в построении компьютера на основе квантовых, а не классических элементарных ячеек. Законы квантовой механики, определяющие поведение таких '''квантовых битов''' (англ.  ''quantum bit'') – кубитов, обеспечивают огромные преимущества (скорость и параллелизм вычислений) квантового компьютера по сравнению с классическим компьютером.
 +
{{Определение
 +
|definition=Любая логическая операция с кубитами называется '''квантовым гейтом''' (англ. ''quantum gate'').
 +
}}
  
 +
==Отличие кубитов от классических битов==
  
{{Определение
+
Классический компьютер состоит из элементарных ячеек – битов, двум состояниям которых приписываются значения <tex>1</tex> или <tex>0</tex>. В наборе битов (регистре) записывается и обрабатывается информация в виде двоичных чисел. Один бит имеет два базисных состояния <tex>0</tex> и <tex>1</tex>. Перебирая эти базисные состояния, можно закодировать двоичное число длиной <tex>N</tex>. Например, в системе из трех битов можно записать одну из восьми последовательностей нулей и единиц.
   
 
  
|definition='''Любая логическая операция с кубитами называется квантовым гейтом (англ. quantum gate).'''
+
Состояния квантовой системы и их преобразования можно описать используя компактные бра/кет обозначения. Бра и кет (англ. ''bracket'' — скобка)—  обозначения, введенные Дираком на заре зарождения квантовой механики как удобное средство манипулирования векторами. Кет-векторами  <tex>\mid x\bigr\rangle</tex> обозначают вектор-столбцы и обычно используют для описания квантовых состояний. В середине скобки, по Дираку, должен помещаться индекс состояния, т.е. величина или набор величин, которые определяют состояние системы. Бра-вектор <tex>\left\langle y\right|</tex> обозначает вектор-строку.
  
 +
В квантовом компьютере кубит – это квантовая система, которая, как и бит, имеет два базисных состояния <tex>\mid0\bigr\rangle</tex> и <tex>\mid 1\bigr\rangle</tex>, но в отличие от бита, кубит может находиться в любом суперпозиционном состоянии <tex>\mid q\bigr\rangle=a\mid0\bigr\rangle+b\mid 1\bigr\rangle</tex>, где <tex>a, b</tex> – комплексные числа,  <tex>{\left|a\right|^2}+ {\left|b\right|^2}=1</tex>. Таким образом, квантовый бит может принимать бесконечно много значений, но как результат измерения мы получим либо состояние <tex>\mid0\bigr\rangle</tex> с вероятностью <tex>{\left|a\right|^2} </tex>, либо состояние <tex>\mid 1\bigr\rangle</tex> с
 +
вероятностью <tex>{\left|b\right|^2} </tex>.
  
}}
+
Наиболее важным отличием кубитов от классических битов является не непрерывная природа суперпозиционных состояний, а возможность квантового перепутывания состояний в системе кубитов. В квантовой механике размерность пространства состояний системы в целом есть произведение размерностей пространств состояний отдельных подсистем. Система из <tex>N</tex> кубитов имеет <tex>2^N</tex> базисных состояний. Произвольное состояние <tex>N</tex> кубитов <tex>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)</tex> содержит все возможные бинарные строки (комбинации из нулей и единиц) длиной <tex>N</tex>. В приведенном выше примере для <tex>N=3</tex> все <tex>8</tex> двоичных чисел могут быть закодированы в трех кубитах '''одновременно'''. Это становится возможным за счет квантовомеханического перепутывания. Нелокальные корреляции в системе кубитов и обеспечивают экспоненциально большое вычислительное пространство и параллелизм квантовых вычислений.
  
 
По числу задействованных кубитов гейты делятся на одно- и многокубитные. Набор <tex>N</tex> кубитов составляет квантовый регистр. Гейт переводит одно состояние регистра в другое.  
 
По числу задействованных кубитов гейты делятся на одно- и многокубитные. Набор <tex>N</tex> кубитов составляет квантовый регистр. Гейт переводит одно состояние регистра в другое.  
Действие гейта на регистр можно записать так: <tex>G\mid R\bigr\rangle=\mid R^\prime\bigr\rangle</tex>.
+
Действие гейта на регистр можно записать так: <tex>G\mid R\bigr\rangle = \mid R^\prime\bigr\rangle</tex>.
  
Гейты – линейные операции: <tex>G(\mid p\bigr\rangle+\mid g\bigr\rangle)=G\mid p\bigr\rangle+G\mid g\bigr\rangle</tex>.
+
Гейты – линейные операции: <tex>G(\mid p\bigr\rangle+\mid g\bigr\rangle = G\mid p\bigr\rangle+G\mid g\bigr\rangle</tex>.
  
 
== Демонстрация действия гейта на кубит ==
 
== Демонстрация действия гейта на кубит ==
 
Состояния квантовой системы и их преобразования можно описать используя компактные бра/кет обозначения, введённые Дираком. Кет-векторами  <tex>\mid x\bigr\rangle</tex> обозначают вектор-столбцы и обычно используют для описания квантовых состояний. Парными бра-векторами  <tex>\langle  y\mid</tex> обозначают сопряжение и транспонирование кет-векторов.
 
  
 
Для демонстрации действия гейта на кубиты используют матричную запись гейта или таблицу истинности.  
 
Для демонстрации действия гейта на кубиты используют матричную запись гейта или таблицу истинности.  
Строка 23: Строка 26:
 
Матрица гейта умножается на столбец весовых коэффициентов регистра и получается новый столбец, соответствующий новому состоянию регистра. В случае, если в действии гейта не участвуют некоторые кубиты, то их и не включают в матрицу, т.e. в матрице записано только реальное действие кубитов.  
 
Матрица гейта умножается на столбец весовых коэффициентов регистра и получается новый столбец, соответствующий новому состоянию регистра. В случае, если в действии гейта не участвуют некоторые кубиты, то их и не включают в матрицу, т.e. в матрице записано только реальное действие кубитов.  
  
Таблица истинности отражает действие гейта на базисные состояния. Ее структура имеет следующий вид: по горизонтали записывается слева начальные состояния входящих кубитов, а справа — соответствующие конечные. По вертикали записываются все базисные состояния. Пример матричной записи кубита и таблиц истинности будет дан в таблице ниже.
+
Таблица истинности отражает действие гейта на базисные состояния. Ее структура имеет следующий вид: по горизонтали записываются слева начальные состояния входящих кубитов, а справа — соответствующие конечные. По вертикали записываются все базисные состояния. Пример матричной записи кубита и таблиц истинности будет дан в таблице ниже.
  
 
Также используется графическая форма записи квантовых алгоритмов. Гейты обозначаются некоторыми символами (часто это кружок или квадрат с цифрой или буквой внутри). Кубиты представлены горизонтальными нитями. Действие гейта на кубит показывается путем "нанизывания" гейта на нужный кубит (или несколько кубитов, если это не однобитный гейт). Квантовый алгоритм представляется в виде сети таких гейтов и называется квантовой сетью. Слева в такой сети находятся начальные состояния кубитов, справа — конечные. Действие алгоритма заключается в прохождении кубитов по своим нитям через гейты слева направо.
 
Также используется графическая форма записи квантовых алгоритмов. Гейты обозначаются некоторыми символами (часто это кружок или квадрат с цифрой или буквой внутри). Кубиты представлены горизонтальными нитями. Действие гейта на кубит показывается путем "нанизывания" гейта на нужный кубит (или несколько кубитов, если это не однобитный гейт). Квантовый алгоритм представляется в виде сети таких гейтов и называется квантовой сетью. Слева в такой сети находятся начальные состояния кубитов, справа — конечные. Действие алгоритма заключается в прохождении кубитов по своим нитям через гейты слева направо.
 
==Отличие кубитов от классических битов==
 
 
Классический компьютер состоит из элементарных ячеек – битов, двум состояниям которых приписываются значения <tex>1</tex> или <tex>0</tex>. В наборе битов (регистре) записывается и обрабатывается информация в виде двоичных чисел. Один бит имеет два базисных состояния <tex>0</tex> и <tex>1</tex>. Система из <tex>N</tex> битов имеет <tex>2N</tex> базисных состояний. Перебирая эти базисные состояния, можно закодировать двоичное число длиной <tex>N</tex>. Например, в системе из трех битов можно записать '''одну''' из восьми последовательностей нулей и единиц <tex>000, 001, 011, 010, 100, 101, 110, 111</tex>.
 
 
В квантовом компьютере элементарными ячейками для записи информации являются квантовые биты – кубиты. Кубит – это квантовая система, которая, как и бит, имеет два базисных состояния <tex>\mid0\bigr\rangle</tex> и <tex>\mid 1\bigr\rangle</tex>, но в отличие от бита, кубит может находиться в любом суперпозиционном состоянии <tex>\mid q\bigr\rangle=a\mid0\bigr\rangle+b\mid 1\bigr\rangle</tex>. Состояние кубита – "немного" (с вероятностью  <tex>\left| {a^2} \right|</tex>) ложно и "немного" (с вероятностью <tex>\left| {b^2} \right|</tex> ) истинно. 
 
 
Наиболее важным отличием кубитов от классических битов является не непрерывная природа суперпозиционных состояний, а возможность квантового перепутывания состояний в системе кубитов. В квантовой механике размерность пространства состояний системы в целом есть произведение (а не сумма) размерностей пространств состояний отдельных подсистем. Система из <tex>N</tex> кубитов имеет <tex>2^N</tex>, а не <tex>2N</tex> базисных состояний. Произвольное состояние N кубитов <tex> (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)</tex> содержит все возможные бинарные строки (комбинации из нулей и единиц) длиной <tex>N</tex>. В приведенном выше примере для <tex>N=3</tex> все <tex>8</tex> двоичных чисел могут быть закодированы в трех кубитах '''одновременно'''.
 
 
  
 
== Описание используемых гейтов ==
 
== Описание используемых гейтов ==
Строка 44: Строка 38:
 
===Однокубитный гейт <tex>NOT</tex>===
 
===Однокубитный гейт <tex>NOT</tex>===
  
Однокубитная логическая операция <tex>NOT</tex> переводит <tex>\mid q\bigr\rangle=a\mid0\bigr\rangle+b\mid 1\bigr\rangle</tex> в <tex>\mid q^\prime\bigr\rangle=b\mid0\bigr\rangle+a\mid 1\bigr\rangle</tex>.
+
Однокубитная логическая операция <tex>NOT</tex> переводит <tex>\mid q\bigr\rangle=a\mid0\bigr\rangle+b\mid 1\bigr\rangle</tex> в <tex>\mid q^\prime\bigr\rangle=b\mid0\bigr\rangle+a\mid 1\bigr\rangle</tex>,
 +
 
 +
т.e. переставляет весовые коэффициенты кубита местами.
 +
 
 +
Квантовому состоянию кубита соответствует столбец <tex>\mid q\bigr\rangle\to \begin{pmatrix} a \\ b \end{pmatrix}</tex>.
 +
 
 +
Поэтому квантовым аналогом классического <tex>NOT</tex>-гейта является матрица вида:
  
т.e. переставляет весовые коэффициенты кубита местами. В классическом случае ей соответствует обычный <tex>NOT</tex>, т.к. один из коэффициентов равен нулю.
+
<tex>X\equiv\begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}</tex>
 +
 +
<tex>X\times\begin{pmatrix} a\\ b\end{pmatrix}=\begin{pmatrix} b\\ a\end{pmatrix}</tex>
  
 
===Двукубитный гейт <tex>CNOT</tex>===
 
===Двукубитный гейт <tex>CNOT</tex>===
Двубитный гейт <tex>CNOT</tex> (''Controlled NOT''), действующий на двукубитное состояние в общем виде записывается так:
+
Двубитный гейт <tex>CNOT</tex> (англ. ''Controlled NOT''), действующий на двукубитное состояние в общем виде записывается так:
 
<tex>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</tex> <tex>+R_{11}\left | \ 10\right \rangle +R_{10} \left | \ 11\right \rangle</tex>
 
<tex>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</tex> <tex>+R_{11}\left | \ 10\right \rangle +R_{10} \left | \ 11\right \rangle</tex>
  
В классическом случае это просто <tex>XOR</tex>.
+
Простейшим двухкубитным контролируемым гейтом в классическом компьютере является <tex>CNOT</tex>. В квантовых вычислениях вводится подобный гейт, который имеет два входных кубита и два кубита на выходе. Как и в классическом случае один из пары кубитов называется контролирующим, а второй контролируемым или кубитом-мишенью. Логика выполнения операции при этом определяется следующим образом: если контролирующий кубит находится в состоянии <tex>\left |\ 1\right \rangle</tex>, тогда контролируемый кубит подвергается квантовой операции <tex>NOT</tex>, в противном случае контролируемый кубит остается без изменения.
  
 
===Другие используемые гейты===
 
===Другие используемые гейты===
Строка 64: Строка 66:
 
===Таблица различных обозначений квантовых гейтов===
 
===Таблица различных обозначений квантовых гейтов===
  
{| class="wikitable"
+
{| border="1" cellpadding="20" cellspacing="0"
 +
 
 
|-
 
|-
!название гейта||графическое обозначение||матричная запись||таблица истинности  
+
!Название гейта||Графическое обозначение||Матричная запись||Таблица истинности  
 
|-
 
|-
| <tex>NOT</tex>          || [[Файл:Not2.png‎ ]]        || <tex>\begin{pmatrix} 0& 1 \\ 1 & 0 \end{pmatrix}</tex>  || <tex> \begin{array}{|c|c|}
+
| <tex>NOT</tex>          || [[Файл:Not2_(1).png ]]        || <tex>\begin{pmatrix} 0& 1 \\ 1 & 0 \end{pmatrix}</tex>  || <tex> \begin{array}{|c|c|}
 
    
 
    
 
   0 & 1 \\
 
   0 & 1 \\
Строка 91: Строка 94:
 
  \end{array}</tex>     
 
  \end{array}</tex>     
 
|-
 
|-
|<tex>S</tex> (''swap'')||  [[Файл:S.jpg‎ ]]  ||<tex>\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}</tex> ||<tex> \begin{array}{|c c|c c|}
+
|<tex>S</tex> (''swap'')||  [[Файл:SWAP'.jpg‎]]  ||<tex>\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}</tex> ||<tex> \begin{array}{|c c|c c|}
 
    
 
    
 
    
 
    
Строка 100: Строка 103:
 
  \end{array}</tex>
 
  \end{array}</tex>
 
|-
 
|-
|<tex>CCNOT</tex> (''Toffoli'')||  [[Файл:Тоффоли.png]] ||<tex>\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}</tex> ||
+
|<tex>CCNOT</tex> (''Toffoli'')||  [[Файл:CCNOT.png]] ||<tex>\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}</tex> ||
 
<tex> \begin{array}{|c c c  ||c c c|}
 
<tex> \begin{array}{|c c c  ||c c c|}
 
A & B & C &  A' & B' & C'\\  
 
A & B & C &  A' & B' & C'\\  
Строка 114: Строка 117:
 
  \end{array}</tex>
 
  \end{array}</tex>
 
|-
 
|-
|<tex>CSWAP</tex> (гейт Фредкина)||[[Файл:Фредкин.jpg]]  || <tex>\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}</tex>    ||<tex> \begin{array}{|c c c  ||c c c|}
+
|<tex>CSWAP</tex> (гейт Фредкина)||[[Файл:CSWAP'.jpg]]  || <tex>\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}</tex>    ||<tex> \begin{array}{|c c c  ||c c c|}
 
A & B & C &  A' & B' & C'\\  
 
A & B & C &  A' & B' & C'\\  
 
  \hline
 
  \hline
Строка 131: Строка 134:
  
 
Квантовая модель вычислений позволяет:
 
Квантовая модель вычислений позволяет:
* Разложить число на множители за <tex>n^2</tex>. Постановка задачи разложения числа на множители выглядит следующим образом: на вход подается составное число <tex>N</tex> в двоичной записи, на выход должны быть выданы два числа <tex>p, q,</tex> такие что <tex>N = pq</tex>. Типичный размер <tex>N</tex> порядка <tex>2^{2000}</tex>. Мотивацией для решения данной задачи является отсутствие на данный момент полиномиального классического алгоритма. Решение этой задачи позволит, например, взломать систему RSA. Лучший из известных классических алгоритмов имеет <tex>O(2^{\sqrt[3]{n}})</tex> в качестве оценки времени работы. Уже сегодня существует квантовый алгоритм, который решает эту задачу за <tex>O(n^2)</tex> [Питер Шор, 1994].
+
*[[Разложение на множители (факторизация)|разложить число <tex>M</tex> на множители ]] за <tex>O(\lg^3  M)</tex>, <ref>[https://ru.wikipedia.org/wiki/%C0%EB%E3%EE%F0%E8%F2%EC_%D8%EE%F0%E0 Википедия {{---}} Алгоритм Шора]</ref>
* Сделать полный перебор за <tex>{\sqrt{n}}</tex> <ref>[https://ru.wikipedia.org/wiki/%C0%EB%E3%EE%F0%E8%F2%EC_%C3%F0%EE%E2%E5%F0%E0 Алгоритм Гровера]</ref>
+
* сделать полный перебор за <tex>{\sqrt{n}}</tex>, <ref>[https://ru.wikipedia.org/wiki/%C0%EB%E3%EE%F0%E8%F2%EC_%C3%F0%EE%E2%E5%F0%E0 Википедия {{---}}Алгоритм Гровера]</ref>
* Осуществить дискретный алгоритм нахождения логарифма за полиномиальное время
+
* осуществить [[Дискретное логарифмирование в группе|дискретный алгоритм нахождения логарифма]] за полиномиальное время, <ref>[http://cs.mipt.ru/docs/comp/rus/develop/other/quantum_comp/ Квантовые компьютеры  и квантовые вычисления]
* Создать стойкую криптосистему: если "подслушать" квантовый бит, то он изменится <ref>[http://habrahabr.ru/post/127461/ Квантовая криптография стучится в дверь]</ref>
+
</ref>
 +
* создать стойкую криптосистему: если "подслушать" квантовый бит, то он изменится. <ref>[http://habrahabr.ru/company/web_payment_ru/blog/229699// Habrahabr {{---}} Квантовые деньги ]</ref>
 
Построение квантового компьютера в виде реального физического прибора является фундаментальной задачей физики XXI века. В настоящее время построены только ограниченные его варианты (в пределах 512 кубит).
 
Построение квантового компьютера в виде реального физического прибора является фундаментальной задачей физики XXI века. В настоящее время построены только ограниченные его варианты (в пределах 512 кубит).
  
Строка 149: Строка 153:
 
* [[Контактная схема]]
 
* [[Контактная схема]]
  
== Источники информации ==
+
==Примечания==
* [http://nuclphys.sinp.msu.ru/nseminar/30.10.12.pdf Философия квантовых вычислений]
 
  
* [http://qilab.phys.msu.ru/papers/kurs4-sych-ru.pdf Исследование возможностей реализации квантовых алгоритмов на аналоговых вычислительных машинах ]
+
<references />
  
*[http://old.kpfu.ru/eng/departments/ktk/RESOURCE/posobie.pdf Квантовые вычисления]
+
== Источники информации ==
 +
* [http://nuclphys.sinp.msu.ru/nseminar/30.10.12.pdf Страхова С.И. "Философия квантовых вычислений"]
  
*[http://www.yury.name/modern/09modernnote.pdf Введение в квантовые вычисления]
+
* [http://qilab.phys.msu.ru/papers/kurs4-sych-ru.pdf Сыч Д.В. "Исследование возможностей реализации квантовых алгоритмов на аналоговых вычислительных машинах ]
  
==Примечания==
+
*[http://old.kpfu.ru/eng/departments/ktk/RESOURCE/posobie.pdf Гайнутдинова А. Ф. "Квантовые вычисления"]
  
<references />
+
*[http://www.yury.name/modern/09modernnote.pdf Ю. Лифшиц "Введение в квантовые вычисления"]
  
 +
*[http://habrahabr.ru/post/127461/ Квантовая криптография стучится в дверь]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Схемы из функциональных элементов ]]
 
[[Категория: Схемы из функциональных элементов ]]

Текущая версия на 19:31, 4 сентября 2022

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

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


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

Классический компьютер состоит из элементарных ячеек – битов, двум состояниям которых приписываются значения [math]1[/math] или [math]0[/math]. В наборе битов (регистре) записывается и обрабатывается информация в виде двоичных чисел. Один бит имеет два базисных состояния [math]0[/math] и [math]1[/math]. Перебирая эти базисные состояния, можно закодировать двоичное число длиной [math]N[/math]. Например, в системе из трех битов можно записать одну из восьми последовательностей нулей и единиц.

Состояния квантовой системы и их преобразования можно описать используя компактные бра/кет обозначения. Бра и кет (англ. bracket — скобка)— обозначения, введенные Дираком на заре зарождения квантовой механики как удобное средство манипулирования векторами. Кет-векторами [math]\mid x\bigr\rangle[/math] обозначают вектор-столбцы и обычно используют для описания квантовых состояний. В середине скобки, по Дираку, должен помещаться индекс состояния, т.е. величина или набор величин, которые определяют состояние системы. Бра-вектор [math]\left\langle y\right|[/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]a, b[/math] – комплексные числа, [math]{\left|a\right|^2}+ {\left|b\right|^2}=1[/math]. Таким образом, квантовый бит может принимать бесконечно много значений, но как результат измерения мы получим либо состояние [math]\mid0\bigr\rangle[/math] с вероятностью [math]{\left|a\right|^2} [/math], либо состояние [math]\mid 1\bigr\rangle[/math] с вероятностью [math]{\left|b\right|^2} [/math].

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

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

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

Матрица гейта умножается на столбец весовых коэффициентов регистра и получается новый столбец, соответствующий новому состоянию регистра. В случае, если в действии гейта не участвуют некоторые кубиты, то их и не включают в матрицу, т.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]\mid q\bigr\rangle\to \begin{pmatrix} a \\ b \end{pmatrix}[/math].

Поэтому квантовым аналогом классического [math]NOT[/math]-гейта является матрица вида:

[math]X\equiv\begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}[/math]

[math]X\times\begin{pmatrix} a\\ b\end{pmatrix}=\begin{pmatrix} b\\ a\end{pmatrix}[/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]CNOT[/math]. В квантовых вычислениях вводится подобный гейт, который имеет два входных кубита и два кубита на выходе. Как и в классическом случае один из пары кубитов называется контролирующим, а второй контролируемым или кубитом-мишенью. Логика выполнения операции при этом определяется следующим образом: если контролирующий кубит находится в состоянии [math]\left |\ 1\right \rangle[/math], тогда контролируемый кубит подвергается квантовой операции [math]NOT[/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 (1).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) SWAP'.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) CCNOT.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] (гейт Фредкина) CSWAP'.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]

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

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

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

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

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

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

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

См.также

Примечания

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