Faster multiplication can now speed up the quantum Fourier transform

[Widget72]

A new result connects two areas of computer science in a surprising way. Quantum Zeitgeist reports on a paper by Chandrima Kayal of Université Paris Cité and CNRS, with Rajat Mittal, Manaswi Paraashar and Nitin Saurabh, showing that faster integer multiplication leads directly to faster quantum Fourier transforms

The quantum Fourier transform, or QFT, sits at the heart of Shor's factoring algorithm, discrete logarithms and phase estimation. Making it cheaper to run helps many of the most important quantum algorithms at once

The paper sets a new upper bound for an exact QFT circuit of order q log q gates. The previous best, from Cleve and Watrous in 2000, had extra logarithmic factors, so this is a meaningful improvement on a result that stood for over 25 years

Any faster circuit for multiplying integers now carries over to a faster QFT. The article links this to an unverified claim about a better multiplication algorithm, which would push things further still if it holds up

There are caveats. The construction is non uniform, the multiplication claim is unverified, and the article itself is inconsistent about some exponents, so readers should check the arXiv paper for the exact details. Even so, theory results like this quietly lower the cost of future quantum computers

How excited should we be about theoretical speed ups like this? And which part of Shor's algorithm do you think still needs the biggest improvement?

Multiplying Integers Now Speeds Up Quantum Fourier Transformsquantumzeitgeist.com