Обеспечивают ли квантовые вычисления какое-либо ускорение в оценке трансцендентных функций?

9

Известно, что с проблемой целочисленной факторизации алгоритм Шора обеспечивает существенное (экспоненциальное?) Ускорение по сравнению с классическими алгоритмами. Существуют ли похожие результаты в отношении более элементарной математики, такой как оценка трансцендентных функций?

Допустим, я хочу рассчитать sin⁡2, ln⁡5 или cosh⁡10, В классическом мире я мог бы использовать расширение, такое как ряд Тейлора, или какой-то итерационный алгоритм. Существуют ли квантовые алгоритмы, которые могут быть быстрее, чем классический компьютер, будь он асимптотически лучше, меньше итераций с той же точностью или быстрее по времени настенных часов?

algorithm speedup Norrius
источник
Уже есть классические алгоритмы, которые могут оценивать их с разумной (например, 80-битной) точностью за несколько тактов (и они фактически реализованы на процессорах); кажется маловероятным, что КК может выполнять значительно быстрее, чем это. Вы спрашиваете о чрезвычайно высокой точности (например, 1 миллион бит)?
Пончо
@poncho Имеет смысл, что такие базовые вещи были оптимизированы почти до совершенства, но мне интересно, есть ли в этих функциях что-то, что можно было бы использовать еще быстрее в контроле качества. Даже если эффект можно увидеть только при высоких требованиях к точности.
Норриус
4
@poncho «маловероятно, что контроль качества может выполняться значительно быстрее». Люди думали, что вряд ли будут улучшения алгоритма наивного умножения, но теперь у нас есть Карацуба. Вы можете спросить, хотим ли мы лучшего алгоритма (да, например, для точности, как вы сказали), но на самом деле не так уж и странно ожидать некоторого улучшения.
Дискретная ящерица

Ответы:

6

Единственное, о чем я могу думать, это алгоритм нахождения степеней матрицы, который имеет суперполиномиальное ускорение. Это из этого списка квантовых алгоритмов (хотя, кажется, немного устарел).

Владимир
источник
Хотя это не дает прямого ответа на вопрос, это очень интересно, спасибо!
Норриус
@Norrius Хорошо, я сосредоточил свое внимание на Are there similar results regarding more basic maths. К сожалению, я не мог найти ничего более связанного.
Владимир