понедельник, 25 февраля 2013 г.

Что такое квантовый компьютер

Одна из концепций, объяснение которой простыми русскими словами встречается примерно нигде - квантовые компьютеры. Попробуем разобраться.

Шум вокруг них довольно большой, СМИ активно перепечатывают новости в стиле "при помощи особой магии группа исследователей добилась чего-то непонятного". Ещё понятно, что квантовые компьютеры как-то связаны с криптографией, и что это явно очень круто, высокотехнологично и будущее. К сожалению, попытки вникнуть в тему чуть глубже быстро приводят к текстам, усыпанным формулами в бракет нотации, терминами вроде "гильбертово пространство" и прочими вещами, мало проясняющими суть дела.

Во-первых, квантовый компьютер - это пока что именно "концепция", а не "устройство" или "штуковина". Работающих квантовых компьютеров не просто нет (что бы там кто ни говорил). Их настолько нет, что даже непонятно, как именно они должны быть устроены, и какие в точности операции позволять. Если сравнивать их с обычными, квантовые вычисления сейчас находятся в лучшем случае примерно на уровне середины ХIX века: Чарльз Бэббидж сконструировал сколько-то механических арифмометров и мечтает построить более мощный и универсальный, а Ада Лавлейс на бумажечке пишет для этого несуществующего универсального арифмометра программы. Какие там интегральные микросхемы, транзистора ещё полвека ждать. Подходящей физической реализации базовых логических элементов нет, одно ясно: шестеренки на эту роль не очень годятся - громоздко, ненадежно и дорого.

То же и с квантовыми компьютерами: как именно будут реализованы кубиты ("универсальные элементы"), пока непонятно, а от этого много что зависит, вплоть до того, какие алгоритмы на них можно будет реализовать, а какие - нет (в отличие от классических машин Тьюринга, не все возможные квантовые компьютеры "по сути одинаковы"). Исследователи (те самые, из статей, перепечатываемых журналистами) занимаются тем, что пробуют различные физические процессы и конструкции на эту роль; пока получается так себе, лучшие достижения современности - что-то типа восьми кажется-работающих (но очень быстро ломающихся) кубитов (представьте себе арифмометр из восьми шестерёнок). Могу соврать, не следил некоторое время, но порядки величин, во всяком случае, такие.

Тогда к чему столько шума, и откуда уверенность в том, что несуществующие в природе, но точно адски дорогие и сложные, к тому же неизвестно что умеющие устройства окажутся в чём-то принципиально лучше существующих компьютеров?

Тут нам придётся в лучших традициях серьезной научной литературы обратиться к сравнению с фильмом "Матрица" (как жаль, что к нему с 1999 года так и не сняли ни одного продолжения). Представим себе ученого, живущего в мире Матрицы, и работающего на Правительство, точнее даже, на Спецслужбы, в том числе общающегося и с опасными людьми (а может, и не совсем людьми) в дорогих костюмах и чёрных очках. К тому же наш Учёный знает физику достаточно для того, чтобы заподозрить, что местами реальность обсчитывается не совсем честно. В общем, главный секрет той вселенной для него вовсе не секрет. К сожалению, толку ему от этого знания немного: "сбежать" изнутри (для этого действия есть более точный термин jailbreak, популяризированный айфонами) все равно не получится. И, хотя он понимает, что на фоне реальных процессов, происходящих во вселенной, всё, чем занимаются правительства - пустая и бессмысленная возня, жить как-то надо, а иллюзорные деньги и иллюзорные женщины ему нравятся всё же больше, чем иллюзорная пуля в затылке. Представили, да? Фантастики тут немного: Учёный не очень отличается от многих реальных физиков ХХ века.

И вот Правительство даёт ему задание, для которого Учёному нужно произвести очень много вычислений (например, коды подпольщиков взламывать, или ядерные взрывы обсчитывать). Тут у него появляется идея: зачем заниматься ерундой и использовать "иллюзорные" компьютеры, если ему точно известно, что на свете совершенно точно существует неизмеримо более мощный суперкомпьютер, на порядки превосходящий все остальные, вместе взятые (хотя бы просто потому, что он же их работу и эмулирует). Давайте получим у людей в костюмах доступ к терминалу, позволяющему запускать свои программы непосредственно на нём! (Или, если такого терминала в этом мире пока не существует, разрешение его построить).

Как вы понимаете, криптография тут просто предлог. Да, конечно, если он научится взламывать коды этих террористов практически мгновенно, ему выпишут премию, и всё такое, но дело не в этом. Сама возможность поработать с реальностью на каком-то новом, гораздо более базовом и реальном, уровне, узнать, как устроен код мира на самом деле, захватывает дух (если у вас нет, это нормально, просто вы, значит, не учёный).

Вернёмся на секундочку в наш мир.

Квантовый компьютер - это аналог такого терминала в нашем мире.

Стоп-стоп, но мы-то живём не в симуляторе. Какие у нас основания считать, что наблюдаемая реальность не очень реальна, и что под ней находится какой-то более глубокий уровень, к тому же дающий доступ к невероятной вычислительной мощи? За поясняющей аналогией придется снова отправиться в мир Матрицы (я же говорил, "на секундочку").

Какие вычислительные мощности нужны Матрице, чтобы эмулировать небольшой город, в котором живёт сто тысяч человек? Не очень понятно, в каких петабайтах их измерить, но ясно только, что очень большие. Давайте обозначим их Х. А мегаполис, в котором живёт десять миллионов человек? Ответ 100*Х не совсем правильный: людей не только стало в сто раз больше, но и каждый из них ещё и видит больше, взаимодействует с большим количеством соседей, и т.п.

Мы можем сказать, что в вычислительном смысле мир Матрицы (как и миры большинства многопользовательских компьютерных игр - MMORPG) имеет размерность чуть больше единицы: если одна его подсистема требует для обсчёта ресурсы Х, то подсистема, "объём" которой больше в N раз, потребует для своего обсчёта чуть больше, чем X*N.

Наш мир, каким его представляли в конце ХIХ века (то есть управляемый классической ньютоновской механикой), в этом смысле имеет размерность 2: вычислительные ресурсы, которые понадобились бы нам для эмуляции классической ньютоновской системы, состоящей из N частиц, пропорциональны числу N2 (каждая частица взаимодействует с каждой на любом расстоянии, так что всего придется учесть примерно N в квадрате пар).

А где-то в середине ХХ века физики неожиданно осознали, что из квантовой механики следует очень странный факт: на самом деле, размерность нашего мира в вычислительном смысле бесконечно велика. Для эмуляции системы, состоящей из N частиц, может потребоваться количество ресурсов, пропорциональное 2N, что при большом N (а элементарных частиц в нашем мире очень-очень много) больше, чем N в любой степени.

Это очень-очень странно: получается, что все наблюдаемые нами на макроскопическом уровне процессы очень простые, а на микроуровне они чудовищно сложны. Рассчитать (то есть иметь возможность повторить) в Матрице всё, что мы видим на макроуровне, гораздо проще, чем рассчитать поведение какого-нибудь одного-единственного атома, хотя мы и знаем в точности, как именно ведут себя отдельные составляющие его электроны, протоны и нейтроны. Вселенная с "обсчётом" всего этого безобразия чудесно справляется, но если бы я был Богом, и если бы люди были целью Моего творения, то, кажется, я нашел бы более экономичный способ.

Ну хорошо, а нельзя ли как-нибудь воспользоваться вычислительной мощью Вселенной, которая, оказывается, на микроуровне бесконечно велика?

Классический компьютер, построенный из N транзисторов, имеет вычислительную мощь порядка N. Квантовый компьютер, построенный из N кубитов (которые, напомню, пока не очень известно, как физически должны выглядеть), будет иметь вычислительную мощь порядка 2N (правда, при этом будет уметь посчитать на них далеко не всё, что умеет классический). Это - конечная цель.

Совсем вкратце о последствиях создания квантовых компьютеров, если мы их дождёмся: - некоторые распространенные схемы шифрования окажутся автоматически взломаны (нам есть, чем их заменить, но если это произойдёт очень быстро, на некоторое время в компьютерной безопасности образуется хаос) - ????

Я серьёзно. Больше применений нет. Для тех, кто разбирается в теме чуть больше, чем никак: применение алгоритма Гровера на практике крайне сомнительно, корректная работа оптимизации на адиабатических квантовых компьютерах не гарантирована (т.к. NP-полные задачи они всё равно не решают), и что там ещё остаётся, кроме совсем уж эльфийской математики? Ну только алгоритм Шора, кажется, и остаётся. Боюсь, когда грантодатели получше осознают эту неприятную истину, шансы на успешное создание квантовых компьютеров резко упадут; к тому же многие авторитетные учёные (М.И.Дьяконов, например) считают, что оно невозможно или запретительно сложно в чисто инженерном смысле, примерно как реактор термоядерного синтеза или обычный компьютер, способный проработать на Венере больше нескольких часов.

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

P.S. inb4 D-Wave: не рассказывайте мне (и остальным) о них в комментариях, пожалуйста, если не знаете ОЧЕНЬ хорошо, о чём говорите; после того, как я написал эмулятор финальной версии (не существовавшей тогда в природе иначе как в виде спецификаций) их чипа C4 Chimera (стоящего $10M), работающий на моём ноутбуке, моя вера в них близка к нулю.


Оригинал взят у plakhov в Что такое квантовый компьютер

via +Давид Мзареулян.

Комментариев нет:

Отправить комментарий