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

Когда обычные компьютеры оперируют с 1 и 0, эти 1 и 0 называются двоичными цифрами, или, для краткости, битами. Поскольку квантовый компьютер имеет дело с 1 и 0, представляющими собой квантовую суперпозицию, они называются квантовыми битами, или кубитами. Достоинства кубитов станут еще более заметными, если мы будем рассматривать большее количество частиц. С помощью 250 вращающихся частиц, или 250 кубитов, можно образовать примерно 10⁷⁵ комбинаций, что больше всего количества атомов во Вселенной. Если бы можно было достичь соответствующей суперпозиции с 250 частицами, то квантовый компьютер смог бы одновременно выполнять 10⁷⁵ вычислений и все их закончить в течение всего лишь одной секунды.

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

Еще одна проблема была вызвана тем, что ученые не знали, как запрограммировать квантовый компьютер, и поэтому не были уверены, какого рода вычисления он способен производить. Однако в 1994 году Питеру Шору из AT&T Bell Laboratories штата Нью-Джерси удалось составить пригодный для квантового компьютера алгоритм. Замечательной новостью для криптоаналитиков было то, что алгоритм Шора описывал ряд шагов, которые могли бы быть использованы квантовым компьютером для разложения на множители гигантского числа, то есть как раз то, что требовалось для взлома шифра RSA. Когда Мартин Гарднер опубликовал задачу по RSA в «Сайентифик Америкен», потребовалась работа шести сотен компьютеров в течение нескольких месяцев, чтобы разложить на множители число, состоящее из 129 цифр. Для сравнения, с помощью алгоритма Шора можно было разложить на множители число, в миллион раз большее, за время, в миллион раз меньшее. К сожалению, он не мог продемонстрировать свой алгоритм для разложения на множители, поскольку по-прежнему не было такого инструмента, как квантовый компьютер.

В 1996 году Лов Гровер, также из Bell Laboratories, разработал еще один мощный алгоритм. Алгоритм Гровера — это способ осуществления поиска в списке с невероятно высокой скоростью, что может казаться не особенно интересным, пока вы не поймете, что это именно то, что требуется для взлома шифра DES.