Что является доказательством того, что квантовые компьютеры могут эффективно моделировать произвольные квантово-механические системы?

JBV предложил мне превратить некоторые комментарии в вопрос, так что здесь.

Другой вопрос [1] касается применения QM-вычислений. Одним из ответов [2] было «эффективное моделирование квантовой механики». Очевидно, эта идея восходит к ранним работам Фейнмана на эту тему; хотя у меня нет ссылки. Так:

Вопрос. Что является доказательством того, что квантовый компьютер может эффективно моделировать произвольную квантово-механическую систему?

На одном уровне это кажется основным. Однако это не кажется тривиальным по следующей причине: большая часть литературы по квантовым вычислениям, по-видимому, сводится к операциям с затворами, действующими на две частицы или другие небольшие подсистемы. (Да, шлюзы Toffoli действуют на 3 входах, но в любом случае часто сводятся к вентилям CNOT с двумя кубитами.)

Безусловно, из-за полноты по Тьюрингу нет никаких сомнений в том, что квантовый компьютер может имитировать произвольную классическую или даже квантовую физику (хотя, возможно, там есть некоторые скептики из-за принципа неопределенности и так далее - мне было бы интересно услышать об этом тоже). Но мне кажется , что для моделирования квантовой физики произвольной эффективно один , по крайней мере нужен способ для имитации произвольных п-способ взаимодействия в основном / почти 2-полосных ворот.

Можно утверждать, что мы можем построить произвольные n-ходовые ворота, но очевидное доказательство после многих лет экспериментальных исследований заключается в том, что даже просто 2-ходовые ворота чрезвычайно сложно построить, и что n-ходовые ворота, безусловно, будут намного сложнее. (Существуют некоторые 3-сторонние квантовые эксперименты, например, неравенства с тремя частицами, но их сложно построить.)

[1] Реальные приложения квантовых вычислений (кроме безопасности)

[2] https://cstheory.stackexchange.com/a/10241/248

Как вы думаете, почему моделирование квантовой физики означает, что вы должны эффективно реализовывать произвольные квантовые ходовые взаимодействия? Если это ваше требование, квантовые компьютеры не могут сделать это эффективно.$n$

Вы можете записать ходовой унитарный вентиль, который реализует произвольную функцию bit-input -bit-output. Это позволило бы решить произвольную проблему с битами за один шаг. Это здравый смысл, что мы не можем найти квантовые системы в «реальной жизни», которые позволят нам сделать это.$n$$n$$n$$n$

Конечно, в реальной квантовой физике квантовая динамика является гамильтоновой, а не просто унитарной, но в произвольном линейном гамильтониане все еще имеется примерно параметров , и это делается с помощью 2-кубитных вентилей (которые имеют постоянное число параметров каждый) потребует экспоненциального количества ворот. Кроме того, я совершенно уверен, что возможность реализации произвольных ходовых гамильтонианов все же позволит вам строить произвольные двоичные функции на битах.$2^n$$n$$n$$O(n)$

Таким образом, требование, предъявляемое к квантовым компьютерам для эффективного моделирования произвольных ходовых взаимодействий, является слишком строгим. Что вам нужно, так это то, что квантовые компьютеры могут эффективно моделировать ходовые взаимодействия, которые фактически возникают в квантовой физике. Квантовые компьютеры способны эффективно моделировать локальную гамильтонову динамику для постоянной , которой может быть достаточно для моделирования взаимодействий, возникающих в реальной квантовой физике.$n$$n$$k$$k$

Если вы можете предложить какие-либо ходовые взаимодействия, которые возникают в квантовой физике и которые трудно квантовать для эффективного моделирования, это было бы действительно захватывающим событием. Тем не менее, я не знаю каких-либо текущих предложений для такого взаимодействия.$n$

Могут ли квантовые компьютеры эффективно имитировать квантовую теорию поля, все еще остается открытым вопрос, но в настоящее время в этом направлении достигнут прогресс .