Лэнс Фотноу - Золотой билет

Вы спросите, как все это связано с гуляшом и с чудесными транспортерами из сериала «Звездный путь»? Давайте посмотрим, как можно организовать транспортер, выполняющий квантовую телепортацию. Допустим, я хочу телепортироваться из Чикаго в Токио и обращаюсь в специализированную компанию. Они создают запутанную квантовую систему из внушительного числа кубитов. Часть кубитов, соблюдая все возможные меры предосторожности, доставляют в Чикаго, остальные – в Токио. В Чикаго меня вместе с кубитами помещают в специальную камеру; описать мое состояние нужно очень точно, поэтому кубитов должно быть достаточно много. Нас вращают в многомерном пространстве, измеряют, и в результате мы все превращаемся в обычные нули и единички. Полученную кучу битов передают в токийский филиал, где с ними в такой же камере производят необходимые вращения. Потом камеру открывают, и я выхожу. Вот это да!

Использованные кубиты – отработанный материал. Если я решу вернуться, или нужно будет телепортировать кого-то еще, понадобится новая система запутанных кубитов. Кстати, с самолетами дело обстоит примерно так же: на обратном пути невозможно повторно воспользоваться израсходованным топливом.

Впрочем, это еще не самое страшное. Главная проблема – сохранить все зависимости между кубитами. Чтобы описать меня, требуется порядка миллиона миллиардов триллионов сцепленных кубитов: примерно столько атомов содержится в человеческом теле. И это еще довольно оптимистичная оценка, поскольку на деле кубитов, вероятно, понадобится намного больше. Ведь достаточно потерять каких-нибудь две-три связи (которые охотно разрушаются при малейшем взаимодействии с окружающей средой) – и из камеры вывалится порядком изуродованная, а то и вовсе неживая версия меня. Поэтому – только после вас. Я уж лучше по старинке, на самолете. Встретимся на месте!

Ряд ученых полагают, что теорию вычислений пора переводить на квантовый уровень. Пусть кванты и не позволят нам решать NP-полные задачи, однако с их помощью можно будет эмулировать физические системы, а это значительно приблизит нас к пониманию сущности материи, космоса и даже человеческого мозга. Мир увидит такие научные открытия, которые сейчас не в состоянии даже вообразить!

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

Что же может послужить очередным толчком в развитии вычислений? Какие еще грандиозные вычислительные задачи требуют нашего внимания? Читайте дальше – и вы все узнаете.

Я уже смирился с тем, что проблему равенства P и NP ожидает довольно унылая перспектива. Думаю, классы все же не равны – правда, в этой жизни доказательства я уже не увижу. И, думаю, нам не придется жить в совершенном мире из второй главы, хотя полностью исключать такую возможность, конечно, нельзя. Вероятно, пройдет не один десяток (а может, и не одна сотня) лет, прежде чем тайна P и NP будет раскрыта.

«P против NP» – не просто хитрая математическая головоломка. Даже будучи неразгаданной, она дает нам некий каркас для размышлений и подсказывает способы борьбы с важнейшими вычислительными задачами. Приведем наиболее актуальные на сегодняшний момент проблемы.

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

• Большие данные.Каждый день в мире появляются тонны новых данных. Взять хотя бы интернет или многочисленные научные эксперименты… Как работать с такими огромными объемами информации? Как искать, структурировать, анализировать, делать прогнозы?

• Интернет вещей.Почти каждый современный человек пользуется компьютерными сетями – к примеру, общаясь на Facebook или отправляя письмо по электронной почте. Дело идет к тому, что скоро все произведенные человеком предметы, будь то одежда или лампочки для чтения, тоже станут частью сети. Как ориентироваться в мире с таким количеством связей?

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

В 1965 году Гордон Мур заметил, что число базовых элементов микросхемы – транзисторов – стремительно возрастает с каждым годом. Мур выдвинул смелое предположение: в последующее десятилетие количество транзисторов на одном кристалле каждые два года будет увеличиваться вдвое. Десятью годами дело в результате не ограничилось; закон Мура – так окрестили правило – действует и по сей день, и в ближайшие годы тенденция, похоже, сохранится.

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

И все же транзисторов на кристалле становится все больше и больше. Зачем это нужно? Чтобы запускать сразу несколько вычислений одновременно: распараллеливая работу, мы значительно уменьшаем время решения задач.

Возьмем для примера суперкомпьютер IBM по имени Уотсон, который в феврале 2011 победил в американской телевикторине «Jeopardy!». Уотсон состоит из 90 серверов IBM Power 750 по 4 процессора Power 7 в каждом. Один процессор Power 7 содержит восемь более мелких процессоров, или ядер, и может параллельно вести сразу восемь вычислений. В итоге получается 32 ядра в одном сервере и 2880 во всем компьютере, так что Уотсон может запускать 2880 процессов одновременно. Неудивительно, что он анализирует варианты ответа быстрее, чем соперники, и успевает нажать кнопку миллисекундой раньше! Впрочем, если производительность компьютеров продолжит расти по закону Мура, то уже через несколько лет 2880 параллельных процессов покажутся нам сущим пустяком; в ближайшие десятилетия могут появиться компьютеры с миллионами и даже миллиардами ядер.