Peut-on quantifier le «degré de quanticité» dans un algorithme quantique?

L'intrication est souvent considérée comme l'ingrédient clé qui fait bien les algorithmes quantiques ... quantiques, et cela peut être retracé aux états de Bell qui détruisent l'idée de la physique quantique en tant que modèle probabiliste à état caché. Dans la théorie de l'information quantique (d'après ma compréhension plutôt faible), l'intrication peut également être utilisée comme une ressource concrète qui limite la capacité de faire certains types de codage.

Mais à partir d'autres conversations (j'ai récemment siégé au comité de doctorat d'un physicien travaillant sur les méthodes quantiques), je suppose que l'intrication est difficile à quantifier, en particulier pour les états quantiques à états mixtes. Plus précisément, il semble difficile de dire qu'un état quantique particulier contient X unités d'intrication (la thèse de doctorat de l'étudiant visait à essayer de quantifier les quantités d'intrication "ajoutées" par des opérations de porte bien connues). En fait, une récente thèse de doctorat suggère qu'une notion appelée «discorde quantique» pourrait également être pertinente (et nécessaire) pour quantifier la «quanticité» d'un algorithme ou d'un état.

Si nous voulons traiter l'intrication comme une ressource comme l'aléatoire, il est juste de se demander comment en mesurer la quantité "nécessaire" pour un algorithme. Je ne parle pas de déquantification complète , mais simplement d'un moyen de mesurer la quantité.

Existe-t-il actuellement un moyen accepté de mesurer la "quanticité" d'un état ou d'un opérateur, ou d'un algorithme en général?

Ça dépend du contexte.

1. Pour les algorithmes quantiques, la situation est délicate, car pour tout ce que nous savons, P = BPP = BQP. Nous ne pouvons donc jamais dire qu'un algorithme quantique fait quelque chose qu'aucun algorithme classique ne peut faire; seulement quelque chose avec lequel une simulation naïve aurait du mal. Par exemple, si un circuit quantique est dessiné sous forme de graphique, il existe alors une simulation classique qui s'exécute en temps exponentiel dans la largeur d'arbre du graphique ). La largeur d'arbre peut donc être considérée comme une limite supérieure de la «quanticité», mais pas une mesure précise.

   Parfois, la mesure de la quanticité dans les algorithmes est confondue avec la tentative de mesurer la quantité d'intrication produite par un algorithme, mais nous pensons maintenant qu'un ordinateur quantique bruyant pourrait avoir des avantages de calcul par rapport à un ordinateur classique, même avec tellement de bruit que ses qubits ne sont jamais dans un état intriqué (par exemple, le modèle à un qubit propre ). Ainsi, le consensus est désormais davantage du côté de la pensée de la quanticité dans les algorithmes quantiques en relation avec la dynamique plutôt qu'avec les états générés en cours de route. Cela peut aider à expliquer pourquoi la «déquantification» n'est généralement pas possible.

2. Pour les états quantiques bipartites, où le contexte est des corrélations bipartites, nous avons beaucoup de bonnes mesures de quantum. Beaucoup ont des défauts, comme être NP-dur, ou non additif, mais nous avons néanmoins une compréhension assez sophistiquée de cette situation. Voici une revue récente .

3. Il existe d'autres contextes, comme lorsque nous avons un état quantique et que nous souhaitons choisir entre différentes mesures incompatibles. Dans ce cadre, il y a des principes d'incertitude qui nous disent des choses sur l'incompatibilité des mesures. Plus les mesures sont incompatibles, plus la situation est «quantique». Cela est lié à la cryptographie et aux capacités zéro erreur des canaux bruyants , entre autres choses.

La réponse d'Aram est excellente, alors s'il vous plaît ne me prenez pas à poster une réponse car en tout cas en désaccord avec ce qu'il a dit, je la complète simplement.

$\frac{1}{\sqrt{2}}\mid 000\rangle + \frac{1}{\sqrt{2}}\mid 111\rangle$$\frac{1}{\sqrt{3}}\mid 100\rangle + \frac{1}{\sqrt{3}}\mid 010\rangle + \frac{1}{\sqrt{3}}\mid 001\rangle$

Cela est particulièrement pertinent pour la question posée, car elle semblerait exclure toute mesure monotone de "quantumness" basée sur des mesures d'intrication.

Un point de vue théorique plus complexe peut être trouvé dans la Sec. 8 de l'article de R. Josza Introduction au calcul quantique basé sur la mesure . Il déclare ce qui suit:

Les modèles basés sur la mesure fournissent un formalisme naturel pour séparer un algorithme quantique en "parties classiques et parties quantiques".

Il énonce également une conjecture sur la quantité de "quantumness" requise par un algorithme BQP:

$O(\log n)$

Voir l'article pour une explication claire de la couche quantique et du modèle en général. La conjecture est toujours ouverte et je suppose que c'est un bon moyen de quantifier la quantité de "quantumness" d'un algorithme, au moins du côté de la complexité de calcul.