L'article "Methods for Reducing Ancilla-Overhead in Block Encodings" de Francisca Vasconcelos et András Gilyén présente des techniques novatrices pour réduire les coûts supplémentaires des qubits d'ancillaire dans les encodages en blocs, une primitive fondamentale dans les algorithmes quantiques. Les principales contributions sont :
1. **Encodages en blocs approximatifs avec une seule ancillaire** : L'article propose une méthode pour approximativement inverser tous les ancillae sauf un dans un encodage en bloc, fournissant un "échange entre espace et temps". Cela permet de réutiliser les ancillae pour des parties ultérieures d'un algorithme quantique. La méthode est montrée comme liée au problème de "correction de phase" dans le traitement de signaux quantiques modulaires.
2. **Multiplication approximative des encodages en bloc** : L'article évalue le nombre minimal d'ancillae nécessaire pour la multiplication cohérente des encodages en bloc. Il prouve que ⌈log2 K⌉ ancillae est optimal pour une multiplication exacte. Il propose également le Gadget de Compression d'Addition Modulaire p (p-MACG), qui réalise une multiplication approximative avec O(1) d'ancillae supplémentaires pour des encodages en blocs avec une déviation bornée par l'identité.
3. **Applications** : L'article discute des applications du p-MACG à la simulation hamiltonienne et aux solveurs d'équations différentielles quantiques. Il démontre également comment l'amplification d'amplitude oblivieuse peut augmenter la probabilité de succès d'une multiplication approximative d'encodages en blocs ε.
L'article fournit des procédures efficaces pour réduire les coûts supplémentaires des ancillae dans les encodages en bloc, permettant des algorithmes quantiques plus efficaces. Il met également en lumière les connexions entre les algorithmes quantiques et les algorithmes de sketched classiques, suggérant un potentiel pour des améliorations supplémentaires.