Quantumly controlled measurement, Hermitian conjugation and normalization in matrix-manipulation algorithms

Résumé Technique : Mesure à Contrôle Quantique, Conjugaison Hermitienne et Normalisation dans les Algorithmes de Manipulation de Matrices

Énoncé du Problème
L'article traite de trois limitations critiques des algorithmes quantiques existants pour la manipulation de matrices (spécifiquement ceux basés sur l'encodage des éléments de matrice dans les amplitudes de probabilité d'un état de superposition pur, comme proposé dans les références [33–35]) :

1. Inefficacité de la Post-Sélection : Les algorithmes actuels reposent sur la mesure d'un qubit ancilla unique pour filtrer les états « déchet » (garbage states) et sélectionner le résultat souhaité. Ce processus souffre d'une faible probabilité de succès qui diminue de manière polynomiale ou exponentielle avec la dimension de la matrice. Par conséquent, l'algorithme nécessite plusieurs exécutions pour obtenir le résultat voulu, ce qui réduit considérablement l'efficacité.
2. Incapacité à Gérer la Conjugaison Hermitienne : Bien que ces algorithmes puissent traiter des matrices complexes, des opérations spécifiques telles que la conjugaison hermitienne ne peuvent pas être réalisées dans le cadre d'encodage standard, ce qui restreint la variété des manipulations algébriques.
3. Contraintes de Normalisation Strictes : L'encodage des éléments de matrice dans un état quantique pur impose une condition de normalisation stricte ($\sum |a_{jk}|^2 = 1$). Cela limite le module des éléments de matrice, nécessissant un étalonnage spécifique qui peut ne pas être optimal pour toutes les applications.

Méthodologie
Les auteurs proposent trois extensions distinctes au cadre de manipulation de matrices :

1. Mesure à Contrôle Quantique (QCM - Quantumly Controlled Measurement) :

   • Au lieu d'une mesure projective standard sur un seul qubit ancilla ($B_1$), les auteurs introduisent un système ancilla à deux qubits ($B_1$ et $B_2$).
   • L'état du premier qubit ($B_1$) agit comme un contrôle pour un opérateur de mesure appliqué au second qubit ($B_2$).
   • Plus précisément, si le système est dans une superposition où le terme « utile » est intriqué avec $|1\rangle_{B_1}$ et le terme « déchet » avec $|0\rangle_{B_1}$, une porte C-NOT intrique $B_1$ avec $B_2$. Un opérateur de mesure contrôlée $W^{(3)}_{B_1B_2} = |1\rangle_{B_1}\langle 1| \otimes M_{B_2} + |0\rangle_{B_1}\langle 0| \otimes I_{B_2}$ est alors appliqué.
   • Ce mécanisme garantit que si la composante utile existe ($\alpha \neq 0$), la mesure sur $B_2$ est déclenchée de manière déterministe, provoquant l'effondrement du système vers l'état souhaité sans l'échec probabiliste associé à la post-sélection standard.

2. Encodage Séparé des Parties Réelles et Imaginaires :

   • Pour permettre la conjugaison hermitienne, les auteurs proposent d'encoder les parties réelles et imaginaires des éléments de matrice complexes dans deux sous-espaces orthogonaux en utilisant un sous-système supplémentaire d'un qubit ($M$).
   • L'état $|0\rangle_M$ étiquette la partie réelle et $|1\rangle_M$ étiquette la partie imaginaire.
   • La conjugaison hermitienne est ensuite réalisée via une opération SWAP sur les registres lignes/colonnes combinée à une opération $\sigma_z$ sur le registre $M$, effectuant ainsi la transposition et la conjugaison complexe.

3. Affaiblissement de la Contrainte de Normalisation :

   • Les auteurs introduisent un qubit auxiliaire supplémentaire ($K$) dans le schéma d'encodage.
   • L'état initial est modifié pour inclure un terme supplémentaire avec une amplitude $b$ associé à l'état $|0\rangle_K$, tandis que les éléments de matrice sont associés à $|1\rangle_K$.
   • Cela change la condition de normalisation d'une égalité ($\sum |a_{jk}|^2 = 1$) en une inégalité ($\sum |a_{jk}|^2 \leq 1$), permettant une plus grande flexibilité dans la magnitude des éléments de matrice.

Contributions Clés et Résultats

• Implémentation dans la Multiplication de Matrices : Les auteurs intègrent la QCM et les deux extensions d'encodage dans un algorithme de multiplication de matrices. Ils démontrent que l'algorithme peut effectuer une multiplication standard ainsi que des opérations impliquant des conjugués hermitiens (par exemple, $A^\dagger B$, $A B^\dagger$).
• Construction de Circuits : Des circuits quantiques détaillés sont présentés pour :
  • La sous-routine QCM.
  • L'opérateur de conjugaison hermitienne.
  • L'algorithme de multiplication de matrices modifié incorporant les trois extensions.
• Analyse de Complexité :
  • Espace : Les modifications ne nécessitent qu'un nombre constant de qubits supplémentaires (spécifiquement, quatre qubits supplémentaires pour les extensions d'encodage et un pour l'ancilla QCM dans le contexte de la multiplication). La complexité spatiale reste $O(n)$, où $N=2^n$ est la dimension de la matrice.
  • Profondeur : La profondeur du circuit reste $O(n)$. Les auteurs notent que bien que le temps d'exécution total des algorithmes précédents était effectivement de $O(2^n n)$ en raison de la nécessité de répétitions pour surmonter les faibles probabilités de succès, l'algorithme basé sur la QCM atteint le résultat en une seule exécution, maintenant la caractéristique de profondeur $O(n)$ du circuit lui-même.
• Récupération de la Normalisation : Les auteurs reconnaissent que la QCM supprime l'information probabiliste concernant la constante de normalisation $G$ (qui était auparavant dérivée de la probabilité de succès de la mesure). Ils proposent une méthode pour mesurer $G$ de manière probabiliste en exécutant l'algorithme plusieurs fois pour mesurer la probabilité de l'état auxiliaire $|0\rangle_K$, bien que cela nécessite des exécutions distinctes de la génération du résultat en un seul coup (single-shot).

Signification et Revendications
L'article affirme que l'introduction de la Mesure à Contrôle Quantique (QCM) résout fondamentalement le « problème de la post-sélection » inhérent aux algorithmes de matrices quantiques basés sur la mesure. En remplaçant le filtrage probabiliste des états déchet par un processus contrôlé quantiquement, l'algorithme élimine le surcoût exponentiel associé aux exécutions répétées.

Les auteurs soulignent que la QCM n'est pas simplement une technique d'amplification d'amplitude (comme l'algorithme de Grover) mais un opérateur distinct combinant le contrôle quantique et la mesure classique, offrant potentiellement un nouveau type de « contrôle quantique-classique ».

De plus, les extensions concernant la conjugaison hermitienne et les contraintes de normalisation assouplies élargissent l'applicabilité des algorithmes de manipulation de matrices à une classe plus large de matrices complexes et de scénarios d'encodage de données. Les auteurs affirment que bien que la réalisation physique pratique de la QCM ne soit pas encore détaillée en termes d'opérateurs quantiques/classiques standards, sa formulation théorique fournit une justification de la réalité des états de superposition quantique et offre une voie vers une algèbre linéaire quantique plus efficace.

L'article conclut que ces modifications peuvent être appliquées non seulement à la multiplication de matrices mais aussi à d'autres algorithmes discutés dans les références [34, 35], incluant l'addition de matrices, le calcul de déterminant, l'inversion et les solveurs de systèmes linéaires, ainsi qu'à d'autres algorithmes quantiques basés sur la mesure.