The power of constant-depth quantum circuits of unbounded size

Résumé Technique : La Puissance des Circuits Quantiques à Profondeur Constante de Taille Illimitée

Énoncé du Problème
L'article étudie la puissance de calcul des circuits quantiques lorsque les restrictions sur la taille du circuit et l'espace auxiliaire sont levées. En complexité classique, la classe $AC^0$ (circuits à profondeur constante avec des portes ET/OU à entrée multiple/fan-in illimité) ne peut pas calculer la parité. Cependant, si la restriction de taille polynomiale est levée, chaque fonction booléenne peut être calculée en profondeur constante via des constructions de forme normale disjonctive (DNF). Les auteurs posent la question suivante : un phénomène similaire est-il vrai pour les circuits quantiques construits à partir de portes mono-qubits arbitraires et de portes de Toffoli généralisées ($QAC^0$) ? Plus précisément, est-il possible d'implémenter exactement toute opération unitaire en profondeur constante si la taille du circuit et le nombre de qubits auxiliaires sont illimités ?

Les auteurs cadrent cette enquête à travers quatre tâches de plus en plus générales :

1. Calculer l'appartenance à n'importe quel ensemble $L \subseteq \{0, 1\}^n$.
2. Implémenter toute permutation des états de la base de calcul.
3. Préparer tout état pur.
4. Implémenter toute unitaire arbitraire sur chaque état d'entrée.

Méthodologie
Les auteurs emploient une combinaison de constructions de circuits classiques réversibles, de techniques classiques probabilistes adaptées au domaine quantique et de protocoles de téléportation quantique.

• Constructions Classiques Réversibles : Les auteurs établissent d'abord que des permutations arbitraires de chaînes de bits peuvent être implémentées en profondeur constante à l'aide de portes Toffoli et de portes de diffusion (fanout). Ceci est réalisé via un schéma de « codage d'indicateur » : l'entrée est mappée vers un vecteur indicateur de dimension $2^n$ (où exactement une entrée est égale à 1), manipulé, puis décodé pour revenir à la chaîne originale. Cela permet l'évaluation parallèle de toutes les chaînes d'entrée possibles.
• Adaptation Probabiliste au Quantique : Pour préparer des distributions de probabilité et des états purs arbitraires, les auteurs adaptent une construction classique probabiliste. Cela implique d'échantillonner des bits indépendamment pour encoder une distribution basée sur la position du premier « 1 ». Dans le cadre quantique, cela est rendu cohérent en appliquant des rotations inverses aux qubits suivant le premier « 1 » afin de les ramener à l'état $|0\rangle$ sans détruire la superposition.
• Extensions de l'Ensemble de Portes : Bien que l'ensemble de portes principal comprenne des portes mono-qubits et des portes de Toffoli généralisées, les auteurs utilisent les portes de diffusion (fanout) comme un outil conceptuel. Ils citent les résultats de Grier, Morris et Wu [GMW26] et Rosenthal [Ros20] pour montrer que la diffusion peut être implémentée exactement en profondeur constante en utilisant uniquement l'ensemble de portes principal, bien que cela puisse nécessiter une augmentation de la taille du circuit vers des bornes doublement exponentielles.
• Réductions pour les Unitaires : Pour l'implémentation d'unitaires arbitraires, les auteurs ne fournissent pas de construction directe. Au lieu de cela, ils proposent plusieurs formulations équivalentes et réductions. Celles-ci incluent la réduction de l'implémentation d'unitaires à :
  • Le clonage de vecteurs d'une base orthonormée spécifiée.
  • La permutation de listes de vecteurs de base.
  • Le décodage de labels de base.
  • L'implémentation d'unitaires avec des sommes de lignes et de colonnes unitaires (via la forme normale d'Idel-Wolf).
  • L'implémentation d'involutions unitaires traceless (en utilisant un qubit propre supplémentaire).
• Téléportation Basée sur les Ports (PBT) : Pour approcher l'implémentation d'unitaires arbitraires sans corrections unitaires dépendantes de la porte spécifique, les auteurs utilisent la Téléportation Basée sur les Ports (PBT). Ils construisent un circuit unitaire qui réalise la PBT en utilisant des états enchevêtrés maximaux (ou les états de Choi de l'unitaire cible) et une mesure conjointe, suivis d'une sélection de port.

Contributions Clés et Résultats

1. Constructions Exactes en Profondeur Constante pour des Tâches Spécifiques :

   • Permutations : Des permutations arbitraires des états de la base de calcul peuvent être implémentées en profondeur constante (profondeur $\le 20$) en utilisant $O(n2^n)$ portes et des qubits auxiliaires.
   • Unitaires Diagonaux : Des unitaires diagonaux arbitraires peuvent être implémentés en profondeur constante (profondeur 7) en calculant des indicateurs, en appliquant des phases en parallèle, et en annulant le calcul (uncomputing).
   • Préparation d'État : Des états purs quantiques arbitraires peuvent être préparés en profondeur constante (profondeur $\le 37$) en utilisant $O(4^n)$ qubits et $O(n2^n)$ portes. Tous les qubits auxiliaires sont retournés à zéro.
   • Implémentation de la Diffusion (Fanout) : La diffusion peut être implémentée exactement en profondeur constante en utilisant uniquement des portes mono-qubits et de Toffoli généralisées, bien que cela puisse nécessiter une taille doublement exponentielle.

2. Réductions pour les Unitaires Arbitraires :
   Le papier démontre que l'implémentation d'unitaires arbitraires est équivalente à l'implémentation de plusieurs opérations spécifiques (par exemple, cloner des vecteurs de base, décoder des labels ou implémenter des involutions traceless). Cela recadre le problème ouvert de l'implémentation d'unitaires arbitraires en un ensemble de défis structurels équivalents.

3. Mesures Adaptatives et Téléportation de Porte :
   Les auteurs montrent que si des mesures intermédiaires adaptatives sont autorisées, toute porte au niveau $\ell$ de la hiérarchie de Clifford peut être implémentée avec une profondeur $O(\ell)$. De plus, l'implémentation d'une unitaire arbitraire se réduit à l'implémentation d'involutions unitaires traceless dans ce modèle adaptatif.

4. Approximation par Téléportation Basée sur les Ports (PBT) :
   Les auteurs construisent un circuit unitaire pour la Téléportation Basée sur les Ports (PBT) pour une dimension d'entrée $d$ et $M \ge d^2 - 1$ ports.

   • Profondeur : La profondeur du circuit est $O(\sqrt{d})$, ce qui est indépendant du nombre de ports $M$.
   • Fidélité : La fidélité d'enchevêtrement est bornée par $F_e \ge (1 - \frac{d^2-1}{2M})^2$.
   • Précision vs Profondeur : Pour toute dimension d'entrée $d$ fixée, l'approximation peut être rendue arbitrairement précise en augmentant $M$ sans augmenter la profondeur du circuit. Cependant, la dépendance vis-à-vis de la dimension d'entrée $d$ demeure ; la question de savoir si une borne de profondeur indépendante de $d$ peut être obtenue reste ouverte.
   • Implémentation : Le circuit utilise uniquement des portes mono-qubits et de Toffoli généralisées et ne nécessite aucune mesure intermédiaire.

Signification et Revendications
Le papier établit que le retrait des restrictions de taille et d'espace auxiliaire permet aux circuits quantiques à profondeur constante d'accomplir des tâches généralement impossibles dans les modèles de taille polynomiale à profondeur constante, telles que la préparation d'états arbitraires et la permutation d'états de base. Cela connecte directement la préparation d'états quantiques au calcul réversible classique et à la préparation de distributions de probabilité.

Cependant, le papier maintient une position modeste concernant l'implémentation d'unitaires arbitraires. Bien qu'il fournisse des constructions exactes en profondeur constante pour les permutations, les unitaires diagonaux et la préparation d'états, l'implémentation d'unitaires généraux reste un problème ouvert. Les auteurs fournissent des caractérisations équivalentes de ce problème mais ne le résolvent pas.

La contribution principale concernant les unitaires généraux est la construction PBT. Les auteurs démontrent que pour toute dimension d'entrée fixée, des unitaires arbitraires peuvent être approximés avec une précision arbitraire sans augmenter la profondeur du circuit en augmentant le nombre de ports. Cependant, la profondeur de cette construction passe à $O(\sqrt{d})$ avec la dimension d'entrée $d$. Les auteurs précisent explicitement que la question de savoir si cette dépendance vis-à-vis de $d$ peut être supprimée (c'est-à-dire obtenir une borne de profondeur indépendante de $d$) reste ouverte. Le travail souligne que la difficulté fondamentale de l'implémentation d'unitaires en profondeur constante ne réside pas dans la production d'une sortie arbitraire à partir d'une entrée fixe, mais dans la prescription de l'action sur chaque état d'entrée simultanément tout en préservant l'unitarité.