Среди изобретений, которые должны изменить мир в XXI веке, на одном из первых мест до сих пор числилось «гипотетическое вычислительное устройство» под названием «квантовый компьютер». «И вот наступило будущее»: канадская компания D-Wave продемонстрировала первый в мире процессор, использующий принцип квантовых вычислений.
Устройство получило название Orion, и оно уже сейчас способно выполнять 64 000 операций параллельно. Как это обычно случается, «будущее» наступило «не вовремя» – по мнению многих экспертов, примерно на 30 лет раньше, чем ожидалось. Теперь осталось довести квантовые вычислительные устройства до практического применения.
Проще говоря: теперь появилась возможность создания машины, которая сможет выполнять за считанные часы такие вычисления, на которые у нынешних компьютеров уйдут столетия.
Принцип квантового процессора
Для начала несколько слов о том, как работает квантовый процессор. В начале 80-х прошлого века нобелевский лауреат, известный в России как автор «Фейнмановских лекций по физике», Ричард П. Фейнман из Калифорнийского технологического института увлек научную общественность идеей точного моделирования явлений квантовой физики на компьютере принципиально нового типа – квантовом.
Действительно, моделировать состояние микрочастиц, которое описывается многомерной волновой функцией с числом переменных, равным числу частиц в системе, да еще и зависящей от времени, даже на современнейшем и мощнейшем компьютере, по-видимому, довольно проблематично. Поэтому, как считал Фейнман, было бы естественно моделировать физическую реальность, которая подчиняется квантовым законам, с помощью «компьютера, построенного из квантовомеханических элементов, подчиняющихся квантовомеханическим законам».
Основная идея квантового вычисления состоит в том, чтобы хранить данные в ядрах атомов, изменяя их ориентацию в пространстве. Элементарная ячейка такого компьютера получила название квантовый бит (quantum bit = кубит). В отличие от привычной нам единицы информации – бита (binary digits = bits), который может принимать только два значения или «0» или «1», квантовый бит в соответствии с принципом неопределенности, постулируемым квантовой механикой, может находиться одновременно в состоянии и «0», и «1».
Таким образом, если классическое вычислительное устройство, состоящее из L вычислительных ячеек способно выполнять одновременно L операций, то для квантового устройства размером L кубит количество выполняемых параллельно операций будет равно 2 в степени L.
Возвращение к истокам
Таким образом, квантовый компьютер на первый взгляд является как бы «возвращением к истокам»: это разновидность аналоговой вычислительной машины, такой как, например, механический арифмометр или шифровальная машинка типа знаменитой «Энигмы», изобретенной в Третьем рейхе.
Но это не так: по своей сути это цифровое устройство, но с аналоговой природой. Хорошо, принцип квантовых вычислений известен лет 20–30 – а как с реализацией? Американские ученые из исследовательского центра IBM (IBM's Almaden Research Center) создали действующую модель квантового компьютера с использованием алгоритма Питера Шора лишь в конце 2001 года.
Этот алгоритм всего лишь позволяет разложить натуральное число n на простые множители, привязав процесс к функции времени, и относится к классу быстрых алгоритмов полиноменального типа. Фактически все, что смог этот прототип, – это догадаться, что 5x3=15.
Компьютер, созданный группой ученых из IBM и Станфордского университета, представлял собой пробирку с миллионами молекул, имеющих семь ядерных спинов (положений). Он мог быть «запрограммирован» при помощи электромагнитных импульсов разной частоты, а для получения результатов работы устройства использовался специальный сканер.
В полной мере квантовые компьютеры проявляют свои достоинства при выполнении факторизации чисел – задачи, лежащей в основе современной криптографии. Чем больше факторизуемое число, тем дольше обычный компьютер будет искать его делители. Каждый следующий разряд удваивает время вычислений.
Для квантового компьютера увеличение числа не создаёт таких проблем, поскольку дополнительные разряды замедляют его работу на фиксированное время. Вот и пришла пора вспомнить о легендарной «Энигме».
Квантовая «Энигма»
Если вы полагаете, что Windows – та программа, на которую в мире продано наибольшее количество лицензий, – наведите ревизию в ящике, где вы храните свои диски с программами. Самую распространенную операционную систему опережает скромный продукт фирмы RSA Data Security, Inc. – программа, реализующая алгоритм шифрования с открытым ключом RSA, названный так в честь его авторов – американских математиков Ривеста, Шамира и Адельмана.
Дело в том, что алгоритм RSA встроен в большинство продаваемых операционных систем, а также во множество других приложений, используемых в различных устройствах – от смарткарт до сотовых телефонов. Вообще, трудно найти известную фирму, работающую в области высоких технологий, которая не купила бы лицензию на эту программу.
На сегодняшний день фирма RSA Data Security, Inc. продала уже более 450 миллионов(!) лицензий. Почему же алгоритм RSA оказался так важен? Для решения проблемы безопасного обмена конфиденциальными сообщениями в 1970-х годах были предложены системы шифрования, использующие два вида ключей для одного и того же сообщения: открытый (не требующий хранения в тайне) и закрытый (строго секретный). Открытый ключ служит для шифрования сообщения, а закрытый – для его дешифровки.
Вы посылаете вашему корреспонденту открытый ключ, и он шифрует с его помощью свое послание. Все, что может сделать злоумышленник, перехвативший открытый ключ, – это зашифровать им свое письмо и направить его кому-нибудь. Но расшифровать переписку он не сумеет. Вы же, зная закрытый ключ (он изначально хранится у вас), легко прочтете адресованное вам сообщение. Для зашифровки ответных посланий вы будете пользоваться открытым ключом, присланным вашим корреспондентом (а соответствующий закрытый ключ он оставляет себе). Как раз такая криптографическая схема и применяется в алгоритме RSA – самом распространенном методе шифрования с открытым ключом.
Расчеты показывают, что с использованием даже тысячи современных рабочих станций и лучшего из известных на сегодня вычислительных алгоритмов одно 250-значное число может быть разложено на множители примерно за 800 тысяч лет, а 1000-значное – за 10 в 25-й степени (!) лет. (Для сравнения возраст Вселенной равен ~10 в10-й лет.) Между тем, согласно оценкам, квантовый компьютер с памятью объемом всего лишь около 10 тысяч квантовых битов способен разложить 1000-значное число на простые множители в течение всего нескольких часов!
Применение идей квантовой механики уже открыло новую эпоху в области криптографии, так как методы квантовой криптографии открывают новые возможности в области передачи сообщений, которые даже теоретически нельзя «расшифровать». Работы над коммерческими системами такого рода уже идут полным ходом.
Лиха беда начало!
Если вычислительный регистр прототипа IBM имел всего семь ядерных спинов, то регистр процессора Orion имеет их уже 16. А это уже кое-что! На восьми- или шестнадцатиразрядных Spectrum и Amiga или им подобных многие из нас начинали свое знакомство с компьютерами. А 8-разрядные процессоры типа Z80 до недавних пор исправно приводили к цели выпущенные за пару тысяч километров «Томагавки» с точностью в 20–30 метров.
Возможности квантового 16-кубитного процессора гораздо серьезней. Он позволяет выйти на такие информационные технологии, на фоне которых создание интегральной микросхемы или Интернета покажется лишь эпизодом.
Однако перед этим предстоит решить ряд серьезных проблем: выбрать способ реализации кубитов (из чего их делать – проще говоря), определить физический механизм взаимодействия между кубитами и найти способ селективного управления кубитами и измерения их квантового состояния на выходе системы.
D-Wave Systems cмогла решить эти проблемы, хотя из материалов пресс-релиза и другой информации на сайте компании можно уяснить лишь выбор способа реализации кубитов, для которого использовались сверхпроводящие материалы на основе ниобия.
О процессоре известно лишь то, что это новый тип аналогового процессора с масштабируемой архитектурой и что он основан на квантовомеханических принципах. Компания, правда, обещает в скором времени представить на своем сайте самую подробную информацию о своем квантовом компьютере.
Сделано это будет, видимо, после того, как выйдет в свет направленная в авторитетный научный журнал статья. Нынешняя презентация, судя по всему, понадобилась компании для утверждения собственного приоритета в области квантовых вычислений.
Квантовый компьютер успешно справился с тремя предложенными ему задачами – поиском молекулярной структуры, соответствующей конкретной молекуле-мишени, составлением сложного плана размещения гостей за столом и решением головоломки Судоку. Скромненько, скажете? Попробуйте решить эти задачи за приемлемое время на обычной машине.
D-Wave Systems заявила, что квантовый компьютер не будет конкурентом нынешним, скорее, он предназначен для решения задач с огромным количеством исходной информации и большим числом переменных. Такие задачи характерны для систем криптографии и безопасной передачи данных, биологии и медицины, моделирования квантовых систем, оптимизации различных процессов. Так что лиха беда начало!
Взято из: http://www.vz.ru/society/2007/2/16/68719.html
За ссылку на статью благодарим Хакер