New quantum algorithms may improve the processing of data

Scientists from the Faculty of Physics of the University of Warsaw, in collaboration with the University of Oxford and NIST (National Institute of Standards and Technology), have shown that quantum interference enables processing of large sets of data faster and more accurately than standard methods. 

Contemporary science, medicine, engineering and information technology demand efficient processing of data:  images, sound and radio signals, as well as information coming from different sensors and cameras. Since the 1970s, this has been achieved with 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 too slow for many demanding applications.

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 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.

Mathematics describes many transforms. One of them is a Kravchuk transform. It is very similar to the FFT, as it allows processing of discrete 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, gestures, sign language, people and faces. Kravchuk 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.

The new paper published on Science Advances shows that the simplest quantum gate, which interferes between two quantum states, essentially computes the Kravchuk transform. Such a gate could be an 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 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.

The results will find applications in the development of new quantum technologies and quantum algorithms. The range of uses go beyond quantum photonics, since a similar quantum interference can be observed in many different quantum systems. 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.


Source: University of Warsaw

Read more Innovation Stories