¿Cuál es la prueba de que las computadoras cuánticas pueden simular eficientemente sistemas mecánicos cuánticos arbitrarios?

JBV sugirió que convirtiera algunos comentarios en una pregunta, así que aquí va.

Otra pregunta [1] es sobre las aplicaciones de la computación QM. Una respuesta [2] fue "simular eficientemente la mecánica cuántica". Aparentemente, esta idea se remonta a los primeros escritos de Feynman sobre el tema; aunque no tengo una referencia. Entonces:

Pregunta. ¿Cuál es la prueba de que una computadora cuántica puede simular eficientemente un sistema mecánico cuántico arbitrario?

En un nivel, esto parece básico. Sin embargo, esto no parece ser trivial por la siguiente razón: la mayoría de la literatura sobre computación cuántica parece reducirse a operaciones en puertas que actúan sobre dos partículas u otros subsistemas pequeños. (Sí, las puertas Toffoli actúan en 3 entradas, pero de todos modos a menudo se reducen a puertas CNOT de dos qubits).

Seguramente no hay duda, debido a la integridad de Turing, de que una computadora cuántica puede simular física clásica o incluso cuántica arbitraria (aunque tal vez haya algunos detractores allí debido al principio de incertidumbre, etcétera, también me gustaría saber sobre eso). Pero me parece que para simular la física cuántica arbitraria de manera eficiente, al menos se necesita una forma de simular interacciones arbitrarias de n vías en puertas en su mayoría / casi de 2 vías .

Se podría argumentar que podemos construir puertas arbitrarias n-way , pero la evidencia clara después de muchos años de investigación experimental es que incluso solo las puertas de 2 vías son extremadamente difíciles de construir, y que las puertas n-way seguramente serían mucho más difíciles. (Hay algunos experimentos cuánticos de 3 vías , por ejemplo , desigualdades de campana de 3 partículas, pero son difíciles de construir).

[1] Aplicaciones del mundo real de la computación cuántica (excepto por seguridad)

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

reference-request quantum-computing application-of-theory vzn
fuente

Además, la idea general de la equivalencia de la computadora QM con la simulación física QM aparentemente se originó con Feynman, quien parecía tomarlo como un hecho o una suposición [quién era más un físico brillante que un científico de la computación] ... por ejemplo, en el artículo y la conferencia. , Simulando la física con las computadoras , 1982

vzn

Respuestas:

$n$

$n$ $n$ $n$ $n$

$2^n$ $n$ $n$ $O(n)$

$n$ $n$ $k$ $k$

$n$

Ordenadores cuánticos pueden o no pueden teoría cuántica de campos eficiente Simular es todavía una cuestión abierta, pero es el progreso actualmente se hace en él.

Peter Shor
fuente

no es que un error tipográfico en la primera línea "debería" => "no debería". y tenga en cuenta que me estoy centrando en el tema más estricto de la eficiencia, no en la mera equivalencia. acepte que las computadoras QM están Turing completas. dado que usted dice que todo esto es bastante sencillo, ¿qué tal el simple caso de simular un sistema cuántico de n partículas donde no hay partículas aisladas entre sí? ¿Cómo se hace eso con qubits?

vzn

n

$n$

tomaré tu palabra, pero mi punto principal: ¿se discute esto en alguna parte de la literatura? Parece que todas esas advertencias podrían llenar fácilmente un papel al menos. parece estar afirmando que es probable que todos los hamiltonianos físicos sean eficientemente simulables a través de qubits, pero eso debe desarrollarse de alguna manera matemáticamente. & Creo que es lo suficientemente trivial como para que las autoridades no puedan decir con soltura que la simulación eficiente de QM de todas las configuraciones arbitrarias de QM es intrínsecamente factible. quizás las influencias ambientales, por ejemplo, las configuraciones de campos eléctricos o magnéticos aplicados podrían complicar el hamiltoniano.

vzn

Creo que lo he visto discutido en alguna parte, pero no recuerdo dónde. Decir qué hamiltonianos se pueden implementar físicamente es una pregunta difícil ... ya que la dinámica de la naturaleza se origina en la teoría del campo cuántico, mostrando que QFT se puede simular eficientemente con una computadora cuántica podría responder esta pregunta, pero (1) todavía estamos Un tiempo muy largo para probar esto y (2) esto podría ser algo así como decir que podemos simular la turbulencia utilizando la dinámica atómica subyacente. En cierto sentido, puede ser cierto, pero es claramente la forma incorrecta de hacerlo.

Peter Shor