Quelle est la preuve que les ordinateurs quantiques peuvent simuler efficacement des systèmes mécaniques quantiques arbitraires?

JBV a suggéré de transformer certains commentaires en question, alors voici.

Une autre question [1] pose sur les applications de l'informatique QM. Une réponse [2] était "simuler efficacement la mécanique quantique". Apparemment, cette idée remonte aux premiers écrits de Feynman sur le sujet; même si je n'ai pas de référence. Donc:

Question. Quelle est la preuve qu'un ordinateur quantique peut simuler efficacement un système mécanique quantique arbitraire?

À un certain niveau, cela semble fondamental. Cependant, cela ne semble pas être trivial pour la raison suivante: la plupart des publications sur l'informatique quantique semblent se réduire aux opérations sur les portes agissant sur deux particules ou d'autres petits sous-systèmes. (Oui, les portes Toffoli agissent sur 3 entrées, mais de toute façon sont souvent réduites à des portes CNOT à deux qubits.)

En raison de l'exhaustivité de Turing, il ne fait aucun doute qu'un ordinateur quantique peut simuler la physique classique ou même quantique arbitraire (bien qu'il y ait peut-être des opposants en raison du principe d'incertitude, etc. - je serais curieux d'en entendre parler aussi). Mais il me semble que pour simuler la physique quantique arbitraire efficace dont on a besoin au moins un moyen de simuler arbitraires n sens des interactions dans la plupart / presque 2 voies portes.

On pourrait affirmer que nous pouvons construire des portes arbitraires à n voies , mais la preuve évidente après de nombreuses années de recherche expérimentale est que même les portes à 2 voies sont extrêmement difficiles à construire, et que les portes à n voies seraient sûrement beaucoup plus difficiles. (Il existe des expériences quantiques à 3 voies , par exemple des inégalités de cloche à 3 particules, mais elles sont difficiles à construire.)

[1] Applications réelles de l'informatique quantique (sauf pour la sécurité)

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

reference-request quantum-computing application-of-theory vzn
la source

En outre, l'idée générale de l'équivalence informatique QM avec la simulation physique QM est apparemment née avec Feynman, qui semblait le considérer comme une donnée ou une hypothèse [qui était plus un brillant physicien qu'un informaticien] ... par exemple dans le document et la conférence , Simuler la physique avec les ordinateurs , 1982

vzn

Réponses:

$n$

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

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

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

$n$

Que ce soit les ordinateurs quantiques peuvent efficacement Simuler la théorie du champ quantique est encore une question ouverte, mais les progrès sont actuellement en cours de fait sur elle.

Peter Shor
la source

n'est-ce pas une faute de frappe en 1ère ligne "devrait" => "ne devrait pas". et notez que je me concentre sur la question plus stricte de l'efficacité, et non de la simple équivalence. accepter que les ordinateurs QM sont Turing complets. puisque vous dites que tout cela est assez simple, que diriez-vous du cas simple de simulation d'un système quantique à n particules où aucune particule n'est isolée les unes des autres? comment cela se fait-il avec les qubits?

vzn

n

$n$

prendra votre parole, mais mon principal pt-- est-ce discuté n'importe où dans la littérature? Il semble que toutes ces mises en garde pourraient facilement remplir au moins un document. vous semblez affirmer que tous les hamiltoniens physiques sont probablement simulables efficacement via des qubits, mais cela doit être étoffé mathématiquement. & Je pense qu'il est suffisamment non trivial pour que les autorités ne déclarent pas clairement qu'une simulation QM efficace de toutes les configurations QM arbitraires est intrinsèquement faisable. peut-être que des influences environnementales, par exemple des configurations de champ électrique ou magnétique appliquées, pourraient compliquer l'hamiltonien.

vzn

Je crois l'avoir vu discuté quelque part, mais je ne me souviens pas où. Dire quels hamiltoniens peuvent être implémentés physiquement est une question délicate ... puisque la dynamique de la nature trouve son origine dans la théorie quantique des champs, montrant que QFT peut être simulé efficacement avec un ordinateur quantique pourrait répondre à cette question, mais (1) nous sommes toujours très long à prouver et (2) cela pourrait être quelque chose comme dire que nous pouvons simuler la turbulence en utilisant la dynamique atomique sous-jacente. Dans un certain sens, c'est peut-être vrai, mais c'est clairement la mauvaise façon de le faire.

Peter Shor