Квантовые компьютеры: немного истории

Признаюсь честно — я не интересовался глубоко темой квантовых компьютеров. Поэтому когда по сети прошла новость о том, что создается операционная система для этих компьютеров, то особо не впечатлился. Но более просвещенные друзья сказали, что все не так просто и подобные заявления — это весьма и весьма серьезные вещи. По моей просьбе Виталий, (комментирующий здесь под ником Wch), написал обзорную статью, в которой рассказывается, что такое квантовые компьютеры. Далее идет его текст.

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

Немного истории

С точки зрения математика, история квантовых компьютеров началась несколько раньше истории обычных.

1903 год. Бертран Рассел и Альберт Уайтхед пишут Principia Mathematica, фундаментальный труд, перевернувший представления о роли и возможностях математики. Эта книга послужила основой для работ Тьюринга по созданию первых компьютеров. Но Рассел был не только математиком, но и философом. В этом своем качестве он часто задавал неожиданные вопросы. История квантовых компьютеров начинается с одного из них, внешне очень простого.

Итак, у нас есть последовательность вида: 1+ ½ +1/6+ … и так далее, проще говоря, сумма 1/n!.

Из школы мы знаем, что эта последовательность сходится, и ее сумма – это число e. И даже не зная про это число, если мы построим график этой последовательности – интуитивно мы легко поймем, что у нее есть предел, и он где-то между 2 и 3. Но если мы попытаемся посчитать это число «в лоб», например, просто складывая члены последовательности на калькуляторе, мы не закончим никогда, так как она бесконечна. А это был единственный способ, доступный тогдашним, еще не программируемым, вычислительным машинам. Значит ли это, что мы нашли существенное качество, отличающее человека от машины? Такой вопрос задал Рассел.

Чтобы ответить на него, он ввел понятие оракула. Машина может получить эту сумму за конечное время при одном условии: каждый следующий шаг вычислений будет короче предыдущего. То есть, если мы посчитали первое число за время t, следующее и сумму мы должны считать за t/3 и так далее. Гипотетический вычислитель, обладающий таким свойством, Рассел и назвал оракулом. Квантовые компьютеры являются именно такими оракулами. Но что это нам дает? Снова обратимся к истории.

Комбинаторика и взрыв

1997 год. Чемпион мира Гарри Каспаров проигрывает суперкомпьютеру Deep Blue. В одну из конференций программистов в сети кто-то отправляет короткое сообщение: «Наши победили». Но так ли это на самом деле? Для этого надо понять, как работал Deep Blue.

Это достаточно просто. Представьте себе шахматную доску в начале партии. Вы начинаете. У вас есть возможность сделать первый ход несколькими способами; в ответ противник может сделать свой ход, тоже набором способов. Чтобы оценить, насколько будет удачным ваш ход, вы можете воспользоваться логикой и интуицией шахматиста, но можете сделать и проще: просчитать все возможные комбинации ходов, перебрав все варианты. Именно так работал Deep Blue. Конечно, не все так просто: он использовал эвристики для отсечения заведомо плохих вариантов, но в основе лежал все равно перебор.

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

Вопрос к оракулу

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

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

  1. Криптография. Это то, что упоминается чаще всего, и про что иногда даже пишутся неказистые технотриллеры вроде «Цифровой крепости» Д. Брауна. Действительно, кажется, в этом противостоянии математических щита и меча появление вычислителей такого рода означает победу над любым традиционным шифром. Но на самом деле все с точностью наоборот, так как квантовому взлому противостоит квантовая криптография, уже достаточно проработанная в теории, и зашифрованные с ее помощью сообщения невзламываемы от слова совсем. Как вывод – мы получаем средство для абсолютно защищенных коммуникаций.
  2. Любые алгоритмы сжатия несут в себе все тот же принцип перебора. Современные протоколы интернета часто используют сжатие пакетов при передаче, но это всегда компромисс между размером пакета и временем на распаковку. То есть, даже не говоря о сложных вещах типа квантовой телепортации, мы получим большой рывок в скорости коммуникаций.
  3. AI. Практически все современные системы искусственного интеллекта являются дальними родственниками Deep Blue, то есть несут в себе такой же алгоритм перебора вариантов. Понятно, что «разумность» машин резко возрастет. Отдельная задача тут – это распознавание образов; сейчас ее часто решают с помощью нейросетей, генетических алгоритмов и прочих элементов машинного обучения, которое представляет собой, опять-таки, перебор вариантов.
  4. Алгоритмы анализа данных, data mining и т.п. Выделяю в отдельный пункт, так как это не совсем AI. Минимум половина этих алгоритмов – это оптимизация перебора. То есть мы получим, например, по-настоящему интеллектуальный поиск в сети, очень хорошую оптимизацию интернета вещей и еще довольно много применений.
  5. Программистам. А вот здесь у меня не очень хорошие новости. В данный момент прототипы квантовых компьютеров используют специальный диалект академического языка Haskell, который справедливо считается одним из самых зубодробительных, так как там мало кодинга и много математики. Разумеется, отчасти это вопрос оптимизирующих компиляторов и трансляторов, но новые алгоритмы придется освоить. По-видимому, возникнет новая планка знаний для профессии.

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

Оракул и мистик

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

И все же, в понимании некоторых технологий есть две части – сухая инженерная и представление о чуде, которым они являются. Я хочу сказать о второй части – о чуде, и нам придется опять обратиться к истории.

В 1703 году двое величайших ученых Европы, Исаак Ньютон и Готфрид Вильгельм Лейбниц, начинают свой знаменитый спор о приоритете в исчислении бесконечно малых. Истинная подоплека спора, однако, скрыта. Это не спор ученых, это спор мистиков. Каббалиста и алхимика Ньютона с пантеистом Лейбницем, а предметом спора является предопределение и свобода разума. Ньютон стоит на позиции предопределения, Лейбниц – свободы.

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

Это представление сломала квантовая физика. Микромир оказался по-настоящему непредсказуем, и, видимо, в том споре был прав Лейбниц. Но все-таки, как это работает на самом деле? Ответа пока нет, но есть предположения.

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

В 1989 году знаменитый физик Роджер Пенроуз пишет книгу “Новый ум короля”. Этой книгой он навлек на себя практически проклятье всех классиков AI; даже в учебниках Пенроуза упоминают сквозь зубы, так как прямо назвать его фриком несколько неудобно. Гипотеза Пенроуза состоит в том, что мозг человека обладает свойствами квантового вычислителя.

В 2014 году исследования показывают, что процесс фотосинтеза включает в себя некоторые квантовые эффекты, использование которых обусловлено эволюцией.

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

Возможно, квантовые компьютеры помогут дать ответ.

Comments

comments

Add a Comment

Ваш e-mail не будет опубликован. Обязательные поля помечены *