Изменения

Идея квантового компьютера, высказанная Фейнманом (англ. ''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>1</tex> или <tex>0</tex>. В квантовой механике размерность пространства состояний системы в целом есть произведение наборе битов (а не суммарегистре) размерностей пространств состояний отдельных подсистемзаписывается и обрабатывается информация в виде двоичных чисел. Система из Один бит имеет два базисных состояния <tex>N0</tex> кубитов имеет и <tex>2^N1</tex>. Перебирая эти базисные состояния, а не можно закодировать двоичное число длиной <tex>2NN</tex> базисных состояний. Например, в системе из трех битов можно записать одну из восьми последовательностей нулей и единиц.

{{ОпределениеСостояния квантовой системы и их преобразования можно описать используя компактные бра/кет обозначения. Бра и кет (англ. ''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|definitiona\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>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>.

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

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

Однокубитная логическая операция <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>NOTX\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> (англ. ''Controlled NOT''), действующий на двукубитное состояние в общем виде записывается так:

Простейшим двухкубитным контролируемым гейтом в классическом компьютере является <tex>CNOT</tex>. В квантовых вычислениях вводится подобный гейт, который имеет два входных кубита и два кубита на выходе. Как и в классическом случае это просто один из пары кубитов называется контролирующим, а второй контролируемым или кубитом-мишенью. Логика выполнения операции при этом определяется следующим образом: если контролирующий кубит находится в состоянии <tex>\left |\ 1\right \rangle</tex>, тогда контролируемый кубит подвергается квантовой операции <tex>XORNOT</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>B</tex> при условии что значение кубитов <tex>A</tex> и <tex>C</tex> равны <tex>1</tex>.

{| classborder="wikitable1"cellpadding="20" cellspacing="0" 

!название Название гейта||графическое Графическое обозначение||матричная Матричная запись||таблица Таблица истинности

| <tex>NOT</tex> || [[Файл:Not2_(1).png ]] || <tex>\begin{pmatrix} 0& 1 \\ 1 & 0 \end{pmatrix}</tex> || <tex> \begin{array}{|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|}

|<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'')|| [[Файл: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'')|| [[Файл: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>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|}