Улучшают ли квантовые алгоритмы классические SAT?

Классические алгоритмы могут решать 3-SAT за времени (рандомизированный) или времени (детерминированный). (Ссылка: лучшие верхние границы по SAT )$1.3071^n$$1.3303^n$

Для сравнения, используя алгоритм Гровера на квантовом компьютере, можно было бы найти и найти решение в , рандомизированное. (Это может все еще потребовать некоторого знания о том, сколько решений может быть или не быть, я не уверен, насколько эти ограничения все еще необходимы.) Это явно значительно хуже. Существуют ли какие-либо квантовые алгоритмы, которые лучше, чем лучшие классические алгоритмы (или, по крайней мере, почти такие же хорошие)?$1.414^n$

Конечно, классические алгоритмы могут быть использованы на квантовом компьютере, предполагая достаточное рабочее пространство; Я задаюсь вопросом о изначально квантовых алгоритмах.

Я думаю, что можно получить нетривиальную верхнюю оценку из квантовых вычислений, ускоряя рандомизированные алгоритмы Шенинга для 3-SAT. Алгоритм Schöning работает во время и с использованием стандартных методов амплификации амплитуды можно получить квантовый алгоритм , который работает во время ( 2 / $(4/3)^n$что значительно быстрее, чем классический алгоритм.$(2/\sqrt{3})^n=1.15^n$

Действительно, как сказал wwjohnsmith1, вы можете получить ускорение квадратного корня по алгоритму Шенинга для 3-SAT, но также в более общем смысле для алгоритма Шенинга для k-SAT. Фактически, многие рандомизированные алгоритмы для k-SAT могут быть реализованы квадратично быстрее на квантовом компьютере.

$O(T(n) \mathrm{poly}(n))$$T(n)$$n$$1/T(n)$$O(T(n))$$O(T(n) \mathrm{poly}(n))$

$O(T(n))$$1/T$$O(\sqrt{T})$$O(\sqrt{T(n)}\mathrm{poly}(n))$