Искусство мыслить рационально. Шорткаты в математике и в жизни - Маркус дю Сотой

деления большого кодового числа, состоит в том, что им приходится проводить одну проверку, прежде чем они могут перейти к следующей. (Уточню для ясности, что в последующих рассуждениях я имею в виду только точное деление, без остатка.) Хорошо бы было разделить компьютер на части так, чтобы все они одновременно проводили разные проверки. Параллельная обработка – очень действенный способ ускорения работы. Взять, к примеру, строительство дома. В состязании на скорость строительства дома, проводившемся в Лос-Анджелесе, победила бригада из 200 строителей, работавших параллельно: они закончили свой дом за четыре часа. Разумеется, некоторые задачи необходимо выполнять последовательно. При строительстве многоэтажного дома или подземного гаража следующий этаж можно добавить, только когда будет построен предыдущий. Но перебор меньших чисел с проверкой того, делится ли на них большее, прекрасно можно производить параллельно. Каждая из таких проверок никак не зависит от результатов всех остальных.

Недостаток параллельной обработки данных состоит в том, что и она ограничивается физическими возможностями. Если разбить задачу на две, время, которое занимают проверки, уменьшится в два раза, но зато увеличится вдвое количество необходимой аппаратуры. По сути дела, такой подход не помогает находить простые делители большого числа.

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

Таким образом, было бы полезно создать целую последовательность таких кубитов. Например, если удастся объединить 64 кубита в состоянии квантовой суперпозиции, такой массив сможет одновременно представлять все числа от 0 до 264 – 1. Обычному компьютеру пришлось бы последовательно перебирать все эти числа, присваивая каждому биту значения, равные 0 или 1. Но квантовый компьютер может сделать это одновременно. В результате мой обычный компьютер, как электрон, как бы существует в нескольких параллельных вселенных сразу. В каждой из них эти 64 кубита представляют разные числа.

Тут-то и начинается самое интересное. В каждом из параллельных миров такой компьютер проверяет, является ли то число, которое он представляет, делителем кодового числа. Но как сделать так, чтобы квантовый компьютер сумел выбрать именно тот мир, в котором кодовое число успешно делится на число проверяемое? Именно этот вопрос решает блестящий прием Шора, который он встроил в свой алгоритм. Как только мы производим наблюдение квантовой суперпозиции, она должна принять решение и окончательно перейти в одно или другое состояние. По сути дела, она выбирает положение 0 или положение 1. Переход в то или иное положение определяется вероятностью.

Шор сумел создать такой алгоритм, который обеспечивает, что после проверки на делимость в каждой из параллельных вселенных квантовая суперпозиция с подавляющей вероятностью переходит в состояние того мира, в котором проверенное число оказалось делителем кодового числа. Все остальные миры, в которых результат проверки оказался отрицательным, настолько похожи друг на друга, что они взаимно уничтожаются. Остается только тот мир, в котором деление прошло успешно.

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

Хотя Шор написал свою программу еще в 1994 году, создание реального квантового компьютера, на котором этот алгоритм смог бы работать, казалось несбыточной мечтой. Одна из проблем квантовых состояний – это так называемая декогеренция. 64 кубита начинают наблюдать друг друга, и суперпозиция исчезает еще до выполнения вычислений. Это одна из причин, по которым, возможно, не существует кот Шредингера – квантовый мысленный эксперимент, в котором кот, пока его не наблюдают, может быть одновременно живым и мертвым. Разумеется, электрон может находиться в состоянии суперпозиции, но как все атомы, составляющие кота, могут одновременно быть в состояниях, в которых кот мертв и жив? Среди большого количества атомов начнутся взаимодействия, и декогеренция приведет к коллапсу суперпозиции.

Однако в последние годы в области изоляции одновременных квантовых состояний были достигнуты поразительные успехи. В октябре 2019 года журнал Nature опубликовал статью исследователей из компании Google под названием «Обеспечение квантового превосходства при помощи программируемого сверхпроводящего процессора»[131]. Как сообщается в этой статье, ее авторам удалось использовать 53 кубита в состоянии суперпозиции, одновременно представляющие числа приблизительно до 1016. Их компьютер смог выполнить чрезвычайно специализированную задачу, на которую у обычного компьютера ушло бы 10 000 лет работы.

Хотя это очень радостная новость, задача, которая была поручена этому квантовому компьютеру, была не того же уровня, что поиск простых делителей больших чисел. Она была довольно сильно приспособлена именно под то оборудование, на котором она выполнялась. Многим показалось, что Google немного перебарщивает с шумихой вокруг «квантового превосходства». Группа, занимающаяся разработкой квантовых компьютеров в компании IBM, отозвалась об этой публикации весьма пренебрежительно и даже показала, что та задача, которой занимались исследователи из Google, может быть выполнена на обычном компьютере не за 10 000 лет, а за несколько дней. Несмотря на все это, достигнутый результат был поразительным. Тем не менее создание квантового компьютера, способного взламывать кредитные карты, по-видимому, все еще остается делом достаточно отдаленного будущего.

Биологические компьютеры

А как насчет задачи коммивояжера? Можно ли найти шорткат к ней при помощи нетрадиционных средств?