Contemporary science, medicine, engineering and information technology demand efficient processing of data—still images, sound and radio signals, as well as information coming from different sensors and cameras. Since the 1970s, this has been achieved by means of the Fast Fourier Transform algorithm (FFT). The FFT makes it possible to efficiently compress and transmit data, store pictures, broadcast digital TV, and talk over a mobile phone. Without this algorithm, medical imaging systems based on magnetic resonance or ultrasound would not have been developed. However, it is still too slow for many demanding applications.
To meet this goal, scientists have been trying for years to harness quantum mechanics. This resulted in the development of a quantum counterpart of the FFT, the Quantum Fourier Transform (QFT), which can be realized with a quantum computer. As the quantum computer simultaneously processes all possible values (so-called “superpositions”) of input data, the number of operations decreases considerably.
Mathematics describes many transforms. One of them is a Kravchuk transform. It is very similar to the FFT, as it allows processing of discrete (e.g. digital) data, but uses Kravchuk functions to decompose the input sequence into the spectrum. At the end of the 1990s, the Kravchuk transform was “rediscovered” in computer science. It turned out to be excellent for image and sound processing. It allowed scientists to develop new and much more precise algorithms for the recognition of printed and handwritten text (including even the Chinese language), gestures, sign language, people, and faces. A dozen years ago, it was shown that this transform is ideal for processing low-quality, noisy and distorted data, and thus it could be used for computer vision in robotics and autonomous vehicles. There is no fast algorithm to compute this transform, but it turns out that quantum mechanics allows one to circumvent this limitation.
“Holy Grail” of computer science
In their article published in Science Advances, scientists from the University of Warsaw—Dr. Magdalena Stobinska and Dr. Adam Buraczewski, scientists from the University of Oxford, and NIST, have shown that the simplest quantum gate, which interferes between two quantum states, essentially computes the Kravchuk transform. Such a gate could be a well-known optical device—a beam splitter, which divides photons between two outputs. When two states of quantum light enter its input ports from two sides, they interfere. For example, two identical photons, which simultaneously enter this device, bunch into pairs and come out together by the same exit port. This is the well-known Hong-Ou-Mandel effect, which can also be extended to states made of many particles. By interfering “packets” consisting of many indistinguishable photons (indistinguishability is very important, as its absence destroys the quantum effect), which encode the information, one obtains a specialized quantum computer that computes the Kravchuk transform.
The experiment was performed in a quantum optical laboratory at the Department of Physics at the University of Oxford, where a special setup was built to produce multiphoton quantum states, so-called Fock states. This laboratory is equipped with TES (Transmission Edge Sensors), developed by NIST, which operate at near-absolute zero temperatures. These detectors possess a unique feature: they can actually count photons. This allows one to precisely read the quantum state leaving the beam splitter and thus, the result of the computation. Most importantly, such a computation of the quantum Kravchuk transform always takes the same time, regardless of the size of the input data set. It is the “Holy Grail” of computer science: an algorithm consisting of just one operation, implemented with a single gate. Of course, in order to obtain the result in practice, one needs to perform the experiment several hundred times to get the statistics. This is how every quantum computer works. However, it does not take long, because the laser produces dozens of millions of multiphoton “packets” per second.