Искусство мыслить рационально. Шорткаты в математике и в жизни - [109]
Таким образом, было бы полезно создать целую последовательность таких кубитов. Например, если удастся объединить 64 кубита в состоянии квантовой суперпозиции, такой массив сможет одновременно представлять все числа от 0 до 2>64 – 1. Обычному компьютеру пришлось бы последовательно перебирать все эти числа, присваивая каждому биту значения, равные 0 или 1. Но квантовый компьютер может сделать это одновременно. В результате мой обычный компьютер, как электрон, как бы существует в нескольких параллельных вселенных сразу. В каждой из них эти 64 кубита представляют разные числа.
Тут-то и начинается самое интересное. В каждом из параллельных миров такой компьютер проверяет, является ли то число, которое он представляет, делителем кодового числа. Но как сделать так, чтобы квантовый компьютер сумел выбрать именно тот мир, в котором кодовое число успешно делится на число проверяемое? Именно этот вопрос решает блестящий прием Шора, который он встроил в свой алгоритм. Как только мы производим наблюдение квантовой суперпозиции, она должна принять решение и окончательно перейти в одно или другое состояние. По сути дела, она выбирает положение 0 или положение 1. Переход в то или иное положение определяется вероятностью.
Шор сумел создать такой алгоритм, который обеспечивает, что после проверки на делимость в каждой из параллельных вселенных квантовая суперпозиция с подавляющей вероятностью переходит в состояние того мира, в котором проверенное число оказалось делителем кодового числа. Все остальные миры, в которых результат проверки оказался отрицательным, настолько похожи друг на друга, что они взаимно уничтожаются. Остается только тот мир, в котором деление прошло успешно.
Представьте себе двенадцать векторов, исходящих из центра циферблата часов и направленных на его числа. Если все они равной длины, то при сложении взаимно уничтожатся, и останется лишь точка в центре циферблата. Но что произойдет, если один из них будет вдвое длиннее остальных? При сложении получится вектор, указывающий в этом направлении. По существу, то же самое происходит и при квантовом наблюдении проверок на делимость.
Хотя Шор написал свою программу еще в 1994 году, создание реального квантового компьютера, на котором этот алгоритм смог бы работать, казалось несбыточной мечтой. Одна из проблем квантовых состояний – это так называемая декогеренция. 64 кубита начинают наблюдать друг друга, и суперпозиция исчезает еще до выполнения вычислений. Это одна из причин, по которым, возможно, не существует кот Шредингера – квантовый мысленный эксперимент, в котором кот, пока его не наблюдают, может быть одновременно живым и мертвым. Разумеется, электрон может находиться в состоянии суперпозиции, но как все атомы, составляющие кота, могут одновременно быть в состояниях, в которых кот мертв и жив? Среди большого количества атомов начнутся взаимодействия, и декогеренция приведет к коллапсу суперпозиции.
Однако в последние годы в области изоляции одновременных квантовых состояний были достигнуты поразительные успехи. В октябре 2019 года журнал Nature опубликовал статью исследователей из компании Google под названием «Обеспечение квантового превосходства при помощи программируемого сверхпроводящего процессора»[131]. Как сообщается в этой статье, ее авторам удалось использовать 53 кубита в состоянии суперпозиции, одновременно представляющие числа приблизительно до 10>16. Их компьютер смог выполнить чрезвычайно специализированную задачу, на которую у обычного компьютера ушло бы 10 000 лет работы.
Хотя это очень радостная новость, задача, которая была поручена этому квантовому компьютеру, была не того же уровня, что поиск простых делителей больших чисел. Она была довольно сильно приспособлена именно под то оборудование, на котором она выполнялась. Многим показалось, что Google немного перебарщивает с шумихой вокруг «квантового превосходства». Группа, занимающаяся разработкой квантовых компьютеров в компании IBM, отозвалась об этой публикации весьма пренебрежительно и даже показала, что та задача, которой занимались исследователи из Google, может быть выполнена на обычном компьютере не за 10 000 лет, а за несколько дней. Несмотря на все это, достигнутый результат был поразительным. Тем не менее создание квантового компьютера, способного взламывать кредитные карты, по-видимому, все еще остается делом достаточно отдаленного будущего.
Биологические компьютеры
А как насчет задачи коммивояжера? Можно ли найти шорткат к ней при помощи нетрадиционных средств? Одну из задач, родственных задаче коммивояжера, исследователям удалось решить, применив компьютер очень необычного типа. В этой задаче – так называемой задаче о гамильтоновом пути – нужно проложить маршрут по сети дорог с односторонним движением, соединяющих нанесенные на карту города́.
Рис. 10.4. Задача о гамильтоновом пути: как попасть из города А в город E, посетив все остальные города только по одному разу?
Требуется найти маршрут, начинающийся из одного города, скажем А, и заканчивающийся в другом городе – Е, – нопроходящий через все остальные города по одному, и только одному, разу. Возможен ли такой маршрут? Оказывается, найти его так же трудно, как решить задачу коммивояжера. Но и эта задача прекрасно подходит для применения параллельной обработки информации. Однако математик Леонард Адлеман не стал обращаться к квантовому миру, а придумал интересный биологический подход к ее решению. К слову, именно фамилию Адлемана обозначает буква А в аббревиатуре RSA, названии шифровальной системы, использующей простые числа для обеспечения безопасности сетевых транзакций.
