Обыкновенные компьютеры подчиняются законам классической физики. Они полагаются на бинарные числа: единицу и ноль. Эти числа сохраняются и используются для математических операций. В обыкновенных устройствах памяти каждый бит определяется зарядом, то есть, бит может быть или единицей, или нулем.
А в квантовых компьютерах бит может быть одновременно единицей и нулем. Законы квантовой физики позволяют электронам занимать несколько состояний одновременно. Квантовые биты или кубиты таким образом существуют в нескольких взаимопересекающихся состояниях. Эта суперпозиция позволяет выполнять операции со многими значениями буквально одним махом, тогда как обычные компьютеры все делают последовательно.
По крайней мере, так гласит теория. Проблема в том, что эту гипотезу до сих пор не проверили экспериментально. До сих пор.
Роберт Кёниг, профессор теории сложных квантовых систем, вместе с коллегами продемонстрировал преимущество квантовых компьютеров. Для этого они разработали квантовую цепь, которая может решить определенную сложную алгебраическую задачу. У новой цепи очень простая структура — она может совершать только фиксированное количество операций на каждом кубите. Считается, что такая цепь имеет постоянную глубину. Во время эксперимента исследователи доказали, что выбранную ими математическую задачу классическая цепь такой же глубины решить просто не может. Более того, они ответили на вопрос, почему квантовые алгоритмы превосходят любые последовательные алгоритмы: квантовые используют нелокальность квантовой физики.
До этой работы преимущество квантовых компьютеров не было ни доказано, ни экспериментально подтверждено, несмотря на все теоретические выкладки.
