Ein schnellerer Quanten-Fourier-Transformationsalgorithmus

Ronit Shah präsentiert einen verbesserten Algorithmus für die Quanten-Fourier-Transformation (QFT). Traditionell benötigt die approximative QFT Θ(n log n) Gatter, und die exakte QFT Θ(n²) Gatter. Der neue Algorithmus, der eine neuartige rekursive Partitionierung von Qubits nutzt, reduziert die Kosten der approximativen QFT auf Θ(n(log log n)²) Gatter und der exakten QFT auf Θ(n(log n)²) Gatter. Dieser Durchbruch verspricht erhebliche Effizienzsteigerungen im Quantencomputing.