Probabilistic Condition, Decision and Path Coverage of Circuit-based Quantum Programs

Cet article présente six critères de couverture probabilistes et structurels adaptés aux programmes quantiques basés sur des circuits, expose l'outil QaCoCo pour les évaluer sur 540 circuits, et révèle que, si la couverture des conditions et des décisions est élevée, la couverture des chemins est limitée par la complexité des portes et que la couverture structurelle montre une faible corrélation avec la détection de défauts.

L'essentiel

Imaginez que vous êtes inspecteur de qualité pour une usine magique et très étrange. Dans une usine normale (logiciel classique), vous pouvez parcourir la chaîne de montage, vérifier chaque machine individuelle et voir si chaque interrupteur a été actionné. Si vous voyez une machine qui ne s'est jamais allumée, vous savez que vous avez manqué un test.

Mais dans cette Usine Quantique, les machines ne s'allument pas simplement ou ne s'éteignent pas. Elles existent dans une « superposition », ce qui signifie qu'elles peuvent être à la fois allumées et éteintes en même temps jusqu'à ce que vous les regardiez. Et si vous les regardez trop tôt pour vérifier votre travail, toute l'usine s'effondre dans un seul état, ruinant la magie.

Ce papier présente une nouvelle façon d'inspecter ces usines magiques sans les briser. Voici le détail :

1. Le Problème : Le Piège de la « Ligne Droite »

En programmation classique, vous avez des instructions « si » (comme : Si le feu est rouge, arrêtez-vous ; sinon, avancez). Pour tester cela, vous devez vérifier à la fois le chemin « arrêtez-vous » et le chemin « avancez ».

Dans les circuits quantiques, il n'y a pas d'instructions « si » évidentes. À la place, il y a des Portes Contrôlées. Imaginez-les comme des interrupteurs magiques. Un interrupteur pourrait dire : « Si le Qubit A est dans un état magique spécifique, alors retournez le Qubit B. »

• L'Ancienne Erreur : Si vous exécutez simplement le circuit du début à la fin, chaque ligne de code s'exécute. Cela ressemble à une couverture parfaite de 100 %. Mais vous auriez pu manquer le fait que l'« interrupteur magique » n'a jamais réellement déclenché le « retournement » parce que les conditions n'ont jamais été réunies. C'est comme conduire une voiture sur une route qui n'a aucun virage ; vous avez parcouru toute la route, mais vous n'avez jamais testé les freins ni le volant.

2. La Solution : QaCoCo (L'Espion Invisible)

Les auteurs ont construit un outil appelé QaCoCo. Imaginez QaCoCo comme une équipe d'espions invisibles qui s'infiltrent dans l'usine.

• La Mise en Place : Avant que l'usine ne fonctionne, QaCoCo décompose les interrupteurs magiques complexes (comme une porte « Swap ») en leurs composants de base minuscules (comme de simples portes « Controlled-Not »).
• Le Coup de l'Espion : Au lieu de regarder directement les interrupteurs (ce qui effondrerait la magie), les espions utilisent un bouton spécial « sauvegarder ». Ils jettent un coup d'œil à la probabilité que l'interrupteur soit allumé ou éteint sans le toucher réellement. Ils enregistrent : « À cet instant précis, il y avait 50 % de chances que l'interrupteur se retourne, et 50 % de chances qu'il ne le fasse pas. »
• Le Résultat : Cela leur permet de calculer la couverture sans détruire l'état quantique.

3. Les Trois Types de Couverture (La Liste de Contrôle d'Inspection)

Le papier propose trois façons de mesurer à quel point vous avez bien testé l'usine :

• Couverture des Conditions (La Vérification de l'« Interrupteur ») : Chaque petit interrupteur à l'intérieur de la porte magique complexe a-t-il eu la chance d'être « allumé » et « éteint » ?
  • Analogie : Avez-vous testé l'interrupteur lumineux dans chaque pièce, même celles cachées derrière une porte ?
• Couverture des Décisions (La Vérification du « Chemin ») : La porte magique entière a-t-elle déclenché son action au moins une fois, et ne l'a-t-elle pas déclenchée au moins une fois ?
  • Analogie : Avez-vous conduit la voiture à la fois lorsque le feu était vert et lorsqu'il était rouge ?
• Couverture des Chemins (La Vérification de la « Combinaison ») : Avez-vous testé chaque combinaison possible d'interrupteurs se produisant en même temps ?
  • Analogie : Si vous avez 10 interrupteurs, avez-vous testé chaque combinaison possible d'eux étant allumés ou éteints ? (C'est le plus difficile, comme essayer de goûter chaque combinaison de saveurs possible dans une immense boutique de glaces).

4. La Touche « Probabiliste »

Dans le monde classique, si vous testez un interrupteur, il est soit « testé », soit « non testé ». Dans le monde quantique, il s'agit de confiance.

• Si un interrupteur a 50 % de chances d'être allumé et 50 % de chances d'être éteint, c'est un test parfait (Confiance Élevée). Vous avez vu les deux côtés de manière égale.
• Si un interrupteur a 99 % de chances d'être allumé et 1 % de chances d'être éteint, vous avez techniquement « testé » les deux, mais vous avez à peine vu le côté « éteint ». C'est un test faible (Confiance Faible).

Les auteurs ont créé un score de « Couverture Probabiliste ». C'est comme un bulletin de notes qui dit : « Vous avez couvert 100 % des chemins, mais votre score de confiance n'est que de 37 % parce que vous avez surtout vu le même résultat encore et encore. »

5. Ce qu'ils ont trouvé (Les Résultats)

Ils ont testé cela sur 540 circuits quantiques différents (une grande variété de programmes quantiques).

• Les Bonnes Nouvelles : Les outils ont révélé que la plupart des circuits étaient très bons en couverture de « Condition » et de « Décision » (environ 97 %). Il est facile de s'assurer que les interrupteurs peuvent se retourner.
• Les Mauvaises Nouvelles : La Couverture des Chemins était beaucoup plus faible (environ 71 %). Lorsque les circuits devenaient complexes (avec de nombreux interrupteurs travaillant ensemble), les « chemins » explosaient. Il est devenu impossible de tester chaque combinaison individuelle.
• Le Fossé de Confiance : Lorsqu'ils ont ajouté le score « Probabiliste », les chiffres ont chuté considérablement. Pour la Couverture des Chemins, la confiance n'était que d'environ 37 %. Cela signifie que même lorsque nous pensons avoir testé un chemin, nous ne l'avons souvent pas vu se produire avec suffisamment de certitude pour être sûrs.
• La Surprise du « Défaut » : Ils ont essayé de casser les circuits exprès (en injectant des bugs) pour voir si une couverture élevée signifiait qu'ils attraperaient les bugs. Ce n'était pas le cas. Tout comme dans le logiciel classique, avoir une couverture élevée ne garantit pas que vous avez trouvé toutes les erreurs. Vous pouvez couvrir 100 % de la route et toujours manquer un nid de poule.

Résumé

Ce papier dit : « Nous ne pouvons pas utiliser les tests de l'ancienne école pour les ordinateurs quantiques car ils sont probabilistes et fragiles. Nous avons construit un nouvel outil (QaCoCo) qui utilise des « espions invisibles » pour mesurer à quel point nous testons bien les interrupteurs quantiques. Nous avons constaté que bien que nous soyons bons pour vérifier les interrupteurs individuels, nous sommes mauvais pour vérifier toutes les combinaisons complexes, et notre « confiance » dans ces tests est souvent plus faible que nous ne le pensons. »

Résumé technique

1. Énoncé du problème

Les tests de logiciels classiques reposent fortement sur des critères de couverture structurelle (par exemple, couverture des lignes, des décisions et des chemins) pour évaluer l'adéquation des tests. Cependant, ces métriques sont largement inefficaces pour les programmes quantiques en raison des différences fondamentales dans leur architecture :

• Absence de flux de contrôle classique : Les circuits quantiques sont généralement implémentés comme des séquences de portes sans branches if-else explicites ni boucles trouvées dans le code classique.
• Nature probabiliste : Les états quantiques sont probabilistes. Une seule exécution ne garantit pas un résultat déterministe, et la mesure des états intermédiaires effondre la fonction d'onde, détruisant le calcul.
• Trivialité des métriques classiques : L'application de métriques classiques à un circuit quantique produit souvent des résultats triviaux (par exemple, 100 % de couverture des lignes) car le circuit s'exécute séquentiellement sans chemins alternatifs à « manquer ».
• Lacune dans les tests : Il existe un manque de compréhension concernant la manière de mesurer l'adéquation des tests pour les algorithmes quantiques, en particulier concernant la gestion des portes contrôlées (qui agissent comme des instructions conditionnelles quantiques) et la prise en compte de la confiance probabiliste que ces conditions soient exercées.

2. Méthodologie

Les auteurs proposent un cadre novateur et un outil nommé QaCoCo (Quantum Controlled Gate Coverage) pour répondre à ces défis.

A. Concept central : Portes contrôlées quantiques

Les auteurs identifient les portes contrôlées (par exemple, cx, cswap, ccx) comme l'équivalent quantique des instructions conditionnelles classiques (if). Ces portes déterminent si une opération est appliquée en fonction de l'état des qubits de contrôle.

• Transpilation : Puisque les portes contrôlées de haut niveau (comme cswap) sont décomposées en portes primitives (comme cx) lors de l'exécution, QaCoCo transpile d'abord le circuit pour révéler la logique conditionnelle sous-jacente (les portes cx).
• Instrumentation sans effondrement : Pour mesurer l'état des qubits de contrôle sans effondrer la fonction d'onde (ce qui ruinerait le résultat), QaCoCo injecte des instructions de simulation uniquement (save_expectation_value et save_probabilities) disponibles dans le simulateur Qiskit Aer. Ces instructions enregistrent la valeur d'attente et la distribution de probabilité des qubits à des points spécifiques sans perturber l'état quantique.

B. Critères de couverture proposés

L'article définit six nouveaux critères, adaptant les concepts classiques au domaine quantique :

1. Critères structurels :

   • Couverture des conditions : Mesure si chaque condition individuelle (qubit de contrôle d'une porte cx décomposée) évalue à la fois « vrai » (état $|1\rangle$) et « faux » (état $|0\rangle$).
   • Couverture des décisions : Mesure si chaque porte contrôlée (le point de décision) évalue à la fois « vrai » (opération appliquée) et « faux » (opération ignorée).
   • Couverture des chemins : Mesure si toutes les combinaisons de conditions au sein d'une décision sont exercées.

2. Critères probabilistes :

   • Reconnaissant qu'une branche « vraie » peut être prise avec une probabilité de 99 % ou de 51 %, les auteurs introduisent la Couverture probabiliste.
   • Cette métrique combine le pourcentage de couverture structurelle avec l'Indice de justice de Jain.
   • Interprétation : Une couverture structurelle de 100 % avec un faible indice de justice indique qu'une branche a été exercée presque exclusivement, offrant une faible confiance dans l'autre branche. Un indice de justice élevé (proche de 1) indique une exploration équilibrée des deux branches.

C. Implémentation de l'outil (QaCoCo)

• Entrée : Circuits OpenQASM (v2/v3).
• Processus : Transpilation $\rightarrow$ Instrumentation (injection d'instructions de sauvegarde) $\rightarrow$ Exécution (Qiskit Aer) $\rightarrow$ Extraction des données $\rightarrow$ Calcul de la couverture.
• Sortie : Pourcentages de couverture structurelle et probabiliste pour les conditions, les décisions et les chemins.

3. Contributions clés

1. Six critères de couverture adaptés aux quantiques : La première définition formelle de la couverture des conditions, des décisions et des chemins (et de leurs variantes probabilistes) spécifiquement pour les programmes quantiques basés sur des circuits.
2. Outil QaCoCo : Un outil Python autonome qui instrumente automatiquement, exécute et calcule ces métriques pour les circuits OpenQASM.
3. Extension probabiliste : L'introduction d'une mesure de confiance (Indice de justice de Jain) à la couverture structurelle, répondant à la nature probabiliste unique de l'exécution quantique.
4. Étude empirique à grande échelle : Une évaluation sur 540 circuits quantiques divers issus du jeu de données MQT Bench, analysant l'efficacité de la couverture et la surcharge.

4. Résultats expérimentaux

L'étude a évalué QaCoCo sur 540 circuits (sous-ensemble de MQT Bench) utilisant des entrées par défaut (tous les qubits initialisés à $|0\rangle$).

• RQ1 (Temps d'instrumentation) : QaCoCo prend en moyenne 28,56 secondes pour instrumenter un circuit. Le temps d'exécution est fortement corrélé à la profondeur du circuit et au nombre de portes contrôlées.
• RQ2 (Surcharge) : L'instrumentation augmente la taille du circuit par un facteur de 4,66 et le temps d'exécution par un facteur de 11,85 en moyenne. Cependant, pour 79 % des circuits, le temps d'exécution reste inférieur à une minute.
• RQ3 (Efficacité de la couverture) :
  • Couverture structurelle : Les entrées par défaut atteignent une couverture Conditionnelle (97,56 %) et Décisionnelle (97,63 %) élevée. Cependant, la Couverture des chemins est significativement plus faible (71,84 %), tombant à 49,82 % pour les circuits avec des portes multi-contrôlées en raison de l'explosion des chemins.
  • Couverture probabiliste : Lorsque l'on prend en compte la confiance (justice), les métriques chutent considérablement. La couverture Conditionnelle/Décisionnelle probabiliste moyenne est d'~88 %, mais la Couverture des chemins probabiliste n'est que de 37,18 %. Cela indique que bien que les chemins soient techniquement « touchés », ils ne sont souvent pas exercés avec une probabilité équilibrée.
• RQ4 (Corrélation avec la détection de défauts) :
  • Une expérience de test de mutation (287k mutants) a révélé une faible corrélation positive ($\rho \approx 0,33$) entre la couverture structurelle et la détection de défauts (score de mutation).
  • Crucialement, il n'y avait aucune corrélation entre la couverture probabiliste et la détection de défauts.
  • Cela s'aligne sur les constatations du logiciel classique : une couverture élevée ne garantit pas la détection de défauts, et les métriques de couverture doivent être considérées comme des outils de diagnostic plutôt que comme des prédicteurs directs de la correction.

5. Importance et implications

• Combler le fossé : L'article fournit le premier cadre rigoureux pour appliquer la couverture structurelle aux circuits quantiques, allant au-delà des métriques triviales de « couverture des lignes ».
• Gestion du probabilisme : En introduisant la couverture probabiliste, les auteurs soulignent que « couvrir » un chemin en informatique quantique n'est pas binaire ; la confiance et l'équilibre de cette couverture sont critiques pour l'adéquation des tests.
• Limites des entrées par défaut : L'étude démontre que les entrées par défaut ($|0\rangle$) sont insuffisantes pour atteindre une couverture de chemins élevée, en particulier dans les circuits complexes avec des portes multi-contrôlées, suggérant un besoin de stratégies avancées de génération d'entrées.
• Simulation vs Matériel : L'approche actuelle repose sur la simulation de vecteur d'état (Qiskit Aer). Les auteurs reconnaissent cette limitation et proposent un travail futur sur l'estimation statistique compatible avec le matériel (en utilisant des mesures en cours de circuit) pour rendre ces métriques applicables aux vrais dispositifs quantiques.
• Stratégie de test : La faible corrélation entre la couverture et les scores de mutation renforce l'idée que la couverture doit être utilisée pour guider la génération de tests et identifier les flux de contrôle inexplorés, plutôt que comme une métrique autonome « réussite/échec » pour la correction.

En résumé, ce travail établit une méthodologie fondamentale pour évaluer l'exhaustivité des tests quantiques, révélant que si la couverture structurelle simple est souvent élevée, l'exploration profonde des chemins et la confiance probabiliste restent des défis majeurs en ingénierie logicielle quantique.