31.10 // АНБ оценит эффективность квантовых вычислений

Агентство национальной безопасности США и Исследовательское бюро американской армии объявили о начале исследовательской программы, призванной ответить на вопросы эффективности и перспективности квантовых вычислений. В частности, перед программой ставятся следующие цели:

• Разработать новые алгоритмы квантовых вычислений для решения трудных задач.
• Формализовать эффективность кандидатных алгоритмов.
• Оценить мощность квантовых вычислений и рассмотреть проблемы сложности и реализуемости квантового компьютинга.

Было заявлено, что конкретные исследовательские проекты должны сосредоточиться на разработке квантовых алгоритмов для математических и вычислительно трудных задач из столь различных областей, как алгебра, теория чисел, геометрия, анализ, оптимизация, теория графов, дифференциальные уравнения, комбинаторика, топология, логика и симуляция.

Представители армии отметили, что разрабатываемые квантовые алгоритмы должны быть нацелены на практическое решение конкретных задач, а также на общую методологию описания и анализа алгоритмов, предназначенных для решения конкретных проблем, однако не пояснили, о каких конкретных задачах и проблемах идёт речь.

Общая задача этой масштабной программы была сформулирована так:

С целью охарактеризовать эффективность кандидатных квантовых алгоритмов требуется разработка оценочных метрик производительности квантовых алгоритмов в сравнении с их классическими аналогами. Проблемы, к решению которых они применимы, должны иметь чётко определённые вводные данные, чётко определённые результирующие данные, а также чёткое описание производимых вычислений. Требуется доскональный учёт всех затрачиваемых вычислительных ресурсов, включая число кубитов, число квантовых вентилей, объём используемой памяти, объём классических пред- и поствычислений, вероятность успеха и количество требуемых проходов алгоритма.
Исследователи должны, исходя из предпосылки существования полностью функционального квантового компьютера, оценить, какие алгоритмические задачи являются наиболее подходящими для подобной машины. Обязательной частью исследования станет сравнение эффективности каждого квантового алгоритма с лучшими из существующих классических алгоритмов, предназначенных для решения той же задачи.

В марте 2009 года агентства планируют выделить на эту программу множество грантов по 200 тыс. долларов сроком от одного года до трёх лет.

Источник: http://www.networkworld.com/community/node/34597