Un Algorithme de Transformation de Fourier Quantique Plus Rapide
2025-01-27
Ronit Shah présente un algorithme amélioré pour la Transformation de Fourier Quantique (TFQ). Traditionnellement, la TFQ approximative nécessite Θ(n log n) portes, et la TFQ exacte nécessite Θ(n²) portes. Le nouvel algorithme, exploitant une nouvelle partition récursive des qubits, réduit le coût de la TFQ approximative à Θ(n(log log n)²) portes et de la TFQ exacte à Θ(n(log n)²) portes. Cette avancée promet des gains d'efficacité significatifs dans le calcul quantique.