1632
правки
Изменения
м
|definition='''Любая логическая операция с кубитами называется '''квантовым гейтом ''' (англ. ''quantum gate'').'''
По числу задействованных ==Отличие кубитов гейты делятся на одно- и многокубитные. Гейт переводит одно состояние регистра в другое. Действие гейта на регистр можно записать так: <tex>G\mid R\bigr\rangleот классических битов==\mid R^\prime\bigr\rangle</tex>.
Гейты Классический компьютер состоит из элементарных ячеек – линейные операции: битов, двум состояниям которых приписываются значения <tex>G1</tex> или <tex>0</tex>. В наборе битов (\mid p\bigr\rangle+\mid g\bigr\rangleрегистре)=G\mid p\bigr\rangle+G\mid g\bigr\rangleзаписывается и обрабатывается информация в виде двоичных чисел. Один бит имеет два базисных состояния <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>0\mid q\bigr\rangle=a\mid0\bigr\rangle+b\mid 1\bigr\rangle</tex>. В наборе битов (регистре) записывается и обрабатывается информация в виде двоичных чисел. Один бит имеет два базисных состояния , где <tex>0a, b</tex> и – комплексные числа, <tex>{\left|a\right|^2}+ {\left|b\right|^2}=1</tex>. Система из Таким образом, квантовый бит может принимать бесконечно много значений, но как результат измерения мы получим либо состояние <tex>N\mid0\bigr\rangle</tex> битов имеет с вероятностью <tex>2N{\left|a\right|^2} </tex> базисных состояний. Перебирая эти базисные состояния, можно закодировать двоичное число длиной либо состояние <tex>N\mid 1\bigr\rangle</tex>. Например, в системе из трех битов можно записать '''одну''' из восьми последовательностей нулей и единиц свероятностью <tex>000, 001, 011, 010, 100, 101, 110, 111{\left|b\right|^2} </tex>.
Состояния Наиболее важным отличием кубитов от классических битов является не непрерывная природа суперпозиционных состояний, а возможность квантового перепутывания состояний в системе кубитов. В квантовой механике размерность пространства состояний системы и их преобразования можно описать используя компактные брав целом есть произведение размерностей пространств состояний отдельных подсистем. Система из <tex>N</tex> кубитов имеет <tex>2^N</кет обозначения, введённые Диракомtex> базисных состояний. Кет-векторами Произвольное состояние <tex>N</tex>кубитов <tex>a_1\mid0\bigr\rangle+b_1\mid x1\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>\langle y\midN=3</tex> все <tex>8</tex> обозначают сопряжение двоичных чисел могут быть закодированы в трех кубитах '''одновременно'''. Это становится возможным за счет квантовомеханического перепутывания. Нелокальные корреляции в системе кубитов и транспонирование кет-векторовобеспечивают экспоненциально большое вычислительное пространство и параллелизм квантовых вычислений.
В квантовом компьютере элементарными ячейками для записи информации являются квантовые биты – кубитыПо числу задействованных кубитов гейты делятся на одно- и многокубитные. Кубит – это квантовая система, которая, как и бит, имеет два базисных состояния Набор <tex>\mid0\bigr\rangleN</tex> и <tex>\mid 1\bigr\rangle</tex>, но кубитов составляет квантовый регистр. Гейт переводит одно состояние регистра в отличие от бита, кубит может находиться в любом суперпозиционном состоянии другое. Действие гейта на регистр можно записать так: <tex>G\mid qR\bigr\rangle=a\mid0mid R^\bigr\rangle+b\mid 1prime\bigr\rangle</tex>. Состояние кубита – "немного" (с вероятностью <tex>\left| {a^2} \right|</tex>) ложно и "немного" (с вероятностью <tex>\left| {b^2} \right|</tex> ) истинно. Набор <tex>N</tex> кубитов составляет квантовый регистр.
Наиболее важным отличием кубитов от классических битов является не непрерывная природа суперпозиционных состояний, а возможность квантового перепутывания состояний в системе кубитов. В квантовой механике размерность пространства состояний системы в целом есть произведение (а не сумма) размерностей пространств состояний отдельных подсистем. Система из <tex>N</tex> кубитов имеет <tex>2^N</tex>, а не <tex>2N</tex> базисных состояний. Произвольное состояние N кубитов Гейты – линейные операции: <tex> G(a_1\mid0mid p\bigr\rangle+b_1\mid 1g\bigr\rangle)(a_2\mid0\bigr\rangle+b_2= G\mid 1\bigr\rangle)...(a_n\mid0p\bigr\rangle+b_nG\mid 1g\bigr\rangle)</tex> содержит все возможные бинарные строки (комбинации из нулей и единиц) длиной <tex>N</tex>. В приведенном выше примере для <tex>N=3</tex> все <tex>8</tex> двоичных чисел могут быть закодированы в трех кубитах '''одновременно'''.
* [http:<references //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 Ю. Лифшиц "Введение в квантовые вычисления"]
rollbackEdits.php mass rollback
Идея квантового компьютера, высказанная Фейнманом (англ. ''Richard Phillips Feynman'') в 1982 году, достаточно проста. Она состоит в построении компьютера на основе квантовых, а не классических элементарных ячеек. Законы квантовой механики, определяющие поведение таких '''квантовых битов''' (англ. ''quantum bit'') – кубитов, обеспечивают огромные преимущества (скорость и параллелизм вычислений) квантового компьютера по сравнению с классическим компьютером.
{{Определение
}}
== Демонстрация действия гейта на кубит ==
Матрица гейта умножается на столбец весовых коэффициентов регистра и получается новый столбец, соответствующий новому состоянию регистра. В случае, если в действии гейта не участвуют некоторые кубиты, то их и не включают в матрицу, т.e. в матрице записано только реальное действие кубитов.
Таблица истинности отражает действие гейта на базисные состояния. Ее структура имеет следующий вид: по горизонтали записывается записываются слева начальные состояния входящих кубитов, а справа — соответствующие конечные. По вертикали записываются все базисные состояния. Пример матричной записи кубита и таблиц истинности будет дан в таблице ниже.
Также используется графическая форма записи квантовых алгоритмов. Гейты обозначаются некоторыми символами (часто это кружок или квадрат с цифрой или буквой внутри). Кубиты представлены горизонтальными нитями. Действие гейта на кубит показывается путем "нанизывания" гейта на нужный кубит (или несколько кубитов, если это не однобитный гейт). Квантовый алгоритм представляется в виде сети таких гейтов и называется квантовой сетью. Слева в такой сети находятся начальные состояния кубитов, справа — конечные. Действие алгоритма заключается в прохождении кубитов по своим нитям через гейты слева направо.
===Однокубитный гейт <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>.,
т.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> (англ. ''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</tex>. В квантовых вычислениях вводится подобный гейт, который имеет два входных кубита и два кубита на выходе. Как и в классическом случае это просто один из пары кубитов называется контролирующим, а второй контролируемым или кубитом-мишенью. Логика выполнения операции при этом определяется следующим образом: если контролирующий кубит находится в состоянии <tex>\left |\ 1\right \rangle</tex>, тогда контролируемый кубит подвергается квантовой операции <tex>XORNOT</tex>, в противном случае контролируемый кубит остается без изменения.
===Другие используемые гейты===
===Таблица различных обозначений квантовых гейтов===
{| classborder="wikitable1"cellpadding="20" cellspacing="0"
|-
!название Название гейта||графическое Графическое обозначение||матричная Матричная запись||таблица Таблица истинности
|-
| <tex>NOT</tex> || [[Файл:Not2Not2_(1).png png ]] || <tex>\begin{pmatrix} 0& 1 \\ 1 & 0 \end{pmatrix}</tex> || <tex> \begin{array}{|c|c|}
0 & 1 \\
\end{array}</tex>
|-
|<tex>S</tex> (''swap'')|| [[Файл:SSWAP'.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|}
\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> \begin{array}{|c c c ||c c c|}
A & B & C & A' & B' & C'\\
\end{array}</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
Квантовая модель вычислений позволяет:
* Разложить число [[Разложение на множители за (факторизация)|разложить число <tex>n^2M</tex>. Постановка задачи разложения числа на множители выглядит следующим образом: на вход подается составное число ]] за <tex>NO(\lg^3 M)</tex> в двоичной записи, на выход должны быть выданы два числа <texref>p, q,<[https:/tex> такие что <tex>N = pq</tex>ru.wikipedia. Типичный размер <tex>N<org/tex> порядка <tex>2^{2000}<wiki/tex>. Мотивацией для решения данной задачи является отсутствие на данный момент полиномиального классического алгоритма. Решение этой задачи позволит, например, взломать систему RSA. Лучший из известных классических алгоритмов имеет <tex>O(2^%C0%EB%E3%EE%F0%E8%F2%EC_%D8%EE%F0%E0 Википедия {\sqrt[3]{n---}}) Алгоритм Шора]</texref> в качестве оценки времени работы. Уже сегодня существует квантовый алгоритм, который решает эту задачу за <tex>O(n^2)</tex> [Питер Шор, 1994].* Сделать сделать полный перебор за <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/postcompany/web_payment_ru/blog/229699/127461/ Квантовая криптография стучится в дверьHabrahabr {{---}} Квантовые деньги ]</ref>
Построение квантового компьютера в виде реального физического прибора является фундаментальной задачей физики XXI века. В настоящее время построены только ограниченные его варианты (в пределах 512 кубит).
* [[Контактная схема]]
== Источники информации Примечания==* [http://nuclphys.sinp.msu.ru/nseminar/30.10.12.pdf Философия квантовых вычислений]
== Источники информации ==*[http://oldnuclphys.kpfusinp.msu.ru/engnseminar/departments/ktk/RESOURCE/posobie30.10.12.pdf Квантовые вычисленияСтрахова С.И. "Философия квантовых вычислений"]
*[http://wwwqilab.yuryphys.namemsu.ru/modernpapers/09modernnotekurs4-sych-ru.pdf Введение в квантовые вычисленияСыч Д.В. "Исследование возможностей реализации квантовых алгоритмов на аналоговых вычислительных машинах ]
*[http://habrahabr.ru/post/127461/ Квантовая криптография стучится в дверь]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Схемы из функциональных элементов ]]
