Быстрое классическое моделирование квантовых алгоритмов

10

Существуют ли примеры случаев, когда классическое моделирование квантового алгоритма для задачи превосходит лучший ранее известный классический алгоритм для этой задачи? «Превосходит» не обязательно означает другой класс сложности, это может быть просто лучшее масштабирование.

Этот вопрос был вдохновлен случаем эффективного классического моделирования алгоритма квантовой рекомендации .

cc.complexity-theory quantum-computing quantum-information delete000
источник
1
Ваш вопрос, как указано, на самом деле не имеет смысла. Классическое моделирование квантового алгоритма - это особый вид классического алгоритма, поэтому он не может быть быстрее, чем лучший классический алгоритм. Это может быть самый быстрый известный классический алгоритм, но он не может быть лучше, так как это сделает его лучше, чем он сам.
Крейг Гидни
Я полагаю, вы имели в виду «Превосходит лучший из известных ранее классических алгоритмов»
Фредерик Гроссханс,
Когда я прочитал вопрос, я подумал об этом предостережении, но ожидал, что будет очевидно, что одним из двух классических алгоритмов будет «ранее известная» не имитация квантового алгоритма. Теперь я знаю лучше.
delete000

Ответы:

6

Ваш вопрос был вдохновлен недавним классическим прогрессом в алгоритме рекомендаций. Обратите внимание, что это не первый раз, когда такое случается. В 2015 году аналогичные разработки произошли с приближенным MAX3LIN : квантовый алгоритм, превосходящий все предыдущие известные классические алгоритмы, мотивировал успешный поиск лучшего классического алгоритма. Однако, насколько мне известно, в обоих этих случаях классические алгоритмы не похожи на классическое моделирование квантовой эволюции.

Мне известна одна статья, описывающая классическое моделирование квантовой системы, позволяющее превзойти ранее известные алгоритмы (полное раскрытие: авторы - мои друзья) :

Квантово-вдохновенный алгоритм оценки перманента положительных полуопределенных матриц, Л. Чахмахчян, Н. Дж. Серф, Р. Гарсия-Патрон, arXiv: 1609.02416 / Phys. Rev. A 96 , 022329

Это основано на связи между постоянной и квантовой оптикой, показанной с помощью бозонной выборки . В отличие от обычного подхода, они смотрят на состояния, которые, как известно, легко моделировать (тепловые состояния), и используют это моделирование для выполнения вычисления Монте-Карло перманента эрмитовых положительных полуопределенных матриц. Для некоторых классов матриц этот алгоритм дает лучшее приближение, чем лучший ранее известный алгоритм (алгоритм Гурвица).

Фредерик Гроссханс
источник