Вычисление в обычном компьютере, как правило, требует выполнения большого количества операций, и критический вопрос – как это количество операций растет по мере того, как увеличивается объем входных данных. В целом ряде задач оно растет так быстро, что скоро даже суперкомпьютеру требуются годы вычислений. Актуальным примером является задача разложения чисел на множители – актуальным потому, что на ее сложности для обычных компьютеров основаны распространенные схемы шифрования. Число 15 мы разлагаем на множители (3 и 5) в уме, разложение числа 323 потребует от вас небольших усилий, а машина сделает это шутя, но перед серьезными числами, в несколько сотен знаков, компьютер уже практически бессилен: ему придется перепробовать так много вариантов, что ответ появится только тогда, когда давно уже перестанет представлять интерес. Квантовый же алгоритм разложения на множители обходится без лавинообразного роста числа операций. Требуется только достаточное количество кубитов – а как мы видели, уже тысяча кубитов позволяет оперировать с очень значительными числами.
Причина, по которой квантовый компьютер исполняет некоторые избранные алгоритмы несравненно быстрее, чем обычный компьютер решает ту же задачу с помощью доступных ему методов, – как раз в том, что волновая функция всех кубитов вместе взятых, подчиняясь уравнению Шрёдингера, эволюционирует во времени как единое целое.
Дело даже не в том, что, как часто можно услышать, «каждый кубит является нулем и единицей одновременно» (эта фраза означает попросту, что состояние кубита может быть какой-то комбинацией «a А плюс b Б» с любыми числами a и b). Сила квантового компьютера происходит не столько отсюда, сколько из запутывания различных кубитов и комбинирования состояний, относящихся к группам кубитов. Например, волновая функция группы из четырех кубитов может выражаться как комбинация состояний «А, А, А, А», «Б, Б, Б, Б» и «А, Б, А, Б» (наугад выбранных мною для иллюстрации из 16 возможностей), каждое с каким-то сопровождающим его внутренним числом. Ни про один кубит из четырех при этом нельзя сказать, что он «представляет собой ноль и единицу одновременно». Эволюционирует же во времени, как всегда в квантовой механике, вся комбинация целиком, т. е. «a (А, А, А, А) плюс b (Б, Б, Б, Б) плюс c (А, Б, А, Б)». Собственно говоря, эволюционируют «внутренние» числа a, b, c и так далее – изменяются таким образом, чтобы к концу вычисления самое большое из них сопровождало правильный ответ (если правильный ответ – АБАБ, т. е. число 5, то больше других должно стать число c).
Конечно, эволюционируя в ходе выполнения алгоритма, волновая функция может представлять собой комбинацию всех состояний: всех 16 в только что приведенном примере четырех кубитов, всех 1024, если кубитов десять, или всех 126765060022822-9401496703205376, если кубитов сто. Перед каждым состоянием в результате исполнения квантовой схемы вычислений появится какое-то внутреннее число, определяющее вероятность при финальном измерении. При желании можно думать, что квантовый компьютер пробует все «ответы», правильный наряду со всеми неправильными, но для правильного алгоритм «выращивает» внутреннее число, дающее самую большую вероятность.
Все это неплохо в принципе, но на практике деликатные физические системы легко выходят из-под контроля. Теоретическая схема работы квантового компьютера исключает обмен информацией с окружающей средой в процессе исполнения алгоритма, но на практике полностью исключить взаимодействие с ней нельзя, и в результате среда так и норовит внести неконтролируемые изменения в состояния кубитов. Кроме того, какие-то из преобразований, составляющих схему квантовых вычислений (упомянутый выше CNOT и его друзья), могут выполняться неточно. У каждого физического устройства есть показатель надежности, и это никогда не сто процентов. Финальное измерение также может произойти с ошибкой. Наконец, кубит может втянуться в «разговор» (взаимодействие) с соседним кубитом, в результате чего возникнут непредусмотренные изменения в их состоянии.
При этом ошибки, случающиеся в квантовых компьютерах, более разнообразны, чем в обычных. Там сбой может состоять только в неконтролируемой замене 0 на 1 или наоборот. Средства борьбы с этим развиты чрезвычайно хорошо (в том числе, конечно, из-за необходимости постоянного использования в интернете) и сводятся тем или иным образом к передаче избыточной информации. Иллюстрацией может служить самая незамысловатая схема утроения: вместо 0 вы передаете 000, а вместо 1, понятно, 111. Если в таком случае принимающая сторона получила, скажем, сигнал 010, то в предположении, что произошла одна ошибка (а не две, что менее вероятно), его следует воспринимать как 000, т. е. попросту 0{81}.
Квантовый аналог этой единственной классической ошибки – случайная замена в кубите состояния «А» на состояние «Б» или наоборот. Но кроме этого с кубитом может случиться что-то совсем другое, не имеющее классического аналога: замена состояния «А плюс Б» на «А минус Б» (это два различных состояния, дальнейшая эволюция которых приведет к различным финальным волновым функциям всей системы){82}.
Мало того, что квантовых ошибок больше, исправление их на первый взгляд кажется невыполнимой задачей. Проблема возникает уже с избыточностью: нельзя создать копию квантового состояния, не разрушив оригинал (теорема о запрете клонирования, упоминавшаяся в предыдущей главе). Поэтому отправить три (да и два) одинаковых состояния вместо одного попросту невозможно. Если этого мало, то есть еще одно обстоятельство, тоже фундаментальное. Нельзя «подглядывать», как идут квантовые вычисления: измерение, выполняемое с целью «проверить, нет ли сбоя», разрушает волновую функцию, и из всех содержавшихся в ней возможностей остается одна – волновая функция коллапсирует, вычислению конец (преждевременный).
Борьба с квантовыми ошибками выглядит проигранной еще до того, как она началась. Поэтому неудивительно, что энтузиазм в отношении квантовых вычислений находился на крайне низком уровне до 1995 г., когда был открыт первый квантовый код для исправления ошибок. На помощь пришла запутанность.
Из состояния одного кубита «a А плюс b Б» (с любыми внутренними числами a и b) можно создать состояние трех кубитов «a (А, А, А) плюс b (Б, Б, Б)». Здесь, во-первых, сохранились те же внутренние числа a и b, во-вторых, видна избыточность, а в-третьих, запрета на создание такого состояния нет – оно не представляет собой трехкратное повторение одного и того же состояния первого кубита, избыточность встроена в него более тонким (если угодно, запутанным) образом.
Для этого, разумеется, нужны два дополнительных кубита – посторонних по отношению к тем, на которых в идеальной ситуации предлагается выполнять вычисление. Про них полезно знать, что их начальное состояние, скажем, «А». Применяя преобразования CNOT к основному кубиту и первому вспомогательному, а затем еще раз к основному и второму вспомогательному, мы из исходного «a А плюс b Б» создаем желаемое «избыточное» состояние «a (А, А, А) плюс b (Б, Б, Б)».
Контрольные измерения затем выполняются таким образом, чтобы отслеживать изменения в состоянии вспомогательных кубитов. Из этих измерений можно сделать заключение о характере случившейся ошибки или о ее отсутствии, и в первом случае определить преобразование (не измерение!), которое надо произвести над «основными» кубитами для ее исправления{83}.
Вопрос сегодняшнего дня – успеваем ли мы бежать впереди накапливающихся ошибок? Для коррекции неизбежных ошибок мы добавляем новые кубиты к тем, которые теоретически необходимы для вычисления, а также выполняем дополнительные преобразования. Они тоже работают не идеально, и требуются дополнительные кубиты для коррекции ошибок, возникающих при коррекции ошибок. Кто кого? Сколько физических кубитов потребуется, чтобы надежно выполнять квантовые вычисления на 1000 идеальных кубитов? Миллион?!
