Квантовый компьютер

Интернет магазин китайских планшетных компьютеров

Компьютеры - Квантовый компьютер - Теория

22 января 2011

Оглавление:
1. Квантовый компьютер
2. Теория
3. Применение квантовых компьютеров
4. Физические реализации квантовых компьютеров
5. Пример реализации операции CNOT на зарядовых состояниях электрона в квантовых точках

Кубиты

Идея квантовых вычислений, впервые высказанная Ю. И. Маниным и Р. Фейнманом, состоит в том, что квантовая система из L двухуровневых квантовых элементов имеет 2 линейно независимых состояний, а значит, вследствие принципа квантовой суперпозиции, пространством состояний такого квантового регистра является 2-мерное гильбертово пространство. Операция в квантовых вычислениях соответствует повороту вектора состояния регистра в этом пространстве. Таким образом, квантовое вычислительное устройство размером L кубит фактически задействует одновременно 2 классических состояний.

Физическими системами, реализующими кубиты, могут быть любые объекты, имеющие два квантовых состояния: поляризационные состояния фотонов, электронные состояния изолированных атомов или ионов, спиновые состояния ядер атомов, и т.д.

Один классический бит может находиться в одном и только в одном из состояний $|0\rangle$ или $|1\rangle$ . Квантовый бит, называемый кубитом, находится в состоянии $|\psi\rangle=a\,|0\rangle+b\,|1\rangle$ , так что |a|² и |b|² — вероятности получить 0 или 1 соответственно при измерении этого состояния; $a,b \in \mathbb{C}$ ; |a|² + |b|² = 1. Сразу после измерения кубит переходит в базовое квантовое состояние, соответствующее классическому результату.

Пример:

Имеется кубит в квантовом состоянии $\frac45\,|0\rangle-\frac35\,|1\rangle$

В этом случае, вероятность получить при измерении

0	составляет	²=16/25	= 64 %,
1		²=9/25	= 36 %.

В данном случае, при измерении мы получили 0 с 64 % вероятностью.

В результате измерения кубит переходит в новое квантовое состояние $|0\rangle$ , то есть, при следующем измерении этого кубита мы получим 0 со стопроцентной вероятностью.

Приведем для объяснения два примера из квантовой механики: 1) фотон находится в состоянии $|\psi\rangle$ суперпозиции двух поляризаций. Это состояние есть вектор в двумерной плоскости, систему координат в которой можно представлять как две перпендикулярные оси, так что a и b есть проекции $|\psi\rangle$ на эти оси; измерение раз и навсегда коллапсирует состояние фотона в одно из состояний $|0\rangle$ или $|1\rangle$ , причем вероятность коллапса равна квадрату соответствующей проекции. Полная вероятность получается по теореме Пифагора.

Если мы измерим только первый кубит квантовой системы, находящейся в состоянии $|\Psi\rangle$ , у нас получится:

С вероятностью p₀ = | a | + | b | первый кубит перейдет в состояние $|0\rangle$ а второй — в состояние $\frac{1}{\sqrt{|a|^2+|b|^2}}$ , а
С вероятностью p₁ = | c | + | d | первый кубит перейдет в состояние $|1\rangle$ а второй — в состояние $\frac{1}{\sqrt{|c|^2+|d|^2}}$ .

В первом случае измерение даст состояние $|\Psi_0\rangle=|0\rangle\bigotimes\frac{1}{\sqrt{|a|^2+|b|^2}}$ , во втором — состояние $|\Psi_1\rangle=|1\rangle\bigotimes\frac{1}{\sqrt{|c|^2+|d|^2}}$

Мы снова видим, что результат такого измерения невозможно записать как вектор в гильбертовом пространстве состояний. Такое состояние, в котором участвует наше незнание о том, какой же результат получится на первом кубите, называют смешанным состоянием. В нашем случае такое смешанное состояние называют проекцией исходного состояния $|\Psi\rangle$ на второй кубит, и записывают в виде матрицы плотности вида $\rho_2=p_0\rho_{\Psi_0}+p_1\rho_{\Psi_1}$ где матрица плотности состояния $|\psi\rangle$ определяется как $|\psi\rangle\langle\psi |$ .

В общем случае системы из L кубитов, у неё 2 классических состояний, …00001, … , 11111…), каждое из которых может быть измерено с вероятностями 0—100 %.

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

Вычисление

Упрощённая схема вычисления на квантовом компьютере выглядит так: берется система кубитов, на которой записывается начальное состояние. Затем состояние системы или её подсистем изменяется посредством унитарных преобразований, выполняющих те или иные логические операции. В конце измеряется значение, и это результат работы компьютера. Роль проводов классического компьютера играют кубиты, а роль логических блоков классического компьютера играют унитарные преобразования. Такая концепция квантового процессора и квантовых логических вентилей была предложена в 1989 году Д. Дейчем. Также Д. Дейч в 1995 году нашёл универсальный логический блок, с помощью которого можно выполнять любые квантовые вычисления.

Оказывается, что для построения любого вычисления достаточно двух базовых операций. Квантовая система дает результат, только с некоторой вероятностью являющийся правильным. Но за счет небольшого увеличения операций в алгоритме можно сколь угодно приблизить вероятность получения правильного результата к единице.

С помощью базовых квантовых операций можно симулировать работу обычных логических элементов, из которых сделаны обычные компьютеры. Поэтому любую задачу, которая решена сейчас, квантовый компьютер решит, и почти за такое же время. Следовательно, новая схема вычислений будет не слабее нынешней.

Чем же квантовый компьютер лучше классического? Большая часть современных ЭВМ работают по такой же схеме: n бит памяти хранят состояние и каждый такт времени изменяются процессором. В квантовом случае система из n кубитов находится в состоянии, являющимся суперпозицией всех базовых состояний, поэтому изменение системы касается всех 2 базовых состояний одновременно. Теоретически новая схема может работать намного быстрее классической. Практически алгоритм Гровера поиска в базе данных показывает квадратичный прирост мощности против классических алгоритмов

Алгоритмы

Главная статья Квантовый алгоритм

Алгоритм Гровера позволяет найти решение уравнения $f=1,\; 0\le x < N$ за время $O$ .
Алгоритм Шора позволяет разложить натуральное число n на простые множители за полиномиальное от log время.
Алгоритм Залки — Визнера позволяет моделировать унитарную эволюцию квантовой системы системы n частиц за почти линейное время с использованием O кубит.
Алгоритм Дойча — Джоза позволяет «за одно вычисление» определить, является ли функция двоичной переменной f постоянной = 0, f₂ = 1 независимо от n) или «сбалансированной» = 0, f₃ = 1; f₄ = 1, f₄ = 0).

Было показано, что не для всякого алгоритма возможно «квантовое ускорение». Более того, возможность получения квантового ускорения для произвольного классического алгоритма является большой редкостью .

Квантовая телепортация

Алгоритм телепортации реализует точный перенос состояния одного кубита на другой. В простейшей схеме используются 4 кубита: источник, приёмник и два вспомогательных. Отметим, что в результате работы алгоритма первоначальное состояние источника разрушится — это пример действия общего принципа невозможности клонирования — невозможно создать точную копию квантового состояния, не разрушив оригинал. На самом деле, довольно легко создать одинаковые состояния на кубитах. К примеру, измерив 3 кубита, мы переведем каждый из них в базовые состояния и хотя бы на двух из них они совпадут. Не получится скопировать произвольное состояние, и телепортация — замена этой операции.

Телепортация позволяет передавать квантовое состояние системы с помощью обычных классических каналов связи. Таким образом, можно, в частности, получить связанное состояние системы, состоящей из подсистем, удаленных на большое расстояние.

<<< MIMD

Нейрокомпьютер >>>

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие