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

Квантовый алгоритм сверхбыстрого поиска был предложен Л.Гровером еще в 1996 г. и теперь носит имя первооткрывателя. Этот алгоритм позволяет быстро найти определенную информацию в неупорядоченных базах данных, например, фамилию по телефонному номеру в телефонной книге, записи в которой не упорядочены в алфавитном порядке. Для этого алгоритм сделает всего SQRT(n) шагов, где n - число записей в базе данных, вместо того, чтобы "шарить" по всем n записям как при обычном поиске.

В сравнительно простых случаях алгоритм Гровера действительно удается реализовать экспериментально. Последний удачный эксперимент такого рода был недавно осуществлен группой исследователей из Мичиганского университета. Квантовый компьютер, который был использован в эксперименте, состоял всего из 2 "захваченных" ионов кадмия, состояния которых были "запутаны".

В этом случае уже после первого шага поиска квантовый компьютер находил нужную запись в базе из четырех записей с 60-процентной точностью, тогда как для обычного компьютера эта величина не могла бы превысить 50-процентный рубеж. Ученые утверждают, что предложенная ими схема легко масштабируема для решения весьма сложных задач поиска, поскольку добавление всего одного иона в систему удваивает число регистров памяти.

Статья была опубликована в ноябрьском номере журнала "Physical Review" (Vol. A 72, Art. 050306, 2005). Полный текст доступен на: monroelab2.physics.lsa.umich.edu/publications/ archive/PRA_72_050306_brickman_grover.pdf. Подробнее про алгоритм Гровера можно почитать в книге: Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. М.: МЦНМО, 1999. 192 с. (ftp.mccme.ru/users/vyalyi/qcomp/qbook.ps.gz).

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