Why This Article?
The way we write software is driven by advances in computing architecture & technology. As computing technology progresses, developers are geared up from writing assembly code to higher level C/C++ code, to massively parallel algorithms, to very large scale distributed SETI like software. One of the next generation technologies is Quantum Computing. Researched since 1960s, Quantum Computers have made their debut in Cryptography and Communications Servers.
Quantum computers have unique working principles, and bring about completely new algorithms that run on Quantum Turing Machines. Many of our today's developer community may actually get to write software for quantum computers. So thought, I would share my learning with the CodeProject community and ignite some interest in Quantum Computing.
Sorry, no source code as of now. Don't have quantum hardware & compiler at home yet :).
Contents
Computing: A Different Perspective
Imagine that we are writing a C++ program to simulate a trajectory of a metal ball thrown by hand. Our software takes the height, velocity, and mass as input, and using gravity and some equations, it computes the distance traveled as the output. Now, all the complicated fancy stuff that we just wrote in our source code actually "comes naturally" to Nature. So we could "just throw a ball" of a given mass at a given height and velocity, and "measure" where it hits the ground - Nature would "compute" the distance traveled for us. Interesting, isn't it? And Nature has been doing this since a pretty long time.
So why not take Nature's advantage in computing? This is exactly what physicists thought, and as an alternative approach to today's transistor & flip-flop based computers, they have devised newer mechanisms to "do computation" using physical systems.
Let's understand a physical system computer by example.
Square Computing Machine
Figure 1 shows a ball on a slope. Galileo performed this experiment in the 17th century. He measured the distance by which the ball falls down, with respect to time. The results at t= 1, 2, 3 units the distance fallen, were 1, 4, 9 times the distance fallen in unit time.
Figure 1. Square Computing Machine.
Note: Later, Newton demonstrated with the Laws of Motion that the governing equation is: Distance Fallen = u*t - 0.5*g*t2 u = 0, when the ball starts from rest.
Now, let's consider ourselves to be the operator of this system. So, users can tell us a number, we can roll a ball, and tell them the square of that number. This is how physical systems do "computation".
Let's understand how a physical system compares with a classical computer.
Classical Computer vs. Physical System
Figure 2 compares these two entities.
Figure 2. Classical Computer vs. Physical System.
A classical computer takes some input, applies a set of rules, and gives an output, and thus performs a computation. A physical system, in comparison, has an initial state, it follows the Laws of Motion (Physics), and it results in a final state of the system through some motion or physical action. Any final state of the system contains information about the system's initial state and what has happened to it since then. And since the motion of any object is governed by definite laws, it can be regarded as information processing. Hence, reaching the final state from an initial state is Information Processing.
Now, we have a different perspective of looking at computations. Let's get into understanding the Quantum Computing terminology.
Qubit
Before we define some terms, here is a brief background and apparatus.
Photons (light particles) are the elementary functional units of Quantum Computers. Photons are governed by the Laws of Quantum Mechanics. Photons and their behavior within a quantum computer are modeled by the Multiverse Theory. Hugh Everett proposed the Multiverse Theory in 1957. Classical physics that explains day-to-day life objects in real world is an approximation of the Multiverse theory. Classical computations are also known as Turing Computations.
An apparatus is shown in Figure 3. A beam splitter splits the incident photon into two parts. Each part is known as an Unsharp photon. The beam splitter can also combine unsharp photons into a sharp photon. The mirror reflects the photon with same "sharpness" - so if an unsharp photon strikes a mirror, the reflected photon is also unsharp, and the same is true for a sharp photon.
Figure 3. Photon Beam Splitter & Mirror.
The output is detected by another interesting apparatus called as a Photon Detector. It gives a high voltage if the photon is incident upon it, otherwise, it outputs a low voltage. The photon detector is a destructive way of measuring the outcome of quantum experiments, but nonetheless very useful to start with.
On a lighter note, Neils Bohr (Nobel laureate) once said, "Anybody who has not been shocked by Quantum theory, has not understood it!" :)
Qubit
A Qubit is a Quantum bit. A Qubit can be as simple as a single photon. A Qubit is a quantum system that is governed by the laws of quantum mechanics. As with flip-flop based classical bits, we can perform four fundamental operations on a Qubit.
- Set a Qubit.
- Reset a Qubit.
- Toggle a Qubit.
- A NULL operation (do nothing).
Qubits have a definite algebra of operations. This algebra is called the static constitution of a Qubit. The dynamic constitution of a system is the laws of motion.
Quantum Observable
A Quantum Observable is an entity that can be observed in a quantum system. Its equivalents in classical real world are length, angle, temperature, etc. A Quantum Observable is, however, much more than just a number. It is what we observe in one universe, and all of its counterparts in multiverse. A Quantum Observable contains information about the structure of a multiversal object.
Qubit is a minimal physical system in which all observables either can be Boolean or multiples of Unit Observables.
There are some very unique operations applicable to a Qubit. These operations can not be performed on classical bits.
Let's learn one of such unique operations.
A Qubit Operation Example
Figure 4 shows a quantum computing setup. Two beam splitters, B1 and B2, are in one plane. The mirrors, M1 and M2, are opposite to each other. There are two Photon Detectors - one on the top and the other on the right side. A photon is incident from the left side.
Figure 4. A Qubit Operation Example.
Quantum Observable (Q)
- Q is 1 if the photon moves in the screen X direction, i.e., left to right.
- Q is 0 if the photon moves in the screen Y direction, i.e., bottom to top.
Analysis of the Experiment
- The photon is incident on B1 from left to right. This is a Beam operation B. Q is 1.
- B1 splits the photon into two unsharp photons, P1 and P2.b
- Unsharp P1 is incident on mirror M1, and Unsharp P2 is incident on mirror M2.
- M1 is changing the P1 direction from 1 to 0. And M2 is changing the P2 direction from 0 to 1. This is a NOT operation.
- B2 joins P1 and P2 into a sharp photon.
- Experiments show that the right side photon detector always fires up - indicating that the outcome is a photon moving in the right direction. This can also be proved using Quantum Algebra, Hermitian matrices, and the expectation value functions - skipped for simplicity. Remember Bohr :)? This is also a Beam operation B. Q is 1.
- Observe that the quantum observable Q has remained unchanged.
For the above experiment, we can write a quantum operation as: B�NOT�B = I (read as B followed by NOT, followed by B, results in I). I is the identity observable (similar to 1 in classical algebra). I indicates unchanged.
Observe that B�NOT�B does not have any equivalent in classical computers. There is no operation in classical computers which, when performed before and after a negation, produces unchanged results.
Figure 5. A Unique Quantum Operation.
Also note that another conclusion of the experiment is pretty weird:
Figure 6. Square Root of NOT.
This square root of NOT is also an interesting operation that finds many useful applications in the quantum computing theory - deserves another article! :)
At this point, it is enough even if you appreciate the idea that quantum computing is pretty different, and that it has systematically built rules of computing. Classical computers are just one approximation of Quantum Computers.
Applications of Quantum Computing
Quantum computing will not help us in doing a+b, or in implementing MFC/C++ applications. Researchers are working to figure out computational problems for which quantum computers will provide a significant speedup.
- There is some evidence that even for a quantum computer, NP-hard problems would remain difficult; these include the travaling salesman problem, or many other optimization problems.
- An exponential speedup in computation time will be possible for some problems which are not NP-hard, but not known to be solvable in polynomial time on a classical computer. The most important one is the Shor's algorithm: factoring a 100 digit number. A classical computer would take 1024 years, and a quantum computer can do it in 20 minutes! This is a big deal if you realize that Shor's (and similar such) algorithm(s) are a key to robust cryptography applications.
- Finger printing for data security & search applications: just 40 Qubits can fingerprint a 1000 page novel.
- Quantum communications and high speed, secure networks.
In addition, there are some really futuristic applications such as a "Google" for molecules - Paul Benioff has done some fundamental research on such quantum robots.
Certainly, the possibilities are endless. The future will be far more exciting than what we have possibly imagined!
Resources
Good references on Quantum Computing can be found at the places below:
Credits
Christoph D�rr provided the exact details of computational problems that quantum computers can solve. Thanks Christoph.
Your comments, suggestions, are all welcome! Either drop me a line Suchit.Tiwari@Ge.com, or post a comment here. I would be more than happy to get in touch.