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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Таблица различных обозначений квантовых гейтов)
м (rollbackEdits.php mass rollback)
 
(не показаны 102 промежуточные версии 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> битов имеет <tex>2N</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>N</tex> кубитов составляет квантовый регистр.
 
  
Наиболее важным отличием кубитов от классических битов является не непрерывная природа суперпозиционных состояний, а возможность квантового перепутывания состояний в системе кубитов. В квантовой механике размерность пространства состояний системы в целом есть произведение (а не сумма) размерностей пространств состояний отдельных подсистем. Система из <tex>N</tex> кубитов имеет <tex>2^N</tex>, а не <tex>2N</tex> базисных состояний.
+
Классический компьютер состоит из элементарных ячеек – битов, двум состояниям которых приписываются значения <tex>1</tex> или <tex>0</tex>. В наборе битов (регистре) записывается и обрабатывается информация в виде двоичных чисел. Один бит имеет два базисных состояния <tex>0</tex> и <tex>1</tex>.  Перебирая эти базисные состояния, можно закодировать двоичное число длиной <tex>N</tex>. Например, в системе из трех битов можно записать одну из восьми последовательностей нулей и единиц.
 
 
{{Определение
 
 
  
|definition=Любая логическая операция с кубитами называется ''квантовым гейтом''.
+
Состояния квантовой системы и их преобразования можно описать используя компактные бра/кет обозначения. Бра и кет (англ. ''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>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>.
  
 
== Демонстрация действия гейта на кубит ==
 
== Демонстрация действия гейта на кубит ==
Строка 23: Строка 24:
 
Для демонстрации действия гейта на кубиты используют матричную запись гейта или таблицу истинности.  
 
Для демонстрации действия гейта на кубиты используют матричную запись гейта или таблицу истинности.  
  
Матрица гейта действует на столбец весовых коэффициентов регистра и получается новый столбец, соответствующий новому состоянию регистра. В случае, если в действии гейта не участвуют некоторые кубиты, то их и не включают в матрицу, т.e. в матрице записано только реальное действие кубитов.  
+
Матрица гейта умножается на столбец весовых коэффициентов регистра и получается новый столбец, соответствующий новому состоянию регистра. В случае, если в действии гейта не участвуют некоторые кубиты, то их и не включают в матрицу, т.e. в матрице записано только реальное действие кубитов.  
  
Таблица истинности отражает действие гейта на базисные состояния. Ее структура имеет следующий вид: по горизонтали записывается слева начальные состояния входящих кубитов, а справа — соответствующие конечные. По вертикали записываются все базисные состояния. Пример матричной записи кубита и таблиц истинности будет дан в таблице ниже.
+
Таблица истинности отражает действие гейта на базисные состояния. Ее структура имеет следующий вид: по горизонтали записываются слева начальные состояния входящих кубитов, а справа — соответствующие конечные. По вертикали записываются все базисные состояния. Пример матричной записи кубита и таблиц истинности будет дан в таблице ниже.
 +
 
 +
Также используется графическая форма записи квантовых алгоритмов. Гейты обозначаются некоторыми символами (часто это кружок или квадрат с цифрой или буквой внутри). Кубиты представлены горизонтальными нитями. Действие гейта на кубит показывается путем "нанизывания" гейта на нужный кубит (или несколько кубитов, если это не однобитный гейт). Квантовый алгоритм представляется в виде сети таких гейтов и называется квантовой сетью. Слева в такой сети находятся начальные состояния кубитов, справа — конечные. Действие алгоритма заключается в прохождении кубитов по своим нитям через гейты слева направо.
  
 
== Описание используемых гейтов ==
 
== Описание используемых гейтов ==
  
 
В квантовом случае, как и в теории классических вычислений, любую обратимую унитарную операцию на кубитах можно представить как совокупность базовых операций. Базисом квантовой логики может служить один трехкубитный гейт (например
 
В квантовом случае, как и в теории классических вычислений, любую обратимую унитарную операцию на кубитах можно представить как совокупность базовых операций. Базисом квантовой логики может служить один трехкубитный гейт (например
Тоффоли <tex>(CCNOT)</tex> или Фредкина <tex>(CSWAP)</tex> — описание этих гейтов будет дано ниже) или
+
Тоффоли <tex>(CCNOT)</tex> или Фредкина <tex>(CSWAP)</tex>) или
 
один однокубитный и один двукубитный гейт (например <tex>NOT</tex> и <tex>CNOT</tex>)
 
один однокубитный и один двукубитный гейт (например <tex>NOT</tex> и <tex>CNOT</tex>)
  
 
===Однокубитный гейт <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>, в противном случае контролируемый кубит остается без изменения.
  
 
===Другие используемые гейты===
 
===Другие используемые гейты===
  
Кроме упомянутых выше гейтов <tex>NOT</tex> и <tex>CNOT</tex> в квантовых вычислениях используются также некоторые другие гейты. Их применение не необходимо, но запись алгоритма с их помощью намного проще. На практике часто используются такие гейты: однобитный <tex>H</tex> (''Hadamard''), двубитные <tex>R</tex> (''rotate''), <tex>S</tex> (''swap''), трехбитные <tex>CCNOT</tex> (гейт Тоффоли), <tex> CSWAP</tex> (гейт Фредкина).
+
Кроме упомянутых выше гейтов <tex>NOT</tex> и <tex>CNOT</tex> в квантовых вычислениях используются также некоторые другие гейты. Их применение не необходимо, но запись алгоритма с их помощью намного проще. На практике часто используются такие гейты: однобитный <tex>H</tex> (англ. ''Hadamard''), двубитный <tex>S</tex> (англ. ''swap''), трехбитные <tex>CCNOT</tex> (гейт Тоффоли), <tex> CSWAP</tex> (гейт Фредкина).
 +
 
 +
Гейт Тоффоли инвертирует кубит <tex>B</tex> при условии что значение кубитов <tex>A</tex> и <tex>C</tex> равны <tex>1</tex>.
 +
 
 +
Гейт Фредкина устроен следующим образом: он осуществляет перестановку кубитов <tex>B</tex> и <tex>C</tex> при условии, что значение кубита <tex>A</tex> равно <tex>0</tex>.
  
 
===Таблица различных обозначений квантовых гейтов===
 
===Таблица различных обозначений квантовых гейтов===
  
{| class="wikitable"
+
{| border="1" cellpadding="20" cellspacing="0"
 +
 
 
|-
 
|-
!название гейта||графическое обозначение||матричная запись||таблица истинности  
+
!Название гейта||Графическое обозначение||Матричная запись||Таблица истинности  
 
|-
 
|-
| <tex>NOT</tex>          ||        || <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 \\
Строка 62: Строка 78:
 
  \end{array}</tex>     
 
  \end{array}</tex>     
 
|-
 
|-
|<tex>CNOT</tex> ||   || <tex>\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 1 & 0& 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}</tex>  ||  <tex> \begin{array}{|c c|c c|}
+
|<tex>CNOT</tex> ||[[Файл:Cnot2.jpg‎]]    || <tex>\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 1 & 0& 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}</tex>  ||  <tex> \begin{array}{|c c|c c|}
 
    
 
    
 
    
 
    
Строка 71: Строка 87:
 
  \end{array}</tex>
 
  \end{array}</tex>
 
|-
 
|-
|<tex>H</tex> (''Hadamard'')||   || <tex >\frac{1}{\sqrt{2}}\begin{pmatrix} 1&  1 \\ 1 & -1 \end{pmatrix}</tex> ||
+
|<tex>H</tex> (''Hadamard'')||[[Файл:H.png ]]‎  || <tex >\frac{1}{\sqrt{2}}\begin{pmatrix} 1&  1 \\ 1 & -1 \end{pmatrix}</tex> ||<tex> \begin{array}{|c|c|}
 +
 
 +
  1 &\frac{1}{\sqrt{2}} \\
 +
  0 & \frac{1}{\sqrt{2}}\\
 +
 
 +
\end{array}</tex>   
 
|-
 
|-
|<tex>S</tex> (''swap'')||     ||   ||
+
|<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|}
 +
 
 +
 
 +
  0 & 0 & 0 & 0 \\
 +
  0 & 1 & 1 & 0 \\
 +
  1 & 0 & 0 & 1 \\
 +
  1 & 1 & 1 & 1 \\
 +
\end{array}</tex>
 
|-
 
|-
|<tex>CCNOT</tex> (''Toffoli'')||   ||<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|}
 +
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}</tex>
 
|-
 
|-
|<tex>CSWAP</tex> (гейт Фредкина)||  ||    ||
+
|<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'\\
 +
\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}</tex>
 
|}
 
|}
 +
 +
==Применение квантовых гейтов==
 +
 +
Квантовая модель вычислений позволяет:
 +
*[[Разложение на множители (факторизация)|разложить число <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>
 +
* осуществить [[Дискретное логарифмирование в группе|дискретный алгоритм нахождения логарифма]] за полиномиальное время, <ref>[http://cs.mipt.ru/docs/comp/rus/develop/other/quantum_comp/ Квантовые компьютеры  и квантовые вычисления]
 +
</ref>
 +
* создать стойкую криптосистему: если "подслушать" квантовый бит, то он изменится. <ref>[http://habrahabr.ru/company/web_payment_ru/blog/229699// Habrahabr {{---}} Квантовые деньги ]</ref>
 +
Построение квантового компьютера в виде реального физического прибора является фундаментальной задачей физики XXI века. В настоящее время построены только ограниченные его варианты (в пределах 512 кубит).
 +
 +
В 2005 году группой Ю. Пашкина  при помощи японских специалистов был построен двухкубитный квантовый процессор на сверхпроводящих элементах.
 +
 +
В ноябре 2009 года физикам из Национального института стандартов и технологий в США впервые удалось собрать программируемый квантовый компьютер, состоящий из двух кубит.
 +
 +
11 мая 2011 года представлен компьютер D-Wave One, созданный на базе 128-кубитного процессора.
 +
 +
В декабре 2012 года представлен новый процессор Vesuvius, который объединяет 512 кубит.
 +
 +
== См.также ==
 +
* [[Троичная логика]]
 +
* [[Контактная схема]]
 +
 +
==Примечания==
 +
 +
<references />
 +
 +
== Источники информации ==
 +
* [http://nuclphys.sinp.msu.ru/nseminar/30.10.12.pdf Страхова С.И. "Философия квантовых вычислений"]
 +
 +
* [http://qilab.phys.msu.ru/papers/kurs4-sych-ru.pdf Сыч Д.В. "Исследование возможностей реализации квантовых алгоритмов на аналоговых вычислительных машинах ]
 +
 +
*[http://old.kpfu.ru/eng/departments/ktk/RESOURCE/posobie.pdf Гайнутдинова А. Ф. "Квантовые вычисления"]
 +
 +
*[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 кубит.

См.также

Примечания

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