Эта странная математика

Недетерминированные машины Тьюринга существуют, как мы уже выяснили, только в нашем воображении. Другое дело – квантовый компьютер, потенциально тоже чрезвычайно мощное устройство, которое уже начали создавать. Как ясно из названия, в основе принципа его работы лежит ряд очень странных явлений из области квантовой механики. А оперирует он не обычными битами (от англ. binary digit – “двоичное число”), а квантовыми, так называемыми кубитами (от англ. quantum bit – “квантовый бит”). Кубит, который может представлять собой просто электрон с неизвестным спином, имеет в контексте квантовых эффектов две характеристики, отсутствующие у обычного бита в традиционном компьютере. Во-первых, он может находиться в суперпозиции состояний: одновременно представлять собой и 0, и 1, а становиться тем или другим только тогда, когда за ним наблюдают. Это же явление можно истолковать и по-другому: квантовый компьютер, вместе со всей остальной вселенной, расщепляется на две копии самого себя, в одной из которых бит 1, а в другой – бит 0, и только при измерении кубита он, вместе с окружающей его вселенной, “схлопывается” в конкретное значение. Второе любопытное свойство, лежащее в основе работы квантовых компьютеров, – запутанность. Два запутанных кубита, даже будучи разделенными в пространстве, так связаны друг с другом явлением, которое окрестили “жутким дальнодействием”, что измерение одного из них мгновенно влияет на измерение второго.

С точки зрения вычислительных возможностей квантовые компьютеры эквивалентны машинам Тьюринга. Но, как мы уже убедились, одно дело уметь что-то вычислить в принципе (когда достаточно времени) и совсем другое – сделать это эффективно. Все, что может (или сможет в будущем) квантовый компьютер, теоретически можно сделать и на классической машине Тьюринга с бумажной лентой, если вы готовы подождать парочку геологических эр, а то и дольше. Эффективность – это совершенно отдельный вопрос. Некоторые виды задач квантовые компьютеры сумеют решать во много раз быстрее, чем сегодняшние традиционные устройства, а вот что касается сути этих задач, то есть того, что способен вычислить квантовый компьютер, его возможности ничем не отличаются от возможностей придуманной Тьюрингом машины.

Профессор Уинфрид Хенсингер (слева) и Себастьян Вайдт работают над прототипом квантового компьютера.

Заманчиво приравнять квантовые компьютеры к недетерминированным машинам Тьюринга, но, увы, это разные вещи. Да, их вычислительные возможности одинаковы, в этом смысле недетерминированные машины Тьюринга не превосходят детерминированные: на ДМТ можно смоделировать как первые, так и вторые. А вот по эффективности квантовым компьютерам вряд ли удастся догнать НМТ, что неудивительно, поскольку НМТ – исключительно гипотетические устройства. Маловероятно, например (хоть это пока и не доказано), что они смогут решать NP-полные задачи за полиномиальное время. Впрочем, одну задачу, которую раньше считали не имеющей такого решения (что предполагало бы ложность равенства “P = NP”), все же удалось с помощью квантовых компьютеров решить за полиномиальное время – это разложение больших чисел на простые множители. В 1994 году американский математик Питер Шор разработал для этого квантовый алгоритм, учитывающий особые свойства такой задачи. К сожалению, аналогичный метод не может быть применен для решения других задач, например NP-полных. Если и можно разработать для квантовых компьютеров полиномиальный алгоритм решения NP-полной задачи, он опять-таки должен задействовать ее специфические особенности.