Quantum-Inspired World of Computers: Science or Fiction?

Omer D. Ikramoglu

Mar 1, 2010

When we draw even a simple line using a computer program, we usually ignore what our computer actually does in the background. It converts videos, images or texts into bits, the smallest building blocks of information, before doing any manipulation. In other words, a digital computer is unable to process this information, unless it is read in its own language, which is represented by two symbols only, the 0 and 1 bits. For example, the character “a” translates into this binary language as the “01100001” bit string. Why such a simple alphabet? Because, this is very convenient from the electronic aspect of your computer. These bits can be simply represented for example, as an electrical level on the circuitry in most computing devices, and best of all they can be programmed to accomplish certain computational tasks.

How about quantum computers? Quantum computers make use of a quantum mechanical phenomenon, so-called quantum superposition (being in different states simultaneously). Classically, voltage across a circuit element can be either positive or negative when measured by a voltmeter, but not simultaneously negative and positive. Could it somehow be possible to be in both states simultaneously?

Quantum superposition

For electrical circuits, the answer is obviously no. In microscopic scales of single atoms, or photons (i.e., single quantized packets that constitutes the light beam), however, the answer is yes. Consider an optical component, for instance, that splits an incoming light beam into two beams of equal intensity. In optics, such a device is called a 50/50-beam splitter. You can ask what happens when a single photon is sent to such a beam splitter. Since a single photon cannot be split in this simple experiment, you might expect that it would either be transmitted or reflected with equal probability . Experiments, however, show that this is not actually true in the single photon level. The single photon is indeed simultaneously reflected and transmitted.

Once microscopic quantum superposition is brought into our macroscopic world, we can imagine many interesting phenomena. Simultaneously occupying many different places and being dead and alive at the same time are only two of them. Of course such technology, especially applied to humans is highly science fiction, given current experimental and theoretical challenges. Nevertheless, quantum superposition has a strikingly interesting similarity with the spiritual states already achievable by saints, such that they can be available in more than one place at a given time or become dead and alive, in the sense that they live both in the future and in the past.

It is not known exactly why quantum superposition exists, but what we know is that it is a necessary ingredient for our complex universe to perform its vital functions in a finite amount of time. Quantum superposition principle reflects the great wisdom and power of the Omnipotent. Similar to the single photon example above, with this principle, God gives the underlying particles of the universe an immense power to achieve many tasks simultaneously. Otherwise, regarding the finite age of the universe (about 15 billion years), our physical universe and the events taking place all around us would not come into existence. The Quantum superposition principle has also inspired researchers to build unprecedentedly fast computers to solve the problems that are intractable with any classical computing method. In this article, we introduce this new strategy to computing.

Quantum computing with superposition

Having provided some background about the quantum superposition, we ask the question “How could we exploit quantum superposition for fast computing?” Below we will give a glimpse of that power. Consider a three-bit register. It can only store one out of eight numbers in the set, {0, 1, 2, 3, 4, 5, 6, 7}, in a given moment of time. For example, number 5 is stored in a three-bit register as “101.” Now suppose that these three bits are replaced by their quantum cousins, so-called qubits (short for quantum bit). You can imagine, for example, a quantum register consisting of three rubidium (Rb) atoms. These individual atoms can be prepared in the 0 and 1 logical states simultaneously by shining a laser beam for a certain amount of time. Then it is possible for three atoms combined to be prepared in a superposition of eight numbers, which is impossible classically. In other words all those eight guys physically exist in the same room, although it doesn’t allow more than one guy to fit classically. If we want to make operations on all of these numbers, we don’t need to perform serially; instead, we can achieve that in only one computational step on a single hardware. Thus, quantum superposition leads to a massive parallelism, which renders the computational complexity (i.e., a measure of how efficiently a given problem could be solved) highly reduced for various difficult problems in computer science.

For example, let’s consider RSA, a well-known algorithm (i.e., a set of instructions to solve a problem on a computer) for secure communication that was invented by Rivest, Shamir, and Adelman, hence the name, in 1977 at MIT. It is widely used in electronic commerce protocols. The details of RSA are out of scope in this article (See the FAQ section of the RSA Laboratories’ web site in Ref. [1] for a brief introduction to RSA). Here, we only want to mention its vulnerability to quantum computers if they were to exist. The security of the RSA cryptosystem relies on the difficulty of factoring large numbers, which is intractable with classical computers. Factorization for small numbers, say 15, is quite simple. When the number of digits increase up to a few 100s, for example, enormous computational resource is required. RSA Laboratories publish the RSA challenge numbers (see Ref. [2] for the list of challenge numbers and the prize) on their web site to test the security of their algorithm at various key lengths. The largest integer, RSA-640, which has 193 decimal digits (640 bits), was factorized recently by F. Bahr, et al. The next challenge number in turn is RSA-704, and the prize is $30,000. Imagine factorizing a 1000-digit number. You would probably be a considerably rich person in just a few minutes, if you had a moderate quantum computer and the RSA Laboratories kept feeding you with new challenge numbers, because the factorization of such a large number with current computational resources takes forever, perhaps even more than the estimated age of the universe. Of course, the RSA Laboratories will not let you be very rich, by simply quitting posting new challenge numbers. They would be interested in your quantum computer, though.

How does the quantum computer crack the world’s most secure cryptosystems with little effort? One can construct new algorithms for quantum computers based on above described principle of superposition. These algorithms can take the outcome of previous calculations and input them as a superposition to the next stage of the instructions, which results in a highly efficient form of computing (please consult Ref [3] to have for a simple explanation of quantum superposition for fast computation). In 1994, Peter Shor from AT&T’s Bell Labs in New Jersey just did that. He developed the world’s first quantum algorithm, which efficiently performs factorization. In 1996, Lov Grover also at Bell Labs invented the unstructured database (i.e., a disordered list such as a list of city names not in alphabetical order) search algorithm for quantum computers, so-called Grover’s algorithm.

Suppose that there is a basket with ten balls in it. You are now asked to find a specific one with your eyes closed, say red. It is known, however, beforehand that there is only one red ball in the basket. All you, or your smart digital friend, can do is just pick one randomly and see if it is red. If you are lucky enough, the first ball you pick might be red. In the worst case, however, you will be successful at your last choice. So, classically you have to repeat the process on average at half times the number of balls. If you made a quantum friend rather than classical, however, your life would be smoother. You would be able to find and manage your stuff easily, no matter how messy you are. Quantum computers speed up such unsorted database searches quadratically. You can find, say your favorite socks, in a number of trials that is about the square root of the total number of your stuff. You may think that you don’t have that much stuff. But consider identifying a specific element in a considerably large pool of unsorted data. As the number of elements in the set increases, it quickly becomes intractable to find what exactly you are looking for. In that case the significance of quadratic boost cannot be denied.

Motivated by the above mentioned factorization and unsorted database search algorithms, the power of quantum computing has inspired great attention, since their invention, among many disciplines including physicists, computer scientists, mathematicians, engineers, and material scientists.

Quantum computer today

Despite promising developments in theory, progress in the physical realization of quantum circuits, algorithms, and communication systems have been extremely challenging to date. There are many approaches for quantum information processing. Major model physical systems include nuclear spins, ions, neutral atoms, solid state nanostructures, superconductors, and optical circuits. In optics, for example, the qubit can be represented by the polarization (i.e., direction of oscillation of electric field) state of a single photon. So that the instructions described by the algorithm could be implemented by manipulating the polarization states of single photons. Unfortunately, all the models for quantum computing have their own drawbacks besides their advantages.

Given the trends, nobody knows whether or not a sufficiently scalable (i.e., large enough to harvest its potential power) quantum computer would be available in the decades to come. Nonetheless, D-Wave Systems, Inc., The Quantum Computing Company, was eager enough to unveil the “world’s first commercially viable quantum computer” (see Figure 1, and Ref [4] for the story.). D-Waves’ 16-qubit quantum computer makes use of superconducting element niobium, which operates at an extremely low temperature. It can search for molecular structures that match a target molecule, create a complicated seating plan, and fill in Sudoku puzzles. Although the device is very slow compared to an inexpensive PC, D-Wave intends to develop a 1000-qubit quantum computer.* The goal is to scale the quantum computer to about 10 thousand qubits to solve the most challenging problems outright, which are simply intractable with classical computers. The researchers, however, are not very optimistic. Prof. Lloyd of Massachusetts of Institute of Technology, a pioneering scientist in superconducting approach for quantum computing that underlies the D-Wave’s quantum computer, says “It’s too good to be true.”

Once quantum computers of reasonable power are built, the world will be unimaginably exciting and perhaps scary too. When the first commercial computer, Universal Atomic Computer I (UNIVAC I) (see Figure 2), was shipped to the United States Air Force in 1952, nobody was indeed aware of what this fat guy would lead to in our social, economical, political, and psychological life. Its descendants, however, are now inevitable parts of our lives. They are helping us in many aspects of daily life. Controlling machines, sending electronic mail, scheduling our plane tickets, communicating with our best friends, playing games, making our payments are only some of them.

In this article we only sketched the quantum superposition principle as an important ingredient for quantum computation. This is certainly not the whole story. “Entanglement” [6], for example, is another complementary resource for quantum computing and communications, as well as quantum mechanics to test its foundations.

Contrary to its classical counterparts, the power of quantum computers indeed comes directly from our granted capability of tailoring and mimicking the amazing design hidden in the microscopic world of atoms, photons or other quantum particles. Quantum computers sooner or later will bring the most science-fiction into reality. They will play a significant role especially in the development of ultra-intelligent machines and robots superior to classical ones, and communication systems whose ultimate security is guarantied by the nature’s architecture which was lay down by God. Quantum computers will reveal to us the deepest secrets of our Creator embedded in our universe, which cannot be explored using conventional computers. That day, the future will only be lacked by our limited imagination.

Acknowledgment

This article was produced in MERGEOUS [7], an online article and project development service for authors and publishers dedicated to the advancement of technologies in the merging realm of science and religion.

Omer D. Ikramoglu is a freelance writer in optics and quantum physics.

References

1. RSA Laboratories, http://www.rsa.com/rsalabs/

2. RSA Challenge Numbers, http://www.rsa.com/rsalabs/node.asp?id=2093

3. A short introduction to quantum computation by A. Barenco, A.Ekert, A. Sanpera and C.Machiavello from La Recherche, November 1996. http://cam.qubit.org/articles/intros/comp.php

4. J. R. Minkel, “First “Commercial” Quantum Computer Solves Sudoku Puzzles”, Scientific American, Feb 13 (2007).

5. UNIVAC I, http://en.wikipedia.org/wiki/UNIVAC_I

6. S. Candaroglu, “Quantum Entanglement: Illusion or Reality?” Fountain, Issue 61 (January-February 2008).

7. http://www.mergeous.com/

* At the time of writing D-Wave Systems had only 16-qubit quantum chip and they were intending to develop a 1000-qubit quantum computer by the end of 2008. Although they couldn’t meet their goal, they now have a design of a 128-qubit most powerful ever quantum chip which awaits the tests (see http://www.dwavesys.com for up to date information).