Квантовые гейты — различия между версиями
(→Источники информации) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 84 промежуточные версии 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>. Например, в системе из трех битов можно записать одну из восьми последовательностей нулей и единиц. | |
− | + | Состояния квантовой системы и их преобразования можно описать используя компактные бра/кет обозначения. Бра и кет (англ. ''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 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 | ||
== Демонстрация действия гейта на кубит == | == Демонстрация действия гейта на кубит == | ||
Строка 25: | Строка 26: | ||
Матрица гейта умножается на столбец весовых коэффициентов регистра и получается новый столбец, соответствующий новому состоянию регистра. В случае, если в действии гейта не участвуют некоторые кубиты, то их и не включают в матрицу, т.e. в матрице записано только реальное действие кубитов. | Матрица гейта умножается на столбец весовых коэффициентов регистра и получается новый столбец, соответствующий новому состоянию регистра. В случае, если в действии гейта не участвуют некоторые кубиты, то их и не включают в матрицу, т.e. в матрице записано только реальное действие кубитов. | ||
− | Таблица истинности отражает действие гейта на базисные состояния. Ее структура имеет следующий вид: по горизонтали | + | Таблица истинности отражает действие гейта на базисные состояния. Ее структура имеет следующий вид: по горизонтали записываются слева начальные состояния входящих кубитов, а справа — соответствующие конечные. По вертикали записываются все базисные состояния. Пример матричной записи кубита и таблиц истинности будет дан в таблице ниже. |
− | Также используется графическая форма записи квантовых алгоритмов. Гейты обозначаются некоторыми символами (часто это кружок или квадрат с цифрой или буквой внутри). Кубиты представлены горизонтальными нитями. Действие гейта на кубит показывается путем "нанизывания" гейта на нужный кубит (или несколько кубитов, если это не однобитный гейт. Квантовый алгоритм представляется в виде сети таких гейтов и называется квантовой сетью. Слева в такой сети находятся начальные состояния кубитов, справа — конечные. Действие алгоритма заключается в прохождении кубитов по своим нитям через гейты слева направо. | + | Также используется графическая форма записи квантовых алгоритмов. Гейты обозначаются некоторыми символами (часто это кружок или квадрат с цифрой или буквой внутри). Кубиты представлены горизонтальными нитями. Действие гейта на кубит показывается путем "нанизывания" гейта на нужный кубит (или несколько кубитов, если это не однобитный гейт). Квантовый алгоритм представляется в виде сети таких гейтов и называется квантовой сетью. Слева в такой сети находятся начальные состояния кубитов, справа — конечные. Действие алгоритма заключается в прохождении кубитов по своим нитям через гейты слева направо. |
== Описание используемых гейтов == | == Описание используемых гейтов == | ||
Строка 37: | Строка 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>-гейта является матрица вида: | ||
− | + | <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>CNOT</tex>. В квантовых вычислениях вводится подобный гейт, который имеет два входных кубита и два кубита на выходе. Как и в классическом случае один из пары кубитов называется контролирующим, а второй контролируемым или кубитом-мишенью. Логика выполнения операции при этом определяется следующим образом: если контролирующий кубит находится в состоянии <tex>\left |\ 1\right \rangle</tex>, тогда контролируемый кубит подвергается квантовой операции <tex>NOT</tex>, в противном случае контролируемый кубит остается без изменения. |
===Другие используемые гейты=== | ===Другие используемые гейты=== | ||
− | Кроме упомянутых выше гейтов <tex>NOT</tex> и <tex>CNOT</tex> в квантовых вычислениях используются также некоторые другие гейты. Их применение не необходимо, но запись алгоритма с их помощью намного проще. На практике часто используются такие гейты: однобитный <tex>H</tex> (''Hadamard''), двубитный <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>A</tex> и <tex>C</tex> равны <tex>1</tex>. | ||
Строка 57: | Строка 66: | ||
===Таблица различных обозначений квантовых гейтов=== | ===Таблица различных обозначений квантовых гейтов=== | ||
− | {| | + | {| border="1" cellpadding="20" cellspacing="0" |
+ | |||
|- | |- | ||
− | ! | + | !Название гейта||Графическое обозначение||Матричная запись||Таблица истинности |
|- | |- | ||
− | | <tex>NOT</tex> || [[Файл: | + | | <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 \\ | ||
Строка 68: | Строка 78: | ||
\end{array}</tex> | \end{array}</tex> | ||
|- | |- | ||
− | |<tex>CNOT</tex> ||[[Файл: | + | |<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|} |
Строка 79: | Строка 89: | ||
|<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|} | |<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> | \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|} |
Строка 93: | Строка 103: | ||
\end{array}</tex> | \end{array}</tex> | ||
|- | |- | ||
− | |<tex>CCNOT</tex> (''Toffoli'')|| [[Файл: | + | |<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'\\ | ||
Строка 107: | Строка 117: | ||
\end{array}</tex> | \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'\\ | A & B & C & A' & B' & C'\\ | ||
\hline | \hline | ||
Строка 123: | Строка 133: | ||
==Применение квантовых гейтов== | ==Применение квантовых гейтов== | ||
+ | Квантовая модель вычислений позволяет: | ||
+ | *[[Разложение на множители (факторизация)|разложить число <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 кубит). | Построение квантового компьютера в виде реального физического прибора является фундаментальной задачей физики XXI века. В настоящее время построены только ограниченные его варианты (в пределах 512 кубит). | ||
Строка 133: | Строка 149: | ||
В декабре 2012 года представлен новый процессор Vesuvius, который объединяет 512 кубит. | В декабре 2012 года представлен новый процессор Vesuvius, который объединяет 512 кубит. | ||
+ | == См.также == | ||
+ | * [[Троичная логика]] | ||
+ | * [[Контактная схема]] | ||
+ | |||
+ | ==Примечания== | ||
+ | |||
+ | <references /> | ||
== Источники информации == | == Источники информации == | ||
− | * [http://nuclphys.sinp.msu.ru/nseminar/30.10.12.pdf Философия квантовых вычислений] | + | * [http://nuclphys.sinp.msu.ru/nseminar/30.10.12.pdf Страхова С.И. "Философия квантовых вычислений"] |
+ | |||
+ | * [http://qilab.phys.msu.ru/papers/kurs4-sych-ru.pdf Сыч Д.В. "Исследование возможностей реализации квантовых алгоритмов на аналоговых вычислительных машинах ] | ||
− | * [http:// | + | *[http://old.kpfu.ru/eng/departments/ktk/RESOURCE/posobie.pdf Гайнутдинова А. Ф. "Квантовые вычисления"] |
− | *[http:// | + | *[http://www.yury.name/modern/09modernnote.pdf Ю. Лифшиц "Введение в квантовые вычисления"] |
+ | *[http://habrahabr.ru/post/127461/ Квантовая криптография стучится в дверь] | ||
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Схемы из функциональных элементов ]] | [[Категория: Схемы из функциональных элементов ]] |
Текущая версия на 19:31, 4 сентября 2022
Идея квантового компьютера, высказанная Фейнманом (англ. Richard Phillips Feynman) в 1982 году, достаточно проста. Она состоит в построении компьютера на основе квантовых, а не классических элементарных ячеек. Законы квантовой механики, определяющие поведение таких квантовых битов (англ. quantum bit) – кубитов, обеспечивают огромные преимущества (скорость и параллелизм вычислений) квантового компьютера по сравнению с классическим компьютером.
Определение: |
Любая логическая операция с кубитами называется квантовым гейтом (англ. quantum gate). |
Отличие кубитов от классических битов
Классический компьютер состоит из элементарных ячеек – битов, двум состояниям которых приписываются значения
или . В наборе битов (регистре) записывается и обрабатывается информация в виде двоичных чисел. Один бит имеет два базисных состояния и . Перебирая эти базисные состояния, можно закодировать двоичное число длиной . Например, в системе из трех битов можно записать одну из восьми последовательностей нулей и единиц.Состояния квантовой системы и их преобразования можно описать используя компактные бра/кет обозначения. Бра и кет (англ. bracket — скобка)— обозначения, введенные Дираком на заре зарождения квантовой механики как удобное средство манипулирования векторами. Кет-векторами
обозначают вектор-столбцы и обычно используют для описания квантовых состояний. В середине скобки, по Дираку, должен помещаться индекс состояния, т.е. величина или набор величин, которые определяют состояние системы. Бра-вектор обозначает вектор-строку.В квантовом компьютере кубит – это квантовая система, которая, как и бит, имеет два базисных состояния
и , но в отличие от бита, кубит может находиться в любом суперпозиционном состоянии , где – комплексные числа, . Таким образом, квантовый бит может принимать бесконечно много значений, но как результат измерения мы получим либо состояние с вероятностью , либо состояние с вероятностью .Наиболее важным отличием кубитов от классических битов является не непрерывная природа суперпозиционных состояний, а возможность квантового перепутывания состояний в системе кубитов. В квантовой механике размерность пространства состояний системы в целом есть произведение размерностей пространств состояний отдельных подсистем. Система из
кубитов имеет базисных состояний. Произвольное состояние кубитов содержит все возможные бинарные строки (комбинации из нулей и единиц) длиной . В приведенном выше примере для все двоичных чисел могут быть закодированы в трех кубитах одновременно. Это становится возможным за счет квантовомеханического перепутывания. Нелокальные корреляции в системе кубитов и обеспечивают экспоненциально большое вычислительное пространство и параллелизм квантовых вычислений.По числу задействованных кубитов гейты делятся на одно- и многокубитные. Набор
кубитов составляет квантовый регистр. Гейт переводит одно состояние регистра в другое. Действие гейта на регистр можно записать так: .Гейты – линейные операции:
.Демонстрация действия гейта на кубит
Для демонстрации действия гейта на кубиты используют матричную запись гейта или таблицу истинности.
Матрица гейта умножается на столбец весовых коэффициентов регистра и получается новый столбец, соответствующий новому состоянию регистра. В случае, если в действии гейта не участвуют некоторые кубиты, то их и не включают в матрицу, т.e. в матрице записано только реальное действие кубитов.
Таблица истинности отражает действие гейта на базисные состояния. Ее структура имеет следующий вид: по горизонтали записываются слева начальные состояния входящих кубитов, а справа — соответствующие конечные. По вертикали записываются все базисные состояния. Пример матричной записи кубита и таблиц истинности будет дан в таблице ниже.
Также используется графическая форма записи квантовых алгоритмов. Гейты обозначаются некоторыми символами (часто это кружок или квадрат с цифрой или буквой внутри). Кубиты представлены горизонтальными нитями. Действие гейта на кубит показывается путем "нанизывания" гейта на нужный кубит (или несколько кубитов, если это не однобитный гейт). Квантовый алгоритм представляется в виде сети таких гейтов и называется квантовой сетью. Слева в такой сети находятся начальные состояния кубитов, справа — конечные. Действие алгоритма заключается в прохождении кубитов по своим нитям через гейты слева направо.
Описание используемых гейтов
В квантовом случае, как и в теории классических вычислений, любую обратимую унитарную операцию на кубитах можно представить как совокупность базовых операций. Базисом квантовой логики может служить один трехкубитный гейт (например Тоффоли
или Фредкина ) или один однокубитный и один двукубитный гейт (например и )Однокубитный гейт
Однокубитная логическая операция
переводит в ,т.e. переставляет весовые коэффициенты кубита местами.
Квантовому состоянию кубита соответствует столбец
.Поэтому квантовым аналогом классического
-гейта является матрица вида:
Двукубитный гейт
Двубитный гейт
(англ. Controlled NOT), действующий на двукубитное состояние в общем виде записывается так:Простейшим двухкубитным контролируемым гейтом в классическом компьютере является
. В квантовых вычислениях вводится подобный гейт, который имеет два входных кубита и два кубита на выходе. Как и в классическом случае один из пары кубитов называется контролирующим, а второй контролируемым или кубитом-мишенью. Логика выполнения операции при этом определяется следующим образом: если контролирующий кубит находится в состоянии , тогда контролируемый кубит подвергается квантовой операции , в противном случае контролируемый кубит остается без изменения.Другие используемые гейты
Кроме упомянутых выше гейтов
и в квантовых вычислениях используются также некоторые другие гейты. Их применение не необходимо, но запись алгоритма с их помощью намного проще. На практике часто используются такие гейты: однобитный (англ. Hadamard), двубитный (англ. swap), трехбитные (гейт Тоффоли), (гейт Фредкина).Гейт Тоффоли инвертирует кубит
при условии что значение кубитов и равны .Гейт Фредкина устроен следующим образом: он осуществляет перестановку кубитов
и при условии, что значение кубита равно .Таблица различных обозначений квантовых гейтов
Название гейта | Графическое обозначение | Матричная запись | Таблица истинности |
---|---|---|---|
![]() |
|||
![]() |
|||
(Hadamard) | ![]() |
||
(swap) | ![]() |
||
(Toffoli) | ![]() |
| |
(гейт Фредкина) | ![]() |
Применение квантовых гейтов
Квантовая модель вычислений позволяет:
- разложить число за на множители , [1]
- сделать полный перебор за [2] ,
- осуществить дискретный алгоритм нахождения логарифма за полиномиальное время, [3]
- создать стойкую криптосистему: если "подслушать" квантовый бит, то он изменится. [4]
Построение квантового компьютера в виде реального физического прибора является фундаментальной задачей физики XXI века. В настоящее время построены только ограниченные его варианты (в пределах 512 кубит).
В 2005 году группой Ю. Пашкина при помощи японских специалистов был построен двухкубитный квантовый процессор на сверхпроводящих элементах.
В ноябре 2009 года физикам из Национального института стандартов и технологий в США впервые удалось собрать программируемый квантовый компьютер, состоящий из двух кубит.
11 мая 2011 года представлен компьютер D-Wave One, созданный на базе 128-кубитного процессора.
В декабре 2012 года представлен новый процессор Vesuvius, который объединяет 512 кубит.