Что такое квантовый компьютер
Что такое квантовый компьютер Говорят: хочешь что-то понять - попробуй объяснить кому-нибудь другому. Кое-кто из френдов меня недавно спрашивал про квантовый компьютер. Составлю краткий конспект, может и сам пойму. :)
Квантовые компьютеры состоят из кубитов (quantum bits, qubits). Они похожи на обычные биты: можно записать FALSE или TRUE, и при чтении тоже получим FALSE или TRUE. Эти два состояния называются базисными, или наблюдаемыми. Но особенность квантовых объектов в том, что для них возможно также множество "промежуточных" состояний, представляющих собой линейные комбинации базисных с комплексными коэффициентами. Например, состояние одного кубита можно представлять в виде вектора (a, b), с ограничением a2+b2=1. Состояние FALSE - это (1, 0), состояние TRUE - (0, 1).
Непосредственно наблюдать такие состояния не получается, и физики до сих пор продолжают спорить, что бы они могли означать. В самой популярной, так называемой копенгагенской интерпретации, квадраты комплексных коэффициентов принято считать вероятностью обнаружить объект в данном базисном состоянии. Но для нас, программистов, это не так важно, хоть горшком назови. А важно, что состояние кубита информационно эквивалентно комплексному числу, вообще говоря, неограниченной точности. Но из всего этого журавля в небе нам доступна только синица: один бит на чтение. Хуже того: при считывании состояния кубита его состояние нарушается и становится равным одному из базисных.
Состояние системы из N кубитов эквивалентно вектору из 2N действительных чисел. Много? Не то слово. Уже для трех сотен кубитов это число существенно превышает количество частиц в наблюдаемой вселенной (порядка 1080). И всю эту кучу можно обрабатывать одним махом, за раз. Поэтому некоторые алгоритмы, требующие экспоненциального времени на обычном компьютере, на квантовом решаются за полиномиальное время.
Обычные компьютеры строятся из логических элементов типа NOT, XOR и т.д. Они принимают несколько битов на вход и на выходе дают некоторое другое количество битов. Известно, что полную систему вычислений можно построить используя всего две операции, NOT и элемент Тоффоли: (a, b, c) -> (a, b, ab+c).
Для кубитов тоже придуманы базовые элементы. Но они имеют некоторые особенности. Количество входов и выходов у эемента должно совпадать. Кроме этого, нельзя размножить кубит: невозможен элемент вида (a, b) -> (a, a). Это следствие того принципа, что все квантовые операции должны быть обратимы.
Пример простого однокубитового элемента: NOT. Преобразует состояние (a, b) в (b, a), в частности FALSE переходит в TRUE и наоборот. Описывается матрицей:
- | 0 1 |
- | 1 0 |
Более интересная однокубитовая операция: элемент Адамара. В отличие от NOT, превращает базисные состояния в смешанные. Описывается матрицей:
- | 1/√2 1/√2 |
- | 1/√2 -1/√2 |
Еще более странный однокубитовый элемент: фазовый сдвиг R(θ). Изменяет соотношение фаз базисных состояний на угол θ. Описывается матрицей:
- | 1 0 |
- | 0 eiθ |
Двухкубитовый элемент: CNOT. Применяет операцию NOT ко второму кубиту, если значение первого кубита равно TRUE. Описывается матрицей:
- | 1 0 0 0 |
- | 0 1 0 0 |
- | 0 0 0 1 |
- | 0 0 1 0 |
Для построения полной системы квантовых вычислений достаточно трёх типов элементов: Адамара, CNOT и фазового сдвига R(θ).
Для забав с квантовыми вычислениями создан экспериментальный язык QCL. Например, алгоритм Гровера выглядит следующим образом:
procedure grover(int n) { int l=floor(log(n,2))+1; // no. of qubits
int m=ceil(pi/8*sqrt(2^l)); // no. of iterations
int x;
int i;
qureg q[l];
qureg f[1];
{
reset;
Mix(q); // prepare superposition
for i= 1 to m { // main loop
query(q,f,n); // calculate C(q)
CPhase(pi,f); // negate |n>
!query(q,f,n); // undo C(q)
diffuse(q); // diffusion operator
}
measure q,x; // measurement
print "measured",x;
} until x==n;
}