Но что, если такую параллельную обработку можно было производить без непременного удвоения аппаратуры? Такая идея пришла в голову математику Питеру Шору, работавшему в 1990-х годах в компании Bell Labs: он понял, что для одновременной проверки нескольких вещей можно использовать довольно необычные методы информатики. Речь шла о странной физике квантового мира. В квантовой физике частица – например, электрон – может находиться, по сути дела, одновременно в двух местах, пока не будет произведено ее наблюдение. Эти два положения могут соответствовать числам 0 и 1. Это называется состоянием квантовой суперпозиции. Его преимущество в том, что здесь не требуется удвоения аппаратуры: речь по-прежнему идет об одном-единственном электроне. Но этот электрон хранит не один элемент информации, а два. Такая единица информации имеет особое название – кубит. В отличие от обычных компьютеров, в которых каждый бит должен находиться либо во включенном, либо в выключенном состоянии, то есть содержать либо 0, либо 1, кубит одновременно существует в параллельных квантовых мирах: в одном из них его значение равно 0, а в другом – 1.
Таким образом, было бы полезно создать целую последовательность таких кубитов. Например, если удастся объединить 64 кубита в состоянии квантовой суперпозиции, такой массив сможет одновременно представлять все числа от 0 до 264 – 1. Обычному компьютеру пришлось бы последовательно перебирать все эти числа, присваивая каждому биту значения, равные 0 или 1. Но квантовый компьютер может сделать это одновременно. В результате мой обычный компьютер, как электрон, как бы существует в нескольких параллельных вселенных сразу. В каждой из них эти 64 кубита представляют разные числа.
Тут-то и начинается самое интересное. В каждом из параллельных миров такой компьютер проверяет, является ли то число, которое он представляет, делителем кодового числа. Но как сделать так, чтобы квантовый компьютер сумел выбрать именно тот мир, в котором кодовое число успешно делится на число проверяемое? Именно этот вопрос решает блестящий прием Шора, который он встроил в свой алгоритм. Как только мы производим наблюдение квантовой суперпозиции, она должна принять решение и окончательно перейти в одно или другое состояние. По сути дела, она выбирает положение 0 или положение 1. Переход в то или иное положение определяется вероятностью.
Шор сумел создать такой алгоритм, который обеспечивает, что после проверки на делимость в каждой из параллельных вселенных квантовая суперпозиция с подавляющей вероятностью переходит в состояние того мира, в котором проверенное число оказалось делителем кодового числа. Все остальные миры, в которых результат проверки оказался отрицательным, настолько похожи друг на друга, что они взаимно уничтожаются. Остается только тот мир, в котором деление прошло успешно.