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

Достижения в области квантовых вычислений привели к разработке новых классических алгоритмов. Известными недавними примерами являются квантово-вдохновенные алгоритмы для линейной алгебры:

• Квантово-вдохновленный классический алгоритм для систем рекомендаций
• Квантово-вдохновленные классические алгоритмы для анализа главных компонент и контролируемой кластеризации
• Квантово-вдохновленная стохастическая регрессия низкого ранга с логарифмической зависимостью от размерности
• Квантово-вдохновленные сублинейные классические алгоритмы для решения линейных систем низкого ранга

и для Макс 3LIN:

• Избиение случайного назначения в задачах удовлетворения ограничений ограниченной степени .

Может быть очень полезно составить список всех известных классических алгоритмов, основанных на квантовых вычислениях. Какие еще примеры известны?

Как утверждает Лесли Дж. Валиант в оригинальной статье 1 его,

Голографические алгоритмы основаны на квантовой вычислительной модели. Тем не менее, они исполняются на классических компьютерах и не нуждаются в квантовых компьютерах.

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

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

Существует целый ряд работ, связанных с квантовыми эволюционными алгоритмами (QIEA), с реальными алгоритмами, использующими методы квантовых вычислений, см. Опрос (источник ACM) . Другой квантово-вдохновленный алгоритм использует его в числовой оптимизации .

Алгоритм (ы) квантового квантового отжига Монте-Карло (QMC-QA ¹ ) или имитированного квантового отжига в дискретном времени (SQA ² ) показал лучшие результаты, чем протестированное устройство D-Wave в последних исследованиях :

Мы устанавливаем первый пример преимущества масштабирования для экспериментального квантового отжига по сравнению с классическим моделируемым отжигом: мы обнаруживаем, что устройство D-Wave демонстрирует значительно лучшее масштабирование, чем моделированный отжиг, с вероятностью 95%, в диапазоне размеров задач, которые мы можем проверить , Однако мы не находим доказательств квантового ускорения: смоделированный квантовый отжиг демонстрирует лучшее масштабирование со значительным запасом.

Поскольку и устройство D-Wave, и SQA превосходят SA в определенных проблемных случаях, создается впечатление, что SQA является своего рода квантовым алгоритмом. Более новое исследование, тестирующее процессор D-Wave 2000Q, также обнаруживает, что его производительность лучше согласуется с предложенной классической моделью, названной «алгоритм спин-вектора Монте-Карло (SVMC)» в этом исследовании, чем с SQA:

Мы используем это, чтобы доказать, что ключевой причиной замедления квантового отжигателя относительно SQA является его субоптимально высокая температура, которая заставляет его вести себя больше как SVMC. Таким образом, высокая производительность SQA в классе экземпляров с логической установкой позволяет предположить, что этот класс является хорошей целью или основой для исследования возможного квантового ускорения с использованием аппаратного обеспечения QA.

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

1. _{Мартонак, Р., Санторо, Дж. Э. и Тосатти, Е. Квантовый отжиг методом Монте-Карло с интегралом по траектории: двумерная модель Изинга. Phys. Rev. B 66 , 094203 (2002). URL http://link.aps.org/doi/10.1103/PhysRevB.66.094203}
2. _{Санторо Г.Е., Мартонак Р., Тосатти Э. и Кар Р. Теория квантового отжига изинговского спинового стекла. Science 295 , 2427–2430 (2002). URL http://dx.doi.org/10.1126/science.1068774 .}

Взгляните на квантовое линейное генетическое программирование. Этот алгоритм направлен на стимулирование компьютерных программ на императивных языках. Например:

• https://www.researchgate.net/project/Quantum-Inspired-Linear-Genetic-Programming

• Квантово-вдохновленное линейное генетическое программирование как система управления знаниями, август 2013 г., The Computer Journal 56 (9): 1043-1062, Дуглас Мота Диас и Марко Аурелио К. Пачеко https://doi.org/10.1093/comjnl/bxs108