Записки программиста

Теперь, когда мы рассмотрели многие интересные квантовые алгоритмы (для тех, кто пропустил, прошу внимательно и последовательно ознакомиться с ранними заметками: один, два, три и далее по ссылкам), мы можем перейти к обзору всего того хозяйства, которое имеется в области квантовых вычислений на текущий момент. Если кто-то считает, что алгоритмом факторизации Шора всё и ограничивается, то это далеко не так.

Есть такой дяденька — Стивен Джордан, и он замечателен тем, что ведёт в этих ваших интернетах информационную страницу под названием «Квантовый зоопарк». Если перейти на неё прямо сейчас, то будет видно, что по состоянию на август 2014 года там представлено 52 описания алгоритмов и решаемых ими задач. При этом, конечно же. большинство описаний касаются довольно глубоких и фундаментальных проблем, чуть более чем полностью наполненных тяжёлыми матанами. Но это совсем не значит, что у них нет применимости. Все базовые алгоритмы оперируют довольно абстрактными вещами, и только потом прикладные программисты переводят абстрактные алгоритмы в прикладную плоскость. Так будет постепенно происходить и здесь.

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

Сводное описание квантовых алгоритмов

Все описанные на текущий момент квантовые алгоритмы подразделяются на три большие группы:

1. Алгебраические и теоретико-числовые алгоритмы;
2. Алгоритмы со специальным оракулом;
3. Алгоритмы квантовой симуляции.

Рассмотрим подробно каждую из этих групп.

Алгебраические и теоретико-числовые алгоритмы

Собственно, всё началось с этой темы, поскольку изначально искались задачи, в которых квантовые алгоритмы давали бы видимое преимущество перед лучшими классическими алгоритмами. И именно в этом множестве и находится наиболее из известных квантовых алгоритмов — алгоритм факторизации Шора. Ну и, чтобы быть честным, Питер Шор разработал два алгоритма, названных его именем, только про алгоритм вычисления дискретного логарифма всё больше умалчивают, а он тоже решает прикладную задачу, которую как бы сложно решить и на которой основаны некоторые криптографические системы (в частности, протокол обмена ключами Диффи-Хеллмана).

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

Всего в группе на текущий момент описано 11 алгоритмов.

Алгоритмы со специальным оракулом

Далее в истории развития модели квантовых вычислений настала плодотворная пора, когда было определено, что данная модель является не хуже классической, так что она в полиномиальном режиме может решать и классические задачи. Были разработаны многочисленные алгоритмы, основанные на так называемых «оракулах», то есть квантовых чёрных ящиках, которые представляют собой отображение классической функции. К сожалению, многие описания алгоритмов не рассматривают вопросы построения квантовых оракулов, а потому часто сложно сказать, насколько на самом деле эффективнее квантовый алгоритм. Но в целом считается, что оракул можно построить с полиномиальной сложностью, а потому этот процесс можно не принимать во внимание.

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

Всего в группе на текущий момент описан 31 алгоритм.

Алгоритмы квантовой симуляции

Наконец, алгоритмы квантовой симуляции основаны на аналоговой похожести процесса эволюции волновой функции каким-либо другим процессам. Эта похожесть и используется для проведения вычислений. Не все алгоритмы в этом разделе вполне эффективны, а для адиабатического процесса квантовой релаксации вообще неизвестна степень повышения эффективности. Да и вообще последний процесс является спорным, и построенный на его основе «квантовый компьютер» D-Wave универсальным квантовым компьютером не является, поскольку решает только одну частную задачу.

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

Всего в группе на текущий момент описано 10 алгоритмов.

Диаграмма отношений квантовых алгоритмов

Надо отметить, что в описании всех квантовых алгоритмов часто попадаются отсылки на другие (смежные) алгоритмы, базовые математические конфепции или решаемые прикладные задачи. Это позволило объединить все алгоритмы в единую семантическую сеть, или если можно так назвать — «карту отношений» квантовых алгоритмов друг с другом. Вот, что получилось в итоге (кликабельно, SVG, ~900 Кб):

Как может заметить внимательный читатель, здесь далеко не 52 прямоугольника, а несколько больше. Это произошло потому, что на диаграмму вынесены некоторые неописанные алгоритмы, а также большое количество решаемых в рамках модели квантовых вычислений прикладных задач (например, компрометация системы криптографии RSA или протокола секретного обмена ключами Диффи-Хеллмана).

Если сложно понять то, что написано в легенде этой схемы, то вот словесное её описание. На представленной диаграмме прямоугольником обозначается квантовый алгоритм или задача, которая может быть решена в рамках модели квантовых вычислений. Жирная граница использована для тех алгоритмов, которые были ранее описаны в цикле статей.

Для каждого алгоритма и задачи приводятся две характеристики — ускорение и типы задач, решаемых алгоритмом (или тип самой задачи). Ускорение алгоритма может быть:

• Константное (с).
• Полиномиальное (p).
• Сверхполиномиальное (sp).
• Экспоненциальное (e).
• Неизвестное (?) — для адиабатических квантовых алгоритмов.

Все алгоритмы и задачи классифицированы по следующим типам задач (при этом у алгоритма вполне может быть несколько типов):

• Теория чисел.
• Теория множеств.
• Теория групп.
• Алгоритмы на графах.
• Алгоритмы на матрицах.
• Алгоритмы поиска.
• Алгоритмы оптимизации.
• Алгоритмы о свойствах функций.
• Криптографические алгоритмы и задачи.
• Алгоритмы квантовой симуляции.

Наконец, между алгоритмами и (или) задачами рассматриваются четыре типа отношений, а именно:

• Если из алгоритма A идёт обычная стрелка в алгоритм B, то это значит, что алгоритм B основан на алгоритме A.
• Если же стрелка пунктирная, то алгоритм B сводится к алгоритму A, то есть это в большей мере отношение подобия.
• Волнистая стрелка обозначает, что алгоритм A решает прикладную задачу B.
• Наконец, двойная линия между прямоугольниками без стрелок обозначает, что два алгоритма сходны между собой.

Как видно, на сегодняшний день квантовая модель вычислений уже является довольно развитой областью знаний. Более того, в научные исследования по данному вопросу вовлечены многие лучшие умы в области как физики, так и информатики (компьютерных наук). Количество публикаций растёт день ото дня. Ищутся новые алгоритмы и способы их применения к решению прикладных задач.

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

Заключение

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

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

Дополнение: Квантовая криптография простыми словами

Метки: Алгоритмы.