- •1) Взлом криптографии.
- •2) Моделирование квантовых физических и химических процессов
- •3) Квантовый поиск по базе данных.
- •1) Кубит.
- •2) Состояния кубита:
- •3) Операции над кубитами
- •1) Cnot (Controlled not Gate)
- •4) Вентиль Фредкина (cswap)
- •2) Вентиль Тоффоли
- •3) Относительный сдвиг фазы
- •2) Квантовые цепочки
- •Описание алгоритмов:
- •1) Алгоритм Шора (1994) — по заданному целому числу n, найти его простые множители.
2) Вентиль Тоффоли
Чтобы построить обратимую вычислительную цепь, нам нужны обратимые логические вентили. 1-битные вентили — единичный, и NOT – обратимы. Единственный нетривиальный 2-битный обратимый вентиль — это CNOT (аналог XOR). Но на NOT и XOR нельзя вычислить все возможные обратимые функции — система неуниверсальна.
1 из вариантов универсального вентиля (т. е. с помощью него можно построить любую обратимую вычислительную цепь) — вентиль Тоффоли, или "controlled-controlled-not". У него 3-битный вход и выход; если первые два бита =1, он обращает третий бит, иначе оставляет всё без изменений.
INPUT |
OUTPUT |
||||
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 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
Вентиль Тоффоли можно реализовать пятью 2-кубитными квантовыми вентилями.
По сути, это означает, что можно создать квантовый компьютер, реализующий любой классический алгоритм. Чтобы реализовать и любой квантовый алгоритм, к нему вдобавок нужен какой-нибудь существенно квантовый вентиль. Например, фазовый сдвиг. Но вообще, подойдёт любой 1-кубитный вентиль с вещественными коэффициентами, создающий нетривиальное квантовое состояние.
Вентиль Тоффоли был реализован на практике в 2009.
3) Относительный сдвиг фазы
Это однокубитный вентиль, определяемый умножением на унитарную матрицу:
Это простейший пример не-классического, квантового вентиля. Он оставляет базовое состояние |0> неизменным, и поворачивает состояние |1> на eiφ. Вероятность измерения |0> или |1> не меняется, но меняется фаза квантового состояния. На сфере Блоха это соответствует повороту в горизонтальной плоскости на угол φ.
4) Вентиль Фредкина (cswap)
Это универсальный вентиль, переставляющий два последних бита, если первый бит=1.
INPUT |
OUTPUT |
||||
C |
I1 |
I2 |
C |
O1 |
O2 |
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 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Его свойство — сохраняется количество 0 и 1. В модели бильярдных шаров это означает, что на выходе то же количество шаров, что и на входе. Это хорошо отвечает сохранению массы в физике, и помогает продемонстрировать, что система не растратна.
Логические цепочки
1) Обратимые логические цепочки: мы бы хотели иметь несколько видов простых обратимых вентилей, которые можно соединять, чтобы получить любую квантовую цепочку.
Например, у нас есть обратимые n-битный вентиль f, и m-битный вентиль g. Соединив их k выходов f с k входами g, мы получим новую (n+m-k)-битную цепочку. И в таких соединениях важно, чтобы промежуточные цепочки также были обратимыми — так чтобы не создавался промежуточный мусор (физически, это означает сохранение энтропии — т. е. мы не теряем информацию в пространство. Для квантовой системы это означает предотвращение декогеренции).
И, можно показать, что, например, вентили Тоффоли — универсальны, и не производят «мусора» - т. е. подходят для наших целей.