«Необратимые» квантовые вычисления удалось впервые осуществить австрийским ученым. Антон Цайлингер (Anton Zeilinger) и его сотрудники из венского Института экспериментальной физики использовали для этого так называемые «запутанные состояния» фотонов. Результаты эксперимента, опубликованные в журнале Nature, неизбежно повлияют на современные представления о практической разрешимости ряда важных проблем теории чисел и криптографии.

Квантовые компьютеры основаны на качественно иной логике, чем современные классические. Принципы действия последних описываются булевой алгеброй, и любому состоянию вычислительной машины отвечает некоторая последовательность битов. Единицей квантовой информации является q-бит — состояние двухуровневой квантовой системы. В вычислениях существенно используются квантовые явления — суперпозиция и «запутывание» (entanglement) состояний, так что N q-битам отвечает 2N-мерное пространство, базисные векторы которого — последовательности «q-нулей» и «q-единиц».

Если «измерить» состояние квантовой системы «до» и «после», мы получим результат вычисления, которое в математической модели описывает соответствующий физический процесс. Это соображение встречается в работах Фейнмана, а в 1980 году советский алгебраист Манин сформулировал на его основе концепцию квантовых вычислений. Постановка вопроса была непривычной для математиков: требовалось «приспособить» задачу к некоторой системе, могущей ее решить.

Задач, для которых уже придуманы квантовые алгоритмы, сравнительно немного. Среди них, однако — проблема разложения на простые множители, исключительно важная для теории чисел и криптоанализа. Многие алгоритмы шифрования, криптостойкость которых с точки зрения классических вычислений не вызывает сомнений, взламываются посредством квантового компьютера.

Попытки воплотить q-бит в конкретных физических системах предпринимались с 1980-х годов. Квантовые компьютеры на основе сверхпроводимости или ядерного магнитного резонанса так и не удалось построить.

www.lenta.ru