Informatique quantique - Relation entre le modèle hamiltonien et unitaire

16

Lors du développement d'algorithmes en informatique quantique, j'ai remarqué qu'il existe deux modèles principaux dans lesquels cela se fait. Certains algorithmes - comme pour le problème de l'arbre NAND hamiltonien (Farhi, Goldstone, Guttman) - fonctionnent en concevant un hamiltonien et un état initial, puis en laissant le système évoluer selon l'équation de Schrödinger pendant un certain temps avant d'effectuer une mesure.t

D'autres algorithmes - tels que l'algorithme de Shor pour l'affacturage - fonctionnent en concevant une séquence de transformations unitaires (analogue aux portes) et en appliquant ces transformations une à la fois à un état initial avant d'effectuer une mesure.

Ma question est, en tant que novice en informatique quantique, quelle est la relation entre le modèle hamiltonien et le modèle de transformation unitaire? Certains algorithmes, comme pour le problème de l'arbre NAND, ont depuis été adaptés pour fonctionner avec une séquence de transformations unitaires (Childs, Cleve, Jordan, Yonge-Mallo). Chaque algorithme d'un modèle peut-il être transformé en algorithme correspondant dans l'autre? Par exemple, étant donné une séquence de transformations unitaires pour résoudre un problème particulier, est-il possible de concevoir un hamiltonien et de résoudre le problème dans ce modèle à la place? Et l'autre sens? Dans l'affirmative, quelle est la relation entre le temps dans lequel le système doit évoluer et le nombre de transformations unitaires (portes) nécessaires pour résoudre le problème?

J'ai trouvé plusieurs autres problèmes pour lesquels cela semble être le cas, mais aucun argument clair ou preuve qui indiquerait que cela est toujours possible, voire vrai. C'est peut-être parce que je ne sais pas comment s'appelle ce problème, je ne sais donc pas quoi rechercher.

user340082710
la source
3
Chaque algorithme de temps polynomial dans l'un correspond à un algorithme de temps polynomial dans l'autre, mais il n'est pas clair que le degré du polynôme sera le même. J'espère que quelqu'un trouvera des références. Ces résultats ont été prouvés aux premiers jours du calcul quantique, et il devrait maintenant y avoir de meilleures preuves de ces théorèmes.
Peter Shor
est-ce que cela se rapporte à ce que l'on appelle l'image Heisenberg vs Schroedinger de QM qui concerne la façon dont les opérateurs sont définis? aussi si ce n'est pas couvert par Nielsen & Chuang, cela semblerait être un oubli majeur! le papier d'arbre NAND utilise des "oracles hamiltoniens" qui semblent être introduits par Farhi / Gutmann 1998. voici un bel article d'enquête sur les oracles hamiltoniens par Mochon 2007
vzn
Le lien du livre que vous avez fourni est en fait le manuel que nous avons utilisé dans mon cours de premier cycle en traitement de l'information quantique. Le livre est vraiment orienté vers l'approche unitaire (dans le contexte des oracles également), mais pas tellement dans le contexte des hamiltoniens. Mon cours de premier cycle était axé sur une perspective cs et non sur une perspective physique, c'est pourquoi je connais le mieux le modèle unitaire.
user340082710
Le document que vous avez également fourni est une bonne référence en général, mais je ne pense pas qu'il réponde à ma question non plus. Enfin, j'ai jeté un coup d'œil à l'image Heisenberg vs Schroedinger de QM, et elle semble liée, mais je pense que ma question est différente (bien que je puisse me tromper - il était difficile de suivre les entrées de Wikipedia).
user340082710
Je pense qu'il existe différentes façons d'interpréter votre question et au lieu de répondre à toutes les interprétations, j'aimerais vous poser la question suivante: pourriez-vous être plus précis sur la version du modèle hamiltonien que vous avez en tête? Quelle est la mesure de la complexité de ce modèle? (c.-à-d., qu'est-ce qui compte à quel point il est difficile de résoudre un problème dans le modèle hamiltonien?) Comment l'apport au problème est-il donné? Est-il donné explicitement ou devez-vous interroger l'entrée via un oracle?
Robin Kothari

Réponses:

10

Pour montrer que l'évolution hamiltonienne peut simuler le modèle de circuit, on peut utiliser le papier Calcul universel par marche quantique multi-particules , qui montre qu'un type très spécifique d'évolution hamiltonienne (marches quantiques multi-particules) est BQP complet, et peut donc simuler le modèle de circuit.

Voici un document d'enquête sur la simulation de l'évolution quantique sur un ordinateur quantique. On peut utiliser les techniques de cet article pour simuler le modèle d'évolution hamiltonien des ordinateurs quantiques. Pour ce faire, il faut utiliser la "trottérisation", ce qui diminue considérablement l'efficacité de la simulation (bien qu'elle n'introduise qu'une explosion polynomiale en temps de calcul).

Peter Shor
la source
Merci! Ces références semblent assez bonnes et devraient pouvoir me donner une idée de la façon dont cela se fait.
user340082710