Квантовый алгоритм

Привет, Вы узнаете о том , что такое квантовый алгоритм , Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое квантовый алгоритм , настоятельно рекомендую прочитать все из категории Квантовая информатика.

квантовый алгоритм  — это алгоритм, предназначенный для выполнения на квантовом компьютере.

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

Результат работы квантового алгоритма носит вероятностный характер^[1]. За счет небольшого увеличения количества операций в алгоритме можно сколь угодно приблизить вероятность получения правильного результата к единице.

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

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

Ускорение на квантовом компьютере не связано с тактовой частотой процессора. Об этом говорит сайт https://intellect.icu . Оно основано на квантовом параллелизме. Один шаг квантового вычисления совершает гораздо большую работу, чем один шаг классического. Однако было бы ошибкой приравнивать квантовое вычисление к распараллеленному классическому. Например, квантовый компьютер не может решить задачу перебора быстрее, чем за  где  — время работы детерминированного классического алгоритма перебора (см.^[3]), в то время как недетерминированный классический алгоритм решает ее за время . Но недетерминированный классический алгоритм требует экспоненциального ресурса памяти, то есть не является физически осуществимым, тогда как квантовый алгоритм не противоречит известным законам природы.

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

Случаи квантового ускорения, на фоне общей массы классических алгоритмов, очень редки (см.^[4]). Однако, это не умаляет принципиального значения квантовых вычислений, потому что они способны принципиально ускорить выполнение задач переборного типа.

Основные схемы квантового ускорения 

Главный тип задач, которые ускоряются квантовыми алгоритмами, являются задачи типа перебора. Их можно разделить на 2 основные группы:

1. Задачи моделирования динамики сложных систем (первоначальная идея Фейнмана) и
2. Математические задачи, сводящиеся к перебору вариантов:
   1. Общий случай перебора: схема Гровера и ее варианты, а также
   2. Задачи поиска скрытых периодов: схема Шора использования быстрого квантового преобразования Фурье, и ее аналоги.

Тип 1) представлен алгоритмом Залки — Визнера  моделирования унитарной динамики квантовых систем   частиц за почти реальное время и с линейной от  памятью. Этот алгоритм использует схему Шора квантового преобразования Фурье .

Тип 2) представлен:

• алгоритмом Гровера общей задачи перебора и его непрерывным и адиабатическим вариантами, а также алгоритмами, использующими схему Гровера: структурного поиска (Фари, Гутман), алгоритмом поиска экстремума (Хойер и др.) и поиска совпадающих строк в базе данных (Амбайнис),
• алгоритмом Шора факторизации целых чисел, алгоритмом Абрамса — Ллойда выявления периода, алгоритмом Китаева определения скрытых подгрупп и др.

Тип 1) представляет наибольший интерес с точки зрения дальнейших приложений квантового компьютера.

Классификация 

Классификация квантовых алгоритмов может проводится по типу квантовых преобразований, используемых алгоритмом. Среди часто используемых преобразований можно отметить: en:phase kick-back, phase estimation, en:quantum Fourier transform, en:quantum walk, en:amplitude amplification,en:topological quantum field theory. Также возможна группировка квантовых алгоритмов по типу проблем, решаемых ими.^[5]

Широко известные алгоритмы  

• Алгоритм Шора
• Алгоритм Гровера
• Алгоритм Дойча — Йожи

Вау!! 😲 Ты еще не читал? Это зря! 

• Квантовый компьютер
• Квантовое программирование
• Список алгоритмов
• Класс BQP

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