L'informatique quantique adiabatique est-elle aussi puissante que le modèle de circuit?

9

Une grande partie de la littérature sur l'informatique quantique se concentre sur le modèle de circuit. L'informatique quantique adiabatique n'est pas basée sur l'application d'une séquence d'opérateurs unitaires, mais sur la modification d'un hamiltonien dépendant du temps. Je recherche un aperçu de l'un des éléments suivants.

  1. L'informatique quantique adiabatique est-elle aussi puissante que le modèle de circuit, ou est-elle intrinsèquement moins puissante?
  2. Existe-t-il des classes de complexité spécifiquement liées à l'informatique adiabatique par opposition au modèle de circuit?
  3. Comment mesurer quantitativement la puissance du calcul adiabatique par rapport à la puissance du modèle de circuit?
cc.complexity-theory reference-request complexity-classes quantum-computing quantum-information vzn
la source
ok NdB oui, il n'a pas été formulé de manière parfaite, merci aux répondants pour obtenir des éclaircissements, exactement ce qui a été demandé. surgi en réaction à une autre question de personnes sur le chat , peut y poursuivre la discussion par toute personne intéressée. Je suis sûr que d'autres avec une représentation plus élevée pourraient trouver de meilleures questions, mais il semble y avoir une forte corrélation inverse. quant à bkg, toutes les références le sauvegardant ont été coupées par le premier montage. aussi, il y a longtemps posé une autre question qui a conduit à celle-ci mais cette autre question s'est vaporisée. poof
vzn
2
J'ai vu le montage précédent. Les communiqués de presse ne sont pas des articles de recherche. Plus précisément, pratiquement n'importe quel article de recherche vous aurait indiqué que l'informatique quantique adiabatique est essentiellement basée sur le qubit. Peu importe ce qui l'a incité: votre question ne montre pas beaucoup d'efforts - et l'activité pour le bien de l'activité est ce que les forums StackExchange essaient d' éviter .
Niel de Beaudrap
3
Vzn: le point est le suivant: pourquoi ne pas enquêter vous-même? Et si après enquête, vous ne trouvez aucune référence, pourquoi ne pas poser cette question? Ce serait constructif, et vous pourriez poser (et enquêter) cette question sur l'informatique quantique en général, pas seulement l'informatique adiabatique.
Niel de Beaudrap
4
@NieldeBeaudrap: Pour moi, il semblait qu'il utilisait simplement le "modèle qubit" comme substitut du modèle de circuit, ce qui n'est bien sûr pas une substitution précise, mais j'ai compris que c'était le sens de la question.
Joe Fitzsimons
1
@JoeFitzsimons: assez juste - c'est probablement l'approche la plus pratique, car elle implique que la question a une réponse sensée, c'est-à-dire celles ci-dessous. Bien que vzn doive éditer la question pour la poser réellement, si c'est le cas, pour la postérité.
Niel de Beaudrap

Réponses:

19

Deux clarifications rapides:

  1. Le CQ adiabatique est généralement "basé sur des qubits" tout comme le CQ basé sur circuit - je ne sais pas d'où vous vient l'idée que ce n'est pas le cas! (Bien que l'on puisse également utiliser des qutrits ou d'autres blocs de construction, dans le circuit ou les modèles adiabatiques.)

  2. Comme l'a souligné Mateus, le résultat à juste titre célèbre d'Aharonov et al. dit que "le QC adiabatique est équivalent au QC standard." Mais ce résultat doit être interprété avec un peu de soin. Il est valable si l'état final du calcul adiabatique peut être arbitraire - de sorte que, en particulier, l'état final peut coder toute l'histoire d'un calcul quantique basé sur un circuit. Cependant, si l'état final doit être un état de base de calcul classique --- comme c'est généralement le cas dans l' algorithme d'optimisation adiabatique(l'exemple "original" du QC adiabatique) --- alors le QC adiabatique peut certainement être simulé dans le modèle de circuit, mais l'inverse n'est pas connu et est loin d'être clair. Donc, avec cette dernière hypothèse, il est possible que l'optimisation adiabatique donne vraiment naissance à une nouvelle classe de complexité intermédiaire entre BPP et BQP.

Scott Aaronson
la source
3
L'article de Bacon et Flammia sur le calcul de l'état des grappes adiabatiques semble donner une autre route qui, à ma connaissance, contourne quelque peu le besoin d'une histoire, bien que vous ayez encore beaucoup de qubits supplémentaires.
Joe Fitzsimons
2
Cependant, le schéma Bacon & Flammia n'a pas un état fondamental unique et diffère donc considérablement de l'AQC conventionnel.
Norbert Schuch
3
@NorbertSchuch: Mais si vous ajoutez les termes supplémentaires du stabilisateur à l'hamiltonien initial correspondant à la fixation de l'état initial, alors l'état fondamental n'est pas dégénéré.
Joe Fitzsimons