Quantum existence testing gives extreme solutions to increase network speed

Using a novel quantum computing algorithm, scientists have simplified the process for finding extreme values in a database compared with classical and earlier quantum computing methods. With its reduced time and minimal error probability, this quantum process could significantly increase the speed of computing in global and mobile networks.

Sándor Imre, an engineer at the Budapest University of Technology, calls this new computing process “quantum existence testing,” which is a special case of quantum counting. The quantum existence testing algorithm searches unsorted databases to find extreme values, attesting to the intriguing powers of the quantum mechanical effects of parallel processing.

Imre’s method combines elements from classical computing as well as the latest research in quantum computing. In today’s classical computers, a binary search algorithm searches for values in a structured database, although this method’s linear process can take long periods of time, especially with very large databases.

“While classical registers contain only one number from a large set, quantum registers are able to handle the entire large set of numbers at the same time,” Imre explained to PhysOrg.com. “Quantum computing is much faster because any operation on a quantum register will perform a certain function evaluation on all the numbers stored in that register. Then, using quantum parallelism, one can compare many possible phase values to a reference value in a single step.”

The first quantum searching algorithm, introduced in the mid-‘90s by Lov Grover, takes advantage of parallel processing to search much more quickly than with a classical algorithm. (The number of calculations in Grover’s algorithm is equal to the square root of the calculations in a classical algorithm.) Imre’s new quantum existence testing is a special case of Shor’s phase estimation algorithm applied on Grover’s circuit, as it searches not for specific values, but values with special characteristics.

“Grover’s algorithm is able to find a copy of a reference element in an unsorted database; however it cannot deal with relations, i.e. greater, smaller, etc,” Imre explained. “Quantum existence testing decides whether any of the elements in the database is smaller (or larger) than a reference value. Classically, to make this decision efficiently, one has to sort the database in advance and keep this sorted status continuously. But by combining quantum existence testing with classical logarithmic searching, we can achieve efficient extreme value searching in an unsorted data base.”

Finding extreme values is not only important for computer scientists searching large databases, but also for everyday applications. For example, global infocom networks use the shortest path (i.e. minimum) to transfer information. Likewise, mobile networks requiring optimal signal detection need to find the largest probability density (i.e. maximum) among 10³⁰ (or a thousand billion billion billion) choices or more, Imre explained.

“Many problems emerging in telecom systems can be regarded as searching in a virtual data base or function,” he said. “For example, to find an optimal route between two end-users located on different continents is nothing other than searching for the best solutions (an extreme value). Or detection in a 3G mobile terminal means that a received radio signal should be compared to all possible sent signals to decide which one has been really sent.”

At its basic level, Imre’s quantum existence testing algorithm consists of a recursive five-step code. The process begins with splitting the searching region into two subregions, and then checking for higher/lower values in that region. Depending on the answer, the code repeats with either the lower or upper subregion.

This algorithm, like the others, is probabilistic. In practical use, it would be programmed to run through a fixed number of steps, the number of which would scale with the error probability. The greatest advantage of the algorithm, as Imre explains, is that it decreases the computational complexity of the search. In other words, the algorithm requires fewer repetitions to produce the same results compared with other methods, translating to faster networks with stronger signals.

“Compared to classical solutions, the improvement with quantum existence testing is about the square root of N in the case of a database N entry of length,” Imre explained. “For example, if you are able to classically find an extreme value in a database containing 1000 entries in 1 second, then the quantum alternative can handle 1000 such databases during the same time, or a database with 1 million entries.”

The question that remains, however, is when quantum computers might be built. Imre noted that there are currently some promising manufacturers that predict quantum computers within a couple years.

“It depends on many things,” he said. “There are many ways to build quantum computers theoretically. The question is how scalable is the given solution? I mean, to build a few-qbit computer is more or less easy, but a 1000-plus-qbit quantum PC proves to be a really hard job. However, there are some quantum-based communication solutions (for example, key distribution) that are already on the market.”

Citation: Imre, Sándor. “Quantum Existence Testing and its Application for Finding Extreme Values in Unsorted Databases.” IEEE Transactions on Computers. To be published.

Copyright 2007 PhysOrg.com.
All rights reserved. This material may not be published, broadcast, rewritten or redistributed in whole or part without the express written permission of PhysOrg.com.

Related stories:

In quantum channels, zero plus zero can equal non-zero
(PhysOrg.com) -- Physicists have discovered a strange characteristic of quantum communication channels. If two quantum channels each have a transmission capacity of zero, they may still have a nonzero capacity when used together. This effect, which has no classical counterpart, reveals a new complexity in the fundamental nature of quantum communication.
MIT quantum discovery could lead to better detectors
(PhysOrg.com) -- A bizarre but well-established aspect of quantum physics could open up a new era of electronic detectors and imaging systems that would be far more efficient than any now in existence, according to new insights by a leader in the field that will appear in the journal Science.
Michigan integral to world's largest physics experiment
After 20 years of construction, a machine that could either verify or nullify the prevailing theory of particle physics is about to begin its mission. CERN's epic Large Hadron Collider (LHC) project currently involves 25 University of Michigan physicists and students. More than 100 U-M researchers have been involved in the project over the years. CERN is the European Organization for Nuclear Research, located in Geneva, Switzerland.
Electrons discover their individuality
(PhysOrg.com) -- Electrons have something in common with people: the more information they acquire about their setting, the more they become aware of their individuality and the more belonging to a group loses its importance. As a result, the coherent harmony that binds the electrons into a fixed relationship with their environment is lost. This is what scientists at the Fritz-Haber Institute of the Max-Planck Society discovered when, with the aid of X-rays, they catapulted electrons out of molecules consisting of two nitrogen atoms.
Physicists Rule Out the Production of Dangerous Black Holes at the LHC
(PhysOrg.com) -- On August 8, the world's largest particle accelerator, the Large Hadron Collider near Geneva, Switzerland, began the process of slowly throttling to full power. When its proton beams are circling at full speed and collisions begin, scientists from around the world will finally be able to start collecting data.
Scientists take the sharpest image ever made with light
(PhysOrg.com) -- A team of scientists from the Technische Universität Dresden (Germany) and the ESRF in Grenoble (France) has produced the image of an object at the highest resolution ever achieved with X-ray light. A 100-nanometre gold particle fixed on a substrate was reconstructed with 5 nanometre resolution. Contrary to other techniques, X-ray imaging works also in real-life environments like chemical processing or in the presence of high magnetic fields. The team reports its findings in the newest issue of Phys. Rev. Lett. dated 5 September 2008 (published online 29 August 2008).
Entanglement without Classical Correlations
Quantum mechanics is full of counterintuitive concepts. The idea of entanglement – when two or more particles instantaneously exhibit dependent characteristics when measured, no matter how far apart they are – is one of them. Now, physicists have discovered another counterintuitive result that deals with the line between the quantum and classical worlds.
Viterbi Algorithm goes quantum
The Viterbi Algorithm, the elegant 41-year-old logical tool for rapidly eliminating dead end possibilities in data transmission, has a new application to go alongside its ubiquitous daily use in cell phone communications, bioinformatics, speech recognition and many other areas of information technology.

News discussion:

Ticker Symbols? in Technology news