Scientists from the Faculty of Physics, University of Warsaw, in collaboration with the University of Oxford and the NIST agency, have shown that quantum interference enables processing of large sets of data faster and more accurately than with standard methods. Their studies may boost applications of quantum technologies in e.g. artificial intelligence, robotics and medical diagnostics. The results of this work have been published in the Science Advances journal.
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 processes simultaneously all possible values (so-called “superpositions”) of input data, the number of operations decreases considerably.
In spite of the rapid development of quantum computing, there is a relative stagnation in the field of quantum algorithms. Now scientists have shown that this result can be improved, and in a rather surprising way.
Kravchuk transform
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 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 Chinese language), gestures, sign language, people, and faces. Already 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. 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. habil. Magdalena Stobinska and Dr. Adam Buraczewski, the University of Oxford and the NIST agency have showed that the simplest quantum gate, which interferes 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 premises of the Department of Physics of the University of Oxford, where a special setup was built to produce multiphoton quantum states, so-called Fock states. This laboratory is equipped with TESs (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.
The result obtained by scientists from Poland, the United Kingdom and the United States, will find applications in the development of new quantum technologies and quantum algorithms. Its range of uses go beyond quantum photonics, since a similar quantum interference can be observed in many different quantum systems. The University of Warsaw applied for an international patent for this innovation. The scientists hope that the Kravchuk transform will soon find use in quantum computation, where it will become a component of new algorithms, especially in hybrid quantum-classical computers that merge quantum circuits with “normal” digital layouts.
