Какой тип алгоритмов быстрее с квантовым компьютером?

Я начинающий студент CS и я алгоритмы обучения. Я слышал , что даже с квантовыми компьютерами, что общие алгоритмы сортировки никогда не могут быть лучше , чем время. Тем не менее, я также знаю , что алгоритмы факторинговых бы намного быстрее. В общих чертах, какие алгоритмы станут существенно быстрее с квантовыми компьютерами? $n\log n$

algorithms quantum-computing hgund
источник

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

Юваль Фильмус

Скотт Ааронсон (гуру квантовых вычислений) (две версии) говорил об этом предмете точно, под названием * Когда именно квантовые компьютеры обеспечивают ускорение? ". Вы можете найти его (или, скорее, их) здесь: scottaaronson.com/ переговоры .

Юваль Фильмус

Насколько я знаю, нет . Нам нужны новые алгоритмы. (см. первый комментарий Ювала.)

Рафаэль

на самом деле не доказано, что факторинг быстрее, только предположительно и т. д., это открытый вопрос P? = BQP и т. д.

vzn

Близко связаны: почему и как квантовый компьютер быстрее, чем обычный компьютер?

Жиль "ТАК - перестань быть злым"

Ответы:

$k$ $a^{k} = b$ $a$ $b$
Алгоритм Гровера дает квадратичное ускорение при поиске несортированных списков (что может использоваться как ускорение для многих алгоритмов).
Моделирование квантовых систем также в BQP, но экспоненциально медленнее на классической ТМ.
Решение уравнения Пелла (на самом деле не одно уравнение) заключается в BQP, другое экспоненциальное ускорение.
Есть также ряд других, более неясных, проблем, которые есть в BQP, но, по-видимому, отсутствуют в P. Wocjan, и Чжан дает хорошую отправную точку для их поиска .

Люк Мэтисон
источник