Квантовые ужасы

Tony

Спецвыпуск Xakep, номер #038, стр. 038-094-1

(tony@nifti.unn.ru, ICQ 165066287, http://itfi.nnov.ru)

Все, что ты боялся узнать о квантовых компьютерах

Основное и, в принципе, единственное назначение компьютера – производить вычисления. Бывают задачи, которые решаются на классических компьютерах крайне эффективно, но также есть задачи, сложность решения которых растет экспоненциально с ростом сложности самой задачи.

Эта статья о том, как можно решить, казалось бы, нерешаемые задачи. Будущее уже не за горами, и с приходом в нашу жизнь квантовых компьютеров, например, рухнут многие известные криптоалгоритмы, и на их место придет… ну, а об этом ниже :).

Мир классический, мир компьютерный

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

Идея нахожусь…

Однозначно сказать, кому все-таки принадлежит идея квантового компьютера, нельзя, разные люди в разных точках планеты примерно в одно и то же время начали выдавать идеи квантовых вычислений. О них говорил еще фон Нейман, в 60-х годах Ландауэр писал о том, что вычисления это физический процесс, а значит, у каждой реализации вычислений будет своя точность. Юрий Манин в 1980 году высказал идею о создании квантового компьютера. В 1982 году Ричард Фейнман привел выкладки, доказывающие, что квантовые компьютеры могут существовать, и квантовые вычисления гораздо мощнее классических. Дэвид Дойч из Оксфорда в 1985 году дал определение квантовому алгоритму и доказал, что для некоторых задач он значительно ускоряет расчеты. Наконец в 1994 году Питер Шор из Bell Labs придумал квантовый алгоритм факторизации числа. И потом началось… Однако прежде чем городить огород из технических и научных терминов, сразу тебя отрезвлю – квантового компьютера не существует и существовать не будет до тех пор, пока этого не позволят технологии, интересы и желания власть и денег имущих. Что же существует? Существует квантовая механика, существует теория квантовых вычислений, существует пара устройств, а вернее прототипов устройств, не являющихся, конечно, квантовыми компьютерами, но представляющих собой, так сказать, сопутствующие товары. Но обо всем по порядку.