Ваня и Маша (хотя на самом деле это, как всегда, были Боб и Элис) работают в крупной транснациональной корпорации и отвечают за администрирование корпоративной базы данных. А база не маленькая - бит этак на 10²⁰ или порядка 11 миллиардов гигабайтов. И к тому же офисы, в которых работают наши герои, находятся на разных концах земного шара. Копии базы данных в разных офисах должны быть идентичными базе данных главного офиса. И ничего не остается, как периодически посылать эти копии в главный офис для сличения с оригиналом. Задачка, прямо скажем, не из легких.

Призадумались наши Ваня и Маша. И посетила их гениальная мысль: а что если сколь угодно большому массиву данных сопоставлять индивидуальные идентификаторы, т.е. массивы данных значительно меньшей величины, как, например, каждому конкретному человеку можно поставить в соответствие совершенно уникальный рисунок папиллярных линий или, говоря по-простому, отпечатки пальцев. Так был придуман метод "классического снятия отпечатков" (classical fingerprinting). Выигрыш налицо: вместо регулярной посылки 10²⁰ бит информации достаточно было посылать только 10¹⁰ или немного больше гигабайта, чтобы с очень высокой вероятностью можно было различать массивы данных и сравнивать их между собой. Для этого независимо в каждом офисе генерировались различительные числа (distinctive numbers) или "отпечатки" (fingerprints). Они получались путем вычислений по особым алгоритмам, выполняемым по всей базе данных и сгенерированным случайным числам - ключам. Эти ключи представляли собой бинарный код коррекции ошибок. При условии, что допускается небольшая вероятность ошибки, длина "отпечатков" могла быть постоянной. Главное, чтобы эти случайные ключи были общими (shared keys) и надежно сохранялись во время обмена данными.

В 1996 году А. Амбайнис (A. Ambainis) доказал, что условие корреляции между ключами Вани и Маши необязательное, достаточно, чтобы они просто имели доступ к ключам друг друга. Тогда же И. Ньюмен (I. Newman) и М. Сэгеди (M. Szegedy) показали, что оптимально, если длина "отпечатков" будет изменяться пропорционально n^1/2, где n - размер массива данных в битах. Казалось, что эта оценка не может быть далее улучшена в сторону еще большего уменьшения длины "отпечатка".

Но совсем недавно Гарри Бурмэн (Harry Buhrman) из Научно-исследовательского института математики и компьютерных наук Амстердама, Рональд де Вольф (Ronald de Wolf) из Амстердамского университета, Ричард Клив (Richard Cleve) и Джон Уэтроуз (John Watrous) из Университета города Калгари (Канада) предложили совершенно иной способ генерирования "отпечатков" больших массивов данных. В статье, опубликованной в "Physical Review Letters" (Vol. 87, No. 16, Art. 167902, 4 pp., 15.10. 2001), они показали, что если генерировать "квантовые отпечатки", т. е. "отпечатки", содержащие квантовую информацию, то их длину можно сделать экспоненциально меньшей кодируемого массива данных. Корреляция (т.е. общие ключи) или "спутанность" (entanglement) между исходными массивами вообще не предполагается.

Предлагаемый метод заключается в том, что 2ⁿ "отпечатков" приводятся в квантовые состояния, так, чтобы попарные внутренние произведения описывающих эти состояния функций (пропорциональные вероятностям различных суперпонированных состояний) были меньше 1, и затем путем измерения (т.е. путем редукции системы к определенным состояниям) с очень высокой вероятностью произвести разбиение множества возможных "отпечатков" на одинаковые и различные. Авторы показали, что для достаточно надежного удаленного сравнения двух массивов данных достаточно, чтобы длина "отпечатков" была пропорциональна log₂(n) кюбитам (т.е. квантовым битам). А это значит, что Ване и Маше для того, чтобы и работу сделать вовремя, и выкроить еще часок, чтобы, например, "початиться", достаточно пересылать в главный офис "отпечатки" всего лишь примерно 70-кюбитной длины. Их роль могут выполнять особым образом подготовленные фотоны, передаваемые по оптоволоконным линиям связи.

Лидер проекта "снятия квантовых отпечатков" Гарри Бурмэн полагает, что использование 5-10-кюбитных квантовых компьютеров уже в ближайшее время будет более эффективным и выгодным, чем использование обычных компьютеров в модели "классического снятия отпечатков".

С полным текстом цитированной статьи можно ознакомиться по адресам: www.cpsc.ucalgary.ca/~cleve/pubs/fingerprint_prl.ps или www.cpsc.ucalgary.ca/~cleve/pubs/fingerprint_qph.ps (потребуется Adobe Acrobat Distiller).

Сергей САНЬКО