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