Умножение квантовой матрицы?

30

Не похоже, что это известно - но есть ли интересные нижние оценки сложности умножения матриц в модели квантовых вычислений? Есть ли у нас какая-то интуиция, что мы можем победить сложность алгоритма Копперсмита-Винограда, используя квантовые компьютеры?

Генри Юн
источник

Ответы:

26

В arXiv: quant-ph / 0409035v2 Берман и Спалек представляют квантовый алгоритм, опережающий алгоритм Копперсмита-Винограда в случаях, когда выходная матрица имеет несколько ненулевых элементов.

Обновление: есть также немного улучшенный квантовый алгоритм Дёрна и Тьерауфа .

Обновление: есть улучшенный квантовый алгоритм Ле Галла, опередивший Бурхмана и Спалека в целом.

Мартин Шварц
источник
1
Это было новым для меня (я мало знаю о квантовых результатах), но, взглянув на бумагу, результат оказался еще более удивительным! Если для матричных умножений есть o ( AnxmBmxn=Cnxnненулевые записи в выходных данных, произведение может быть вычислено засубквадратичноевремя,o(nm). o(n)o(nm)
Даниэль Апон
10
Там очень небольшое улучшение , чтобы это для специального случая булевой матрицы продукта, мин { } , когда есть ш nonzeroes в выходном сигнале. (Он появился в нашей статье FOCS'10 «Субкубические эквивалентности между задачами пути, матрицы и треугольника».)n1.3w17/30,n2+w47/60n13/15w
virgi
3
Недавнее усовершенствование к в случае булевой матрицы продукта arxiv.org/abs/1112.5855 , с также соответствующими нижними границами. nw1/2
Абель Молина
14

Если вы заинтересованы в умножении двух матриц и получении полного классического результата, ответ Мартина, вероятно, является окончательным ответом на ваш вопрос. Однако, если вы хотите вычислить что-то вроде вы можете сделать это чрезвычайно эффективно. У Харроу, Хасидима и Ллойда есть алгоритм ( arXiv: 0811.3171 ) для вычисления v X - 1 v, который является логарифмическим только в измерениях матрицы X для разреженных матриц. Кажется, довольно просто адаптировать этот подход для расчета продуктов, а не наоборот.vXYvvX1vX

Джо Фитцсимонс
источник
3
В этом случае время выполнения будет по-прежнему зависеть от номера условия матриц, и матрицы должны иметь сложные записи. Кроме того, если X и Y невелики, то то же самое можно сказать и их произведении, и v ' X Y v можно оценить классически с таким же экспоненциальным ускорением, используя случайную выборку. vXYv
Арам Харроу
@ Арам: Хорошая мысль! Я знаю, что ваш алгоритм работает для разреженных матриц, но у меня сложилось впечатление, что он может работать и для некоторых не разреженных матриц. Это верно?
Джо Фицсимонс
Да, это работает для не разреженных матриц, когда мы знаем хорошие способы моделирования этих гамильтонианов. Так что, возможно, здесь возможно что-то нетривиальное.
Арам Харроу
1
@Aram: С использованием кодировки, которую вы используете, разве мы не получаем преобразование Фурье всех разреженных матриц через QFT?
Джо Фицсимонс
@Joe: я только что заметил это. Да, эти матрицы (которые вы можете считать разреженными в основе импульса) также можно использовать. В этом нет ничего уникального для нашего алгоритма. Скорее, это утверждение о классе гамильтонианов, которые мы знаем, как моделировать на квантовом компьютере.
Арам Харроу