Informatique quantique unidirectionnelle temporairement plate

Je suis physicien dans l'âme et je pense donc que l'informatique quantique à sens unique est géniale. En particulier, l'informatique quantique basée sur la mesure de l'état des graphes (MBQC) a été un très bon développement dans la recherche sur l'informatique quantique, à l'origine de Raussendorf & Briegel . Il suffit de préparer un état enchevêtré multipartite comme décrit par un graphique, puis d'effectuer des mesures séquentielles sur chaque nœud ou qubit (mesures adaptatives pour les calculs déterministes).

Un autre excellent aspect de cette approche est que les circuits de Clifford peuvent être mis en œuvre en un seul cycle de mesures, comme l'ont montré Raussendorf, Browne et Briegel . Ces circuits peuvent être simulés de manière classique (efficacement) comme le montrent Gottesman et Knill, c'est donc une connexion intéressante entre la simulation classique et les ressources temporelles.

Cependant, tous les circuits MBQC à état de graphes temporellement plats (consistant en une série de mesures) ne sont pas censés être simulables classiquement. Par exemple, les familles de circuits dans le modèle de circuit quantique consistant en des portes de navettage appelées circuits IQP comme introduits par Shepherd et Bremner peuvent être implémentées en un seul pas de temps dans MBQC. Ces circuits IQP ne seraient pas classiquement simulables (en termes de complexité de calcul, cela conduirait à un effondrement de la hiérarchie polynomiale) .

Voir aussi une belle description d'une classe de circuits implémentés en un seul pas de temps ici . Étant donné que les unités de navettage / diagonales peuvent avoir un comportement intéressant, mais les circuits sans navettage peuvent être simulés de façon classique. Il serait intéressant de disposer de circuits non commutables pouvant être mis en œuvre mais dont la simulation classique ne s'est pas encore révélée.

Quoi qu'il en soit, ma question est:

Existe-t-il d'autres circuits intéressants qui peuvent être mis en œuvre en un seul pas de temps dans MBQC?

Bien que je préfère les relations à la complexité de calcul ou à la simulation classique, je trouverais quelque chose d'intéressant.

Edit: Après l'excellente réponse de Joe ci-dessous, je devrais clarifier quelques choses. Comme Joe l'a dit (et quelque peu embarrassant je l'ai dit dans un de mes propres articles), les circuits MBQC à mesure unique sont en IQP. Pour être plus précis, je m'intéresse à des circuits intéressants dans les problèmes d'IQP qui peuvent être implémentés en une seule série de mesures en MBQC. Les circuits de Clifford sont un exemple intéressant. S'il y avait d'autres exemples qui peuvent être simulés de façon classique, ce serait extrêmement intéressant. Étant donné que la simulation de circuits IQP est considérée comme peu probable de manière classique, il serait intéressant de trouver des exemples de circuits qui le sont.

Compte tenu de la mise à jour de la question, j'ai pensé qu'il était préférable de poster ceci comme une nouvelle réponse, car elle est totalement différente de ma réponse précédente, et j'espère qu'elle est intéressante.

Il semble par la nouvelle formulation de la question qu'il y a une supposition cachée que l'état de la ressource MBQC a un nombre de qubits polynomial dans le nombre de qubits logiques. Cela ne doit pas nécessairement être le cas, ce qui conduit à une situation potentiellement intéressante. Il est possible de construire des calculs basés sur des mesures à couche unique pour lesquels l'état de la ressource est nécessairement exponentiel dans le nombre de qubits logiques, .$n$

$j$$X$$Z$$\exp{\big(i \theta \prod_i Z_i \big)}$$i$$j$$j$$|0\rangle\langle 0|\otimes I + |1\rangle\langle 1|\otimes \prod_i Z_i$$|+\rangle$$\frac{1}{\sqrt{2}}\left(|0\rangle \otimes I + |1\rangle\otimes \prod_i Z_i\right)$$\exp(i\theta X)$$\frac{1}{\sqrt{2}}\left(|0\rangle \otimes (\cos \theta I + i \sin \prod_i Z_i) + |1\rangle\otimes (\prod_i Z_i\right)(\cos \theta I + i \sin \prod_i Z_i)$$\prod_i Z_i$$\cos \theta I + i \sin \prod_i Z_i$$\exp{\big(i \theta \prod_i Z_i \big)}$

$n$$C....CZ$gate) est un exemple d'une telle opération qui nécessite un nombre exponentiel de portes de navettage, bien qu'elle puisse être réalisée avec un nombre linéaire de portes de non-navettage. Ainsi, il est possible de construire des calculs basés sur des mesures sur une seule couche qui mettent en œuvre des programmes X exponentiels dans le nombre de qubits logiques, et donc en dehors d'IQP pour les qubits logiques (bien qu'à l'intérieur d'IQP pour les qubits physiques).

Il y a potentiellement un problème ici, dans la mesure où ils nécessitent un nombre exponentiel de paramètres pour spécifier de manière unique toutes les paires du programme X. Cependant, si vous considérez que de tels angles sont générés de manière algorithmique (disons avec la restriction que chaque angle peut être calculé en temps polynomial), il n'est même pas clair si la simulation d'un tel calcul peut être effectuée dans BQP.

Cela n'a pas de sens pour moi de poser des questions sur les opérateurs non-navetteurs mis en œuvre en un seul pas de temps (bien que la profondeur constante soit certainement logique). Cependant, vous pouvez implémenter des portes non commutantes sur le sous-espace logique d'un MBQC qui sont implémentées à l'aide de mesures de navettage sur l'état des ressources, bien que les portes implémentées ne soient pas déterministes.

En fait, je crois que vous regardez IQP plus étroitement que vous ne le devriez probablement. La réponse à votre question est que tout MBQC qui peut être implémenté dans une seule couche de mesure dans MBQC est contenu dans IQP. C'est simplement parce que plutôt que d'exprimer le résultat en termes d'espace logique de Hilbert, vous pouvez l'exprimer comme une série d'opérations de navettage sur les qubits physiques. Shepherd et Bremner traitent en fait de cela dans leur article (dans la section 5.2 où de telles opérations sont appelées programmes graphiques).