Quantum interference enables constant-time quantum information processing We live in the age of information and thus efficient data processing is crucial. It is especially important in science, medicine, engineering and information technology that demand fast processing of images, sound, radio signal and records coming from various probes and cameras. Since 1970s, this is achieved by means of the Fast Fourier Transform (FFT) algorithm. However, the Fast Fourier Transform (FFT) becomes a bottleneck in processing of large amounts of data. Recently, another discrete transform, the Kravchuk Transform, has been “rediscovered” in computer science. It is especially suited for processing of noisy data data in computer vision and artificial intelligence. For example, it is well suited for image processing, voice recognition, face recognition and medical diagnostics. However, the main obstacle against its wider adoption is lack of a fast computational algorithm. Our innovation is to show that the Quantum Kravchuk Transform can be achieved with quantum computers. Whilst the FFT requires numerous iterations of the algorithm, the Quantum Kravchuk Transform
can be computed in a single step just by one quantum gate, regardless the length of the input data. The gate can be implemented e.g. by a beam splitter – the simplest photonic interferometer. We need two beams of quantum light that carries the information to be processed to enter from two sides and measure the light behind the beam splitter. In the case of a standard 10-megapixel digital camera image, this means that Quantum Kravchuk Transform can be computed millions times faster than the FFT. This is a “Holy Grail” of computer science that may boost early medical diagnostics, artificial intelligence and computer vision. It may also play an important role in the “second quantum revolution”. This work is a result of collaboration between the University of Warsaw and the University of Oxford.