В квантовых вычислениях квантовый алгоритм - это алгоритм, который работает на реалистичной модели квантовых вычислений, наиболее часто используемой моделью является модель вычислений с квантовой схемой. Классический (или неквантовый) алгоритм — это конечная последовательность инструкций или пошаговая процедура решения задачи, где каждый шаг или инструкция может выполняться на классическом компьютере. Точно так же квантовый алгоритм представляет собой пошаговую процедуру, каждый из шагов которой можно выполнить на квантовом компьютере. Хотя все классические алгоритмы также могут выполняться на квантовом компьютере : термин квантовый алгоритм обычно используется для тех алгоритмов, которые кажутся квантовыми по своей сути или используют некоторые существенные особенности квантовых вычислений, такие как квантовая суперпозиция или квантовая запутанность. Проблемы, которые неразрешимы с помощью классических компьютеров, остаются неразрешимыми с использованием квантовых компьютеров. Эффективно моделировать на классических компьютерах. Наиболее известными алгоритмами являются алгоритм Шора для факторинга и алгоритм Гровера для поиска в неструктурированной базе данных или в неупорядоченном списке. Алгоритмы Шора работают намного (почти экспоненциально) быстрее, чем самый известный классический алгоритм разложения на множители — решето общего числового поля.Алгоритм Гровера работает квадратично быстрее, чем лучший из возможных классических алгоритмов для той же задачи, линейного поиска.
==============================
Квантовые алгоритмы обычно описываются в широко используемой схемной модели квантовых вычислений квантовой схемой, которая воздействует на некоторые входные кубиты и завершается измерением. Квантовая схема состоит из простых квантовых вентилей (quantum circuit s) , которые воздействуют не более чем на фиксированное число кубитов. Количество кубитов должно быть фиксированным, потому что изменение количества кубитов подразумевает неунитарную эволюцию. Квантовые алгоритмы также могут быть сформулированы в других моделях квантовых вычислений, таких как модель гамильтонова оракула.
Квантовые алгоритмы можно классифицировать по основным методам, используемым в алгоритме. Некоторые часто используемые методы/идеи в квантовых алгоритмах включают возврат фазы, оценку фазы, квантовое преобразование Фурье, квантовые блуждания, усиление амплитуды и топологическую квантовую теорию поля. Квантовые алгоритмы также могут быть сгруппированы по типу решаемых задач, например, см. Обзор квантовых алгоритмов для алгебраических задач.
==============================
В теории сложности и теории вычислимости машина-оракул — это абстрактная машина, используемая для изучения проблем принятия решений.
Его можно представить как машину Тьюринга с черным ящиком, называемым оракулом, который способен решать определенные задачи за одну операцию. Задача может быть любого класса сложности. Можно использовать даже неразрешимые проблемы, такие как проблема остановки.
==============================
Алгоритмы на основе квантового преобразования Фурье
==============================
Квантовое преобразование Фурье является квантовым аналогом дискретного преобразования Фурье и используется в нескольких квантовых алгоритмах. Преобразование Адамара также является примером квантового преобразования Фурье над n-мерным векторным пространством над полем F2. Квантовое преобразование Фурье можно эффективно реализовать на квантовом компьютере, используя только полиномиальное число квантовых вентилей.
- Алгоритм Дойча-Йожы решает проблему черного ящика, которая, вероятно, требует экспоненциально большого количества запросов к черному ящику для любого детерминированного классического компьютера, но может быть выполнена ровно одним запросом квантовым компьютером. Если мы допускаем как квантовые, так и классические алгоритмы с ограниченной ошибкой, то ускорения не происходит, поскольку классический вероятностный алгоритм может решить задачу с постоянным числом запросов с малой вероятностью ошибки. Алгоритм определяет, является ли функция f постоянной (0 на всех входах или 1 на всех входах) или сбалансированной (возвращает 1 для половины входной области и 0 для другой половины).
2.Алгоритм Саймона
Алгоритм Саймона решает проблему черного ящика экспоненциально быстрее, чем любой классический алгоритм, включая вероятностные алгоритмы с ограниченной ошибкой. Этот алгоритм, обеспечивающий экспоненциальное ускорение по сравнению со всеми классическими алгоритмами, которые мы считаем эффективными, послужил мотивацией для алгоритма факторинга Шора.
==============================
3.Алгоритм квантовой оценки фазы
Алгоритм оценки квантовой фазы используется для определения собственной фазы собственного вектора унитарного вентиля с учетом квантового состояния, пропорционального собственному вектору, и доступа к вентилю. Алгоритм часто используется как подпрограмма в других алгоритмах.
===============================
4.Алгоритм Шора
Алгоритм Шора решает задачу дискретного логарифмирования и задачу факторизации целых чисел за полиномиальное время,тогда как самые известные классические алгоритмы требуют сверхполиномиального времени. Эти задачи не являются P- или NP-полными. Кроме того, это один из немногих квантовых алгоритмов, который решает задачу, отличную от черного ящика, за полиномиальное время, в то время как самые известные классические алгоритмы работают за суперполиномиальное время.
===============================
5.Проблема со скрытой подгруппой
Проблема абелевой скрытой подгруппы является обобщением многих проблем, которые могут быть решены квантовым компьютером, таких как проблема Саймона, решение уравнения Пелла, проверка главного идеала кольца R и факторизация. Известны эффективные квантовые алгоритмы для абелевой проблемы скрытых подгрупп. Более общая проблема скрытых подгрупп, где группа не обязательно абелева, является обобщением ранее упомянутых проблем, изоморфизма графов и некоторых проблем с решетками. Для некоторых неабелевых групп известны эффективные квантовые алгоритмы. Однако для симметрической группы не известны эффективные алгоритмы, которые давали бы эффективный алгоритм для изоморфизма графов , и для группы диэдра, который решал бы некоторые проблемы с решеткой.
===============================
6.Оценка сумм Гаусса
Сумма Гаусса — это тип экспоненциальной суммы. Самый известный классический алгоритм для оценки этих сумм требует экспоненциального времени. Поскольку проблема дискретного логарифмирования сводится к оценке суммы Гаусса, эффективный классический алгоритм оценки сумм Гаусса подразумевал бы эффективный классический алгоритм вычисления дискретных логарифмов, что считается маловероятным. Однако квантовые компьютеры могут оценивать суммы Гаусса с полиномиальной точностью за полиномиальное время.
=================================
7.Ловля Фурье и проверка Фурье
У нас есть оракул, состоящий из n случайных логических функций, отображающих n-битные строки в логическое значение. Требуется найти n n-битных строк z1,...,zn таких, что для преобразования Адамара-Фурье хотя бы 3/4 строк удовлетворяют
Это можно сделать за квантово-полиномиальное время с ограниченной ошибкой (BQP).
Это должна быть экспоненциально сложная задача с одним ответом. То есть количество вариантов ответа растёт с ростом размера входных данных, и из этих вариантов верен только один. Пока по моим данным известны только три задачи... Читать далее
Деньги дают под криптографию, логистику. Т.е. там где бинарная логика (двоичная система) неудобна. Наверно неплохо задачки кластерного анализа решать.
У меня встречный вопрос. Как этот вопрос попал ко мне? Я ищу логику Кью.