Pages

1 May 2018

Quantum Computing explained!


At sub atomic levels every thing that we know about classical physics breaks, not just by a small margin but at massive scale. Welcome to the world of quantum mechanics and be ready to be amazed. Before we start talking about Quantum Computing, we must have a good grip of what Quantum Mechanics is, what is special about it, and how quantum-mechanical phenomenons help us perform advanced computations. Initial researches on Quantum Mechanics can be dated back to 17th century, when scientists proposed wave theory of light (Light can exhibit both a wave theory, and a particle theory at the same time). The existence of a light quantum was proposed by Max Planck in 1900, which was further enhanced by Albert Einstein stating that that light is composed of tiny particles called photons, and each photon has energy. In general, quantum mechanics deals with the behaviour of matter and its interactions with energy on the scale of atoms and subatomic particles.

With the advent in quantum mechanics, Newtonian Mechanics (or Classical Mechanics) begin to subside at fundamental levels. Some specific nature of light itself was unable to be explained by classical physics, the Hydrogen spectral series, for instance, when hydrogen gas is heated in a tube and the emitted light is observed, it can be noticed that the emission spectrum of atomic hydrogen contains number of spectral series rather than having a continuous emission of light (or electromagnetic radiation), yes, it is more like bands of colours and different from the expectation of classical physics. Danish physicist Niels Bohr came up with an explanation for this, the Bohr model, in which he narrates atom as a small, positively charged nucleus surrounded by electrons that travel in circular orbits around the nucleus — similar to structure of the Solar System. Each orbit corresponds to a different energy level. Changes of energy, such as the transition of an electron from one orbit to another around the nucleus of an atom, is done in discrete quanta. The term quantum leap refers to the abrupt movement from one discrete energy level to another, with no smooth transition. There is no “inbetween’’.

Quantum leap was special, because the movement of electron was not progressive, it just disappeared from one orbit and appear in the next orbit with no intermediate state and emitted(or absorbed) a specific amount of energy. Well this makes things interesting. Bhor explained that amount of energy at this level can not be further sub divided and it is called quanta, a specific minimum quantity of energy. First insights of this kind of energy levels where provided by a physicist named Planck, so we call it as Planck constant. So, in general, the energy of electron in an atom is quantized.

This is just the beginning, where the predictability of classical physics was over turned by the potentiality of quantum physics. And this was very concerning to many physicists of that time. Why does an electron follow quantized orbits and not have intermediate states?

Thesis of Louis de Broglie in 1923 answered this question. He explained that matter can exhibit both particle and wave nature same as that of light. And the wave nature of electrons insist them to obtain certain wave lengths which are allowed for them to fit in an orbit. But with in that orbit electron can exists at all places, not just at a particular spot, due to the wave nature of electron. This was fundamentally different to classical physics but was experimentally proven. Since matter with higher mass, like us humans, have high momentum and the wave length of such matters will be considerably smaller as mass is inversely proportional to De Broglie Wavelength. So the effect of de Broglie explanation diminishes at macroscopic levels.

Double-slit experiment, conducted by Davisson and Germer in 1927, proved that light and matter can exhibit properties of both classically defined waves and particles. A similar but simpler form of the double-slit experiment was performed by Thomas Young in 1801. Light when passed through two slits in a barrier can from interference pattern in the screen on the other side.(Light going through the double slit does not form a double band pattern on the screen) The interesting part of these experiments was even if we pass electron/photon one at a time the interference pattern builds ups on the screen/detector. How the hell is this possible? This means that if we send a single electron from a source through a double slit ( and we don’t know through which slit the electron passes) the place on the screen (or detector) the electron appears on the other side is probabilistic ( means it can be any where in an interference pattern). And if we send considerable amount of electrons it will form the interference pattern on the other side. This means that each single electron must exhibit the property of a wave, other wise it will not be interfering with any other thing, the single electron wave at one side of the barrier will produce two waves at other side of double-slit barrier (just like a single water wave passed through two holes can form two waves on the other side) and these two waves interact with each other to form a interference pattern.

Erwin Schrodinger published an equation which describes moving electron as a wave which is spread across. The equation is also known as Schrodinger equation which helped him to win the Nobel Prize in Physics in 1933.

German physicist and mathematician Max Born formulated the Probability Density Function which describes all this as a possibility of finding electron as wave. This was after his studies about Bohr Model’s electron orbits, which helped to formulate the matrix mechanics representation of quantum mechanics along with Werner Heisenberg. Later a year Heisenberg proposed Heisenberg’s uncertainty principle which sates that the position and the velocity of a particle cannot both be measured exactly, at the same time, even in theory.

Werner Heisenberg along with Niels Bohr devised Copenhagen interpretation of quantum mechanics which states physical systems generally do not have definite properties prior to being measured and quantum mechanics can only predict the probabilities that measurements will produce certain results. The act of measuring will result in a Wave Function Collapse changing the probabilities into one possible value.

Albert Einstein responded

“God does not play dice with the universe”

Niels Bohr replied

“Stop telling God what to do with his dice.”

The whole thing of quantum physics was hard to digest even for the brightest mind of all times. But it was evident in the double-slit experiment, if we try to find out through which slit the electron passes by placing a measurement device at any of the slits the interference pattern disappears.

Its highly recommended to see this video :

So, it is meaningless to assign reality to the universe in the absence of observation. In the intervals between measurements quantum systems truly exists as a fuzzy mixture of all possible properties. This is Quantum superposition, the normal material universe has meaning only at the moment of measurement.

In case of our electron, superposition can be described as the possibility of electron being at different position at the same time. This can be also applied to spin (which is an intrinsic form of angular momentum) of electron, as per the uncertainty principle. Electron can spin in all directions until we measure its spin, up on measuring the spin will be either aligned to the direction of measurement or in the opposite direction. This is also termed as spin up or spin down.

Things are different in quantum system also difficult to grasp at first glance, in order to relax we may need to see a cat video. What about Schrodinger’s cat?

Lets watch this too..

In short, a cat in a closed box with something (say an explosive) that may or may not kill it, is in superposition, which means cat can be either alive or dead for the outside world. So until we open the box and observe the cat have half the probability of being dead and half the probability of being alive.

There is one more important implication to this experiment, that is what happens with in the closed box. If the cat feel the explosion then it will be dead, if it doesn’t feel explosion it will be alive. The state of cat is some how connected to that of explosive. In quantum world this is described as Quantum entanglement.

Quantum entanglement is the phenomenon by which more than one particle, generated together or closely interacted, can start a relationship and the quantum state of each particle cannot be described independently (if cat is dead, explosive exploded/ if explosive exploded cat is dead). Thus the particle cannot be described independently, they become a connected system and measuring one will affect the state of another. This property will be preserved even when they are separated by large distance too.

For instance, consider two electrons which are entangled, we will consider spin (position or momentum can be considered, we will take spin which is angular momentum) of electrons sums to zero when it is generated. Now we can separate these electron by any distance and measure them independently. If the first electron measures a spin up, then the other one will be always spin down and vise versa. And the effect of measurement happens instantly, which means faster than the speed of light.

The idea that entangled quantum particle exist in a state of probabilities, and will only losses the superposition state if one of the particle is measured, and the other particle will be affected instantaneously, even if separated by any distance drove many scientists of that time crazy. It even include Einstein, who refereed to it as “spooky action at a distance". He even came up with the EPR paradox, which says two particles interact to form deep relationships and information was encoded in some ‘hidden parameters’ about the possible states. Just like one electron says if some one measures me I will spin up and other says I will spin down. Other wise it will break theory of relativity by sending information faster than the speed of light.

Alain Aspect disproved EPR paradox in 1980, using the Bell test experimentbased on Bell’s theorem proposed by John Stewart Bell in 1964. Yes, quantum world is real and spooky actions do exist.

Now lets restart every thing with quantum computing in perspective… Lets do this again.

Quantum computing studies theoretical computation systems that make direct use of quantum-mechanical phenomena, such as superposition and entanglement, to perform operations on data.

In classical computer, we transforms any data to zeros and ones, so called bits.Actually to high voltage and low voltage for processing, then pass them through a series of gates called logic gates which can manipulate the data to figure out result. Logic gates like AND, OR, NOT, XOR, etc. can be arranged in different ways to process the bits and produce the output. It can do simple operation like addition to complex encryption. Logical gates are physically realised by using transistors, which now days depends on the properties of silicon semi-conductors to perform operation instead of using mechanical switches.

Sure classical computers are fast and efficient but they are not good at problems which involve exponential complexity like the Integer factorization. Especially the prime factorization when integers are further restricted to prime numbers (Semiprime). Basically, it is easy to find product of two large prime numbers but it take enormous amount of computation with classical computers to find the numbers that produced it given the product. In fact this complexity is the basis of many cryptosystems including RSA.

So how quantum computers tackle this problem?

In quantum computing, the basic computational unit is a Qubit which can represent information. A qubit have some similarities to normal bit such as it can be measured to either zero or one. But the power of qubit lies in its quantum mechanical properties like superposition and entanglement. A qubit can be in both zero state and one state at the same time. States of a qubit is represented using “ket 0” and “ket 1” notation its written as |0> and |1> and the basic measured state is similar to classical 0 and 1.

What exactly can be a qubit in a real quantum computer? Well it can be an electron with spin, a photon with polarisation, impurity spins, trapped ions, neutral atom, semiconducting circuits etc.

The super position of simple qubit can be represented using below Bloch sphere

It may seem bit complex but the main point that we need to keep in mind is that the single qubit at any time can be in a super position of |0> and |1>and it can be expressed as

where a and b are amplitude (proportional to probabilities) of qubit being measured to 0 and 1 respectively and a² + b² =1

So a qubit can be in super position of two states, and once it is measured it will return one of the two states based on the probabilities of each state. So measuring a qubit itself has an effect on the the system, so measurement of a qubit is similar to a gate which affect the state of the qubit.

If we consider more than one, say two, qubit things become more interesting, the basic state will be 00, 01, 10, 11 but the qubits can be in super position of all for states at the same time. So this should be represented as

In order to represent two qubits we need 4 probabilities/amplitude (a, b, c, d), if we have three qubits we will need 8. So if we have n qubits, we will need 2^n numbers to represent the the overall state of that quantum system. So with small increase in the number of qubits we will be able to generate systems which can represent enormous states and this is dissimilar to classical computers.

Even if the amount of information required to describe the super position grows exponentially with number of qubits we will not be able to access all this information because of the fundamental limits of quantum measurement. Spin of an electron in superposition can be in all directions but when we measure, it is in one direction either up or down. Also we will not be able to predict the out come, it is probabilistic based on the probability associated with state (Eg: half times up and half times down). That means in order to use full potential of quantum computer we need develop quantum algorithms which explore the existence of huge amount of information stored in super position of qubits and at the end of the computation, leave the system in one of the base states which we can detect with certainty.

In a quantum computer, it is possible to have two qubits with opposite values, but the value of individual qubits is unknown until we measure. This is possible because of quantum entanglement. Say we have two electron qubit which have zero state, then we put the first electron/qubit into superposition by applying a electromagnetic wave, with a certain frequency which is proportional to the energy difference between zero and one state. Now, when we try to adjust the second electron/qubit by applying electromagnetic wave of frequency which was required when first electron/qubitis in zero state, the first electron/qubit in super position will have an effect in the spin of second qubit and second one will also move to a superposition (not a stable state). So the state of these two qubits will be entangled and if we measure first one and get up-spin then the other will give down-spin and vice versa. This entanglement will be persevered at any long distance. Until we measure them the two qubits can only be considered as a single system with probable values. This is impossible in a classical computer, to have two bits with no value but the opposite values.

So the increase in the number of qubits will exponentially increase the number of possible entangled states. One key point to notice is that the quantum entanglement can be very fragile (Quantum decoherence) and any system that utilises this should have a very minimum external interference.

The building blocks of quantum circuits (model for quantum computation) is quantum logic gate. They are like logic gates of classical computing world but unlike many classical logic gates, quantum logic gates are reversible. This is because quantum mechanics require a quantum system to never lose information over time and it must always possible to reconstruct the past.

Can you think of any classic gates which will make to the quantum world?

AND gate will not make it since both 1 AND 0, 0 AND 1 gives output as 0.

Yes, NOT can make it to quantum world

NOT 0 = 1, NOT 1 =0

This is reversible if output is zero then input is one, if output is one, input is zero. This gate is known by the name Pauli-X gate in the quantum world. It maps |0> to|1> and |1> to|0>

Hadamard gate also acts on a single qubit and creates a superposition.

The swap gate swaps two qubits. That is |10> to|01> and so on.

Controlled gates act on 2 or more qubits, where one or more qubits act as a control for some operation. For example, the controlled NOT gate (or CNOT) acts on 2 qubits, and performs the NOT operation on the second qubit only when the first qubit is|1>, and otherwise leaves it unchanged.

CNOT Gate:


In case of CNOT gate also, we can see that each output is distinct and there is no ambiguity and states can be restored.

In an electron spin based quantum computer the CNOT gate can be implemented easily. Since the control bit and target bit are close-together and control bits spin have some effect on target bit, and it can decide whether we can flip the target with certain electromagnetic wave.

CNOT gate can also be used to produced entangled state of Control and Target. If we apply Hadamard gate to control first and then apply CNOT gate, both control and target will be in superposition and entangled together. The CNOT gate is generally used in quantum computing to generate entangled states.

CNOT together with arbitrary qubit rotation can implement any logic functions in quantum computers.

There are other quantum gates also available that you can find here.

Measurement of a qubit can also change the state of the system and functions very similar to gates but it is not an actual quantum gate.

For a quantum computer to work we should be able to change properties of arbitrary qubits and we should be able to run quantum logic gates on one or more qubits by making interaction between them.

Now we need to make use of all these logic to create some useful algorithms. There is no point in using a quantum computer to perform computationally simple operations, since classical computers can do this at a cheaper rate. Because of the fact that the infrastructure itself is complex and the quantum computers can handle large number of states at the same time, the effective use of quantum computers are confined to specific areas like finding the prime factors, search large amount of data, etc. which are computationally intensive.

Quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer and this will involve quantum properties like, superposition and entanglement. There are different algorithms already available and more are in the pipeline.

Shor’s algorithm for integer factorisation is one of the most famous one because of its implication in cryptography.

Grover’s algorithm is also well known and used for searching an unstructured database or an unordered list.

There are other interesting algorithms available that you can find here.

Let’s explore a small variant of Grover’s algorithm, the quantum algorithm for searching.

First, consider a list of N phone numbers and name from which we need to find name of a specific number

Unlike normal quantum algorithms that provides an exponential increase in speed, Grover’s Algorithm only provides a quadratic increase in speed. The complexity will be a function of square root of number of possible elements, N. This is much more efficient when compared with classical algorithms which may have complexity N. Grover’s Algorithm work using Amplitude amplification.

For our example we will consider only four numbers, which can be represented using 2 qubits and we need to find the name associated with 10

a|00> + b|01> + c|10> + d|11>

where a,b,c and d are the amplitudes and a=b=c=d.

this is the first step in Grover’s Algorithm is to put the qubit in super position.

Second step is to apply an oracle function which flips the amplitude of item we are looking for in opposite direction. In this case c becomes -c. Now a=b=d and c is different and negative.

Third step is to apply an amplification function which amplifies the difference between each amplitude and those of the equal superposition states. Since the value of -c is having much difference from other amplitude the value of c rapidly increases compared to a,b or d.

Now if we measure the qubits the 3rd state will be returned with maximum probability (Step 2 and 3 can be applied again to increase probability). So using this technique we are able solve the search by loading all the available values into the qubit all at once. The more number of qubits available the higher there problem domain sizes we can work with.

All well and good but what about the hardware to run all this.

Current implementation of quantum computers are based on semi-conductors. The qubits generated from these semi-conductors should be kept away from any external interference. Other wise the quantum mechanical properties of these qubits will be lost. So the temperature of these quantum computers are kept very near to absolute zero and the set up for this along with calculations at microscopic levels can make quantum computers extremely expensive. Precise microwave/electromagnetic waves can be used to modify the states of qubites. It is often the case that a classical computer is used along with a quantum computer to help with processing.

IBM Q is an industry-first initiative to build commercially available universal quantum computers for business and science. IBM Q Experience allows us to run quantum algorithms either using online composer or using its python library for free. The number of qubits in these systems are relatively small but will increase rapidly for sure.

D-Wave Systems is another major player in this space with their flag ship 2000 qubit D-Wave 2000Q quantum computer. D-Wave products are widely used by companies like Google to run Quantum Artificial Intelligence Lab and NASA for their research.

The D-Wave machine uses Quantum annealing to perform its operations. This is great for optimising solutions to problems by quickly searching over a space and finding the global minimum which becomes the solution. This approach might be faster for certain problem domains but a system using quantum annealing will find it difficult to run certain algorithms like the famous Shor’s algorithm.

On the other hand Universal quantum computing offered by IBM will serve broader problem domains and allow us to design much more complex algorithms. But designing those algorithms with Universal quantum computing can be complex and it comes with its own challenges in system design and consistency.

Quantum mechanics is a field of science which is inherently astounding, and computing capabilities offered by it is just the tip of the iceberg. It has wide range applicability in biology (it can explain mutation by superposition), computer hardware (to explain properties of semiconductor chips), and it can even explain how the expectation or thoughts of human can affect the future as explained by the Global Consciousness Project, which experimentally proved that “When human consciousness becomes coherent, the behavior of random systems may change“. Yes, It is true that there is strange relation between human mind and quantum physics. Further more, it can be used for Quantum teleportation which was reported by Chinese scientists that they had transmitted the quantum state of a photon on Earth to another photon on a satellite in low Earth orbit. Quantum mechanics posses the potential to change every thing that we know and do in the classical way.

I hope you understand something…

“If you think you understand quantum mechanics, you don’t understand quantum mechanics.” Richard Feynman

Thanks for your time.

No comments:

Post a Comment