Methods for Reducing Ancilla-Overhead in Block Encodings

Les ordinateurs quantiques promettent de résoudre des problèmes qui prendraient des millénaires à des machines classiques, mais ils sont notoirement fragiles. Pour effectuer des calculs complexes, ces machines s'appuient sur une technique appelée encodage par bloc (block encoding), qui leur permet de représenter des opérations mathématiques qui ne sont pas parfaitement réversibles, une nécessité pour des applications du monde réel comme la simulation de réactions chimiques ou la résolution d'équations différentielles. Considérez l'encodage par bloc comme un moyen de cacher un calcul complexe et non réversible à l'intérieur d'un processus quantique plus large et réversible en utilisant des bits d'aide supplémentaires, appelés ancillas. Ces bits d'aide agissent comme un espace de travail temporaire, permettant à l'ordinateur quantique de manipuler des données sans enfreindre les lois fondamentales de la mécanique quantique. Cependant, à mesure que les algorithmes deviennent plus complexes, ils nécessitent de plus en plus de ces bits d'aide. Comme le matériel quantique est actuellement limité dans le nombre de qubits qu'il peut contenir, cette demande d'espace supplémentaire crée un goulot d'étranglement sévère, forçant souvent les chercheurs à choisir entre exécuter un calcul ou se retrouver totalement à court de mémoire.

Une équipe de chercheurs de l'Université de Californie à Berkeley et de l'Institut mathématique Alfréd Rényi de Hongrie a développé deux nouvelles méthodes pour réduire considérablement le nombre de ces bits d'aide requis pour les encodages par bloc. Leurs travaux abordent le problème sous deux angles différents, offrant un compromis entre l'espace et le temps dans le premier cas, et entre l'espace et la précision dans le second. La première méthode introduit un moyen de « nettoyer » l'espace de travail une fois qu'un calcul est terminé. Dans de nombreux algorithmes quantiques, une fois qu'un encodage par bloc est utilisé, les bits d'aide restent dans un état désordonné et intriqué qui ne peut être réutilisé. Les chercheurs ont conçu un protocole qui réinitialise de manière cohérente presque tous ces bits d'aide vers un état zéro propre, les libérant ainsi pour une utilisation dans les parties ultérieures de l'algorithme. Ce processus n'est pas instantané ; il nécessite des étapes de calcul supplémentaires, échangeant ainsi du temps supplémentaire contre la ressource précieuse que constitue l'espace supplémentaire. Le résultat est un système capable d'effectuer les mêmes opérations complexes en utilisant un seul bit d'aide, quel que soit le nombre de bits initialement nécessaires, à condition que le calcul ne soit pas parfaitement précis mais suffisamment proche pour un usage pratique.

La seconde partie de leurs travaux s'attaque au défi spécifique de la multiplication de nombreux encodages par bloc, une exigence courante pour simuler l'évolution des systèmes physiques au fil du temps. Traditionnellement, multiplier un grand nombre de ces encodages nécessitait un nombre de bits d'aide qui augmentait de manière logarithmique avec le nombre d'opérations, une demande qui dépasse rapidement les capacités du matériel disponible. Les chercheurs ont prouvé que pour une multiplication exacte et parfaite, cette exigence logarithmique est une limite stricte qui ne peut être contournée. Cependant, ils ont montré que si l'on est prêt à accepter une erreur infime et contrôlée, cette limite peut être brisée. Ils ont introduit un nouveau gadget qui effectue ces multiplications avec un nombre constant et faible de bits d'aide, quel que soit le nombre d'opérations enchaînées. L'erreur introduite par cette compression est extrêmement faible et diminue rapidement à mesure que le nombre de bits d'aide augmente légèrement. Cette approche est particulièrement efficace pour les simulations où les étapes individuelles sont déjà très proches de ne rien faire, un scénario courant dans les simulations physiques où de petits pas de temps sont utilisés pour suivre des changements graduels.

Pour s'assurer que ces calculs compressés restent utiles, les chercheurs ont également démontré comment utiliser une technique appelée amplification d'amplitude aveugle (oblivious amplitude amplification). Cette méthode agit comme un filtre qui augmente la probabilité de succès du calcul, transformant efficacement un processus qui pourrait échouer souvent en un processus qui réussit presque à chaque fois, même en utilisant la méthode compressée et approximative. Les résultats suggèrent qu'en gérant soigneusement le compromis entre précision et utilisation des ressources, les algorithmes quantiques peuvent devenir beaucoup plus efficaces. Il ne s'agit pas seulement d'un exercice théorique ; les méthodes sont directement applicables à la simulation de la dynamique hamiltonienne, qui décrit comment l'énergie se déplace à travers un système, et à la résolution d'équations différentielles quantiques, qui sont essentielles pour modéliser tout, de la dynamique des fluides aux réactions chimiques. En réduisant la surcharge d'ancillas, ces techniques pourraient permettre aux ordinateurs quantiques actuels et futurs de s'attaquer à des problèmes qui étaient auparavant hors de portée en raison d'un manque de mémoire disponible.