Какие реальные проблемы (кроме криптографии) могут быть эффективно решены квантовым алгоритмом?

Этот вопрос очень похож, так как есть общее утверждение о том, какие проблемы можно решить более эффективно с помощью квантового компьютера?

Но ответы на эти вопросы в основном смотрели на это с теоретической / математической точки зрения.

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

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

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

Под эффективными квантовыми алгоритмами я имею в виду, что в алгоритме должен быть хотя бы один шаг, который необходимо преобразовать в квантовую схему на квантовом компьютере с n-кубитом. Таким образом, в основном эта квантовая схема создает матрицу x и ее выполнение даст одну из возможностей с определенной вероятностью (поэтому разные прогоны могут давать разные результаты - где вероятный капот каждого из возможностей определяется построенной x эрмитовой матрицей.)$2^n$$2^n$$2^n$$2^n$$2^n$$2^n$

Поэтому я думаю, что для ответа на мой вопрос должен быть какой-то аспект / характеристика проблемы реального мира, которая может быть отображена в эрмитовой матрице. Итак, какие аспекты / характеристики реальной проблемы могут быть сопоставлены с такой матрицей?$2^n \times 2^n$

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

Я не буду давать точных утверждений о том, какие проблемы могут быть решены более эффективно с помощью квантовых алгоритмов (по сравнению с существующими классическими алгоритмами), а приведу несколько примеров :

• Дискретное преобразование Фурье (DFT) используется практически во всех современных музыкальных системах, например, в iPod. Этот алгоритм единолично изменил мир цифровой музыки. Смотрите это для краткого изложения. Тем не менее, квантовое преобразование Фурье может дополнительно улучшить сложность ДПФ, то есть от до . Я написал ответ по этому поводу здесь .O ( log 2 N $\mathcal{O}(N\log(N))$$\mathcal{O}(\log^2 N)$

• Квантовый алгоритм для линейных систем уравнений дает экспоненциальное ускорение над классическими методами , такими как исключения Гаусса.

Квантовый алгоритм для линейных систем уравнений, разработанный Aram Harrow, Avinatan Hassidim и Seth Lloyd, представляет собой квантовый алгоритм, разработанный в 2009 году для решения линейных систем. Алгоритм оценивает результат скалярного измерения на векторе решения заданной линейной системы уравнений.

Алгоритм является одним из основных фундаментальных алгоритмов, которые, как ожидается, обеспечат ускорение по сравнению с их классическими аналогами, наряду с алгоритмом факторизации Шора, алгоритмом поиска Гровера и квантовым моделированием. При условии, что линейная система является разреженной и имеет низкий номер условия , и что пользователь интересуется результатом скалярного измерения на векторе решения, а не значениями самого вектора решения, тогда алгоритм имеет время выполнения , где - количество переменных в линейной системе. Это обеспечивает экспоненциальное ускорение по сравнению с самым быстрым классическим алгоритмом, который выполняется в или O(log(N) κ 2 ) N O ( N κ ) O(N${\displaystyle \kappa }$$O(\log(N)\kappa ^{2})$${\displaystyle N}$${\displaystyle O(N\kappa )}$$O(N{\sqrt {\kappa }})$ для положительных полуопределенных матриц).

• Гамильтоново моделирование :

Одним из самых ранних и наиболее важных приложений квантового компьютера, вероятно, будет моделирование квантово-механических систем. Существуют квантовые системы, для которых не известно эффективное классическое моделирование, но которые мы можем моделировать на универсальном квантовом компьютере. Что значит «симулировать» физическую систему? Согласно OED, симуляция - это «метод имитации поведения некоторой ситуации или процесса (будь то экономический, военный, механический и т. Д.) Посредством соответствующей аналогичной ситуации или аппарата». То, что мы будем понимать под симуляцией, - это аппроксимация динамики физической системы. Вместо того, чтобы адаптировать наш симулятор для моделирования только одного типа физической системы (который иногда называют аналоговым моделированием),

За подробностями обращайтесь к главе 7 лекционных заметок Эшли Монтаро.

• Гибридные квантовые / классические алгоритмы :

Гибридные квантовые / классические алгоритмы объединяют подготовку и измерение квантовых состояний с классической оптимизацией. Эти алгоритмы обычно нацелены на определение собственного вектора основного состояния и собственного значения эрмитова оператора.

QAOA :

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

Вариационный квантовый Eigensolver

Алгоритм VQE применяет классическую оптимизацию для минимизации энергетического ожидания состояния анзаца, чтобы найти энергию основного состояния молекулы ^[2] . Это также можно расширить, чтобы найти возбужденные энергии молекул. ^[3] .

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

[1]: Квантовый приближенный алгоритм оптимизации Farhi et al. (2014)

[2]: вариационный решатель собственных значений на квантовом процессоре Peruzzo et al. (2013)

[3]: Вариационное квантовое вычисление возбужденных состояний Brierley et al. (2018)