In 1982, a scientific paper - 'Simulating Physics with Computers' written by the famous physicist Richard P. Feynman was published. In his paper,

Feynman had pointed out that there seemed to be essential difficulties in simulating quantum mechanical systems on classical computers, and suggested that building computers based on the principles of quantum mechanics would allow us to avoid those difficulties. (source)

Many physicists taking a cue from Feynman, started to explore this field. But there were other developments that had been taking place in the field of computer science much earlier which also naturally led us to this new frontier of quantum computing. 

Here I would like to mention two such developments.

Evolution of the Church-Turing Thesis

Let me warn you, this might seem like a detour, but it is a very interesting development in history that led us to quantum computing. 

Much before modern computers were invented, Alan Turing - a mathematician well known for breaking the ciphers of the German Enigma machine - published a paper in 1936, in which he developed the model of a programmable computer, now called the Turing Machine. In his theoretical model, he showed that we can also imagine a Universal Turing Machine that could simulate any other Turing Machine. 

This implied that -

if an algorithm can be performed on any piece of hardware (say, a modern personal computer), then there is an equivalent algorithm for a Universal Turing Machine which performs exactly the same task. (source) 

•  Discussions related to efficiency of algorithms in the field of 'computational complexity', sparked the conversation of efficiency of the Universal Turing Machine, and it was felt necessary to add the words 'efficiently' to the Church-Turing thesis. 
  
  
• Later another update was inspired by the Solovay-Strassen test for primality (an algorithm for checking whether a number is prime or composite). This algorithm was probabilistic in nature, that is, it could tell that a number was "probably prime or else composite with certainty". So it seemed like this case of probabilistic algorithms could not be simulated by a Universal Turing Machine and thus challenged the Church-Turing thesis. However, this challenge was resolved by just considering a probabilistic Universal Turing Machine for the case of probabilistic algorithms. So the Church-Turing thesis kept holding true.

Evolution of the Chuch-Turing Thesis

To one scientist, David Deutsch, these updates to the Church-Turing thesis seemed never-ending and the capabilities of the computational model of a Turing Machine seemed open-ended. 

He wanted to find the ultimate computational model that could efficiently simulate any other model of computation; one single model that could efficiently work for all probabilistic and deterministic algorithms, and even go one step beyond by being able to solve those computational problems that can never be solved by classical computers (like Turing Machines). 

At this point, David Deutsch started to consider the idea of a Universal Quantum Computer. This was an important impulse towards the exploration of quantum computing.

Interference From Quantum Effects In Electronics

Since the invention of the electronic transistors in 1947, engineers have made tremendous progress in creating highly packed and complicated electronic circuits using transistors for performing computational tasks. With time, engineers have been able to fit larger numbers of transistors (4.3 billion on a chip) in smaller areas of the circuit board, enabling us to build very powerful general purpose computers. But by creating such tiny transistors (1nm in size) so close to the atomic scale (0.1 nm - 0.5 nm) we are now starting to see the effects of quantum mechanics interfere with the functioning of these devices. Weird phenomena like Quantum Tunnelling take such prominence, that they can't be ignored. One way to solve this issue, could be to find a new way to use these principles of quantum mechanics to perform computations, in a way using it to our advantage. This pushes us to think seriously about quantum computing.

So just to quickly rewind before we move on, 3 key factors that drove scientists to explore the field of quantum computing were - 

1. Desire to simulate the quantum physics of real quantum-mechanical systems on a computer.
2. Pursuit to find the ultimate computational model that could simulate all other computational models.
3. Finding a way of utilizing the principles of quantum mechanics for computing.

You'd be surprised that our ideas of classical computing help us so much in thinking about quantum computations. It is a whole new world, with fundamentally new physics, but still with so many parallels to what we already know. How? You'll see in a bit. But first, let's just take a quick look at the most fundamental idea in classical computing.

In classical computing, we represent information in the form of 'bits' (binary-digits). A single bit can take one of two values at a given time - 0 or 1. A bit can be implemented in various physical forms, such as HIGH/LOW voltage in a wire, or light-ON/light-OFF in an optical fiber etc. 

It is quite easy to physically implement natural numbers using bits. With one wire we can represent two mathematical numbers (1 & 2). More wires can help us represent more numbers as shown below. With each new wire, the amount of numbers that can be represented doubles, because the number of combinations that can be formed using 0s and 1s doubles.

Representing numbers with combinations of bits

I'm sure you were wondering about what parallels we can draw between classical and quantum computing. Well here's the first one - quantum bits.

Just like classical bits are the basic units for classical computing, Qubits (quantum bits) form the basic units for quantum computing.

A single qubit can be in the quantum state |0> or quantum state |1>, or in a special quantum state called the superposition state.

Quantum states are represented by this notation '|>' called the 'ket-notation', where |0> is read as 'ket-zero' and |1> is read as 'ket-one'.

The 'superposition state' is a quantum state made up from the linear combination (in other words superposition) of the basis states |0> & |1>.

Wait! Wait! Wait! What is Superposition?

Alright! Let's slow down a bit and try to understand what this term 'superposition' really means.

So in classical mechanics (think of Newton's Laws of Motion), properties of objects - properties like position, velocity, momentum, etc. - have very specific values at every instant in time.

Let's consider a particle. And its 'position' property.

Now in classical mechanics, at any one instance in time (how I wish I could freeze time), the position of the particle has very specific values of x, y and z coordinates. I've tried to show this in the image below.

Classical Mechanics - Position (x,y,z coordinates) at 4 instances in time

But in quantum mechanics, when we go down to the level of atoms and sub-atomic particles like electrons, protons, photons (the light-particle) etc., things get very blurry. 
In the quantum world, at an instant of time, properties do not have specific values, but instead have a range of possible values simultaneously. 

Thus the same particle as before, in the quantum world would have a range of possible positions existing simultaneously (imagine a cloud of possible position points). I've tried to show this in the image below.

Quantum Mechanics - Cloud of possible positions of the particle

This simultaneous existence of possible values of a property (position in this case) is called a 'superposition'; and the particle is said to be in a state of superposition. Every position has a certain probability attached to it - the probability (or chance) of the particle showing up there when observed. The yellow graph shows the distribution of probabilities with varying positions, called the wave-function.

"When observed" ?!! What's that supposed to mean?
Well yea! If you were thinking, particles maintain their state of superposition always, you're wrong. They are very flimsy at that. They love being in a state of superposition when you are not looking at them; that is, when you do not disturb them at all in any way. But the moment you do, they immediately pick one value from the range of possible values and settle. This is called the 'wave-function collapse'.
It is as if, they don't want us to discover their little secret and catch them red handed. 

Even the simple act of looking, for which you would have to shine light on the particle, would disturb the superposition and cause it to collapse. Below is an image that can help you visualize this. When you're not looking (in the dark), the probability cloud exists, and the moment you switch on the lights, i.e., try to see it, the cloud collapses to one specific position(marked by a yellow dot.) Spend a few moments looking at the image below and absorbing what we've just discussed.

Superposition state (cloud) exists only when not being observed

Now that you have seen what we really meant by superposition, let's try to understand the superposition state of a qubit. 

Consider an electron which has a property called 'spin'. It is an intrinsic property of elementary particles, a sort of angular momentum vector like the angular momentum you might have seen in classical mechanics. If you pick a direction of measurement, say the vertical direction, the electron may be spinning about its vertical axis in one of the two directions, i.e., clockwise or anti-clockwise. Thus the spin angular momentum can have one of the two directions, i.e., up or down (ignore the magnitude for now.)

Quantum States of the 'Spin' property of an electron

Now by our understanding of superposition in the quantum world, when we are not looking at the electron, its spin property will be in both SPIN UP & SPIN DOWN state simultaneously, with a probability of occurrence attached to each state. 

Mathematically, this is denoted by the following wave-function, a linear combination of the two states - 

where alpha and beta denote the probabilities of occurrence of the spin-up state and spin-down state respectively upon measurement. One thing to note however, is that alpha and beta are complex numbers of the form (a + i b). 

But being complex numbers how can alpha & beta denote probability values (which are scalar values)?
Well actually, the square of the magnitude of those complex numbers (which is scalar) are equal to the probabilities. And the summation of the two individual probabilities must be equal to 1.

So what we have just seen is a qubit implemented using an electron. It may be implemented using any single quantum mechanical system with a quantum property that has exactly two possible values. So you can even implement it with a photon with two values of its 'polarization' property. 

Generic Representation of A Single Qubit

Generically, if you consider a qubit (physically implemented in whatever fashion), it will have some property with two possible values, lets represent the two values as |0> and |1>. Until we observe, i.e., make a measurement of the property, the qubit will possess both the values |0> & |1> simultaneously (be in a superposition of |0> & |1>) with specific probability numbers alpha & beta attached to them respectively. 

Mathematically - 

Where alpha and beta are bound by the constraint - 

Alpha and beta are such that, when we measure the qubit, the probability that the superposition will collapse to |0> state is the square of the magnitude of alpha, and the probability that the superposition will collapse to |1> state is the square of the magnitude of beta.

Take note of the fact, that when the superposition collapses to either |0> or |1> state and you measure it, it turns into a classical bit 0 or 1; and the superposition is lost forever.

Various Superposition States

You can see we have always talked about the superposition probabilities as alpha and beta variables. What we mean to say is that for different combinations of (alpha, beta) you can get different superposition states. 

Here are examples of a few superposition states:

All of the above are individual superposition states. When we are not observing, the qubit is in some superposition state similar to the ones given above.

It's really hard for us to find out the value of alpha and beta for the superposition state the qubit is in. We'll have to prepare infinitely many qubits in the exact same quantum state and then make a measurement on all of them to find the probabilities from the final occurrences - number of 0s and number of 1s.

Mathematics is the language of science and it helps us probe and represent what we observe in our experiments through solid mathematical equations we can trust. 

In the same fashion, understanding the field of quantum computing has been simplified by representing qubits as matrices and computations on them being thought of as algebraic operations of matrices. 

Quantum State of a Single Qubit

The quantum state of a single qubit is written in matrix form as:

Using this notation, we can represent |0> and |1> as:

You can now see that the matrix notation makes sense because by using matrix algebra if we add up the matrix versions of |0> and |1> we do get the matrix version of the generic quantum state of the qubit - 

Quantum State of a Multiple Qubit Sytem

So what if you had two qubits. Is there a way to define some sort of an overall quantum state for the two-qubit system.

Actually there is. It is called the 'Joint State' of the system.

If you had two qubits, one in quantum state |x> and one in quantum state |y>, if we were to consider the two qubits as one system, then the overall quantum state of the system (joint state) can be given by the tensor product of the individual quantum states.

Overall Quantum State of a 2-Qubit System

Mathematically speaking, in terms of matrices, tensor product is given as below:

So what kind of overall quantum state (or joint state) does the above result indicate? 

Well it's not quite evident if we look at the final single column matrix. But there is another way to calculate the tensor product which provides a better picture of the result:

Now take a look at the above result. If we look closely, the final result looks like a linear combination (superposition) of four states: 

Also the sum of the squares(S) of the numbers attached to each state is equal to unity, as shown below:

Therefore the final state seems to fit the profile of a legitimate quantum state which has been made from the superposition of 4 basis states |00>, |01>, |10> and |11>, with attached probabilities. 

Thus we can say that the tensor product of individual quantum states represents the overall quantum state (or joint state) of the multi-qubit system. The overall quantum state is known as a 'product state'. 

Another name for it is 'separable state' because the state can be separated as the the product of the states of its individual constituent particles. 

It may seem like the joint state of all multi-qubit systems maybe represented as a tensor product of two other quantum states. But its not always the case. 

Check these quantum states out as examples, which cannot be broken into a tensor product of two other states, they are unseparable -

These quantum states can actually be prepared by taking two qubits and performing certain state transformations so that we get two qubits such that their overall quantum state is entangled. The entangled state is also referred to as 'un-separable state'.

We can entangle prepare a pair of entangled qubits

We'll come back later to what quantum operation is used to entangle qubits.

Before we move on, it would help to quickly revise a few ideas from matrix algebra that we'll be dealing with in the coming chapters.

1. Identity Matrix ( I ): 

An Identity matrix is a square matrix in which all the elements of the principle diagonal are 1s and all the remaining elements are 0s. Multiplying the Identity matrix to another matrix leaves the other matrix unchanged.

2. Conjugate Matrix ( A* ):

The conjugate matrix A*  of a matrix A, is the matrix given by the replacing each element (a + i b) with its complex conjugate(a - i b).

3. Transpose of a Matrix:

You can visualize this operation as below:

Taking Transpose  - Flipping the matrix across its main diagonal

4. Conjugate-Transpose of a Matrix:

The conjugate transpose of a matrix is obtained by first taking the conjugate of the matrix, and then transposing the conjugate.

5. Matrix Multiplication:

If you have no idea about how two matrices are multiplied, without wasting much time, I'd like point you directly to this short video on the same. It should quickly get you up to speed.

By now I hope you've gotten a feel for the quantum state of a qubit, specially the superposition state and even the joint state of multiple qubits. Now it's time to understand how we can manipulate these quantum states. Being able to do so, lies at the heart of all quantum computations.

Just like in classical computing, we manipulate classical bits by passing them through boolean logic gates, in quantum computing we manipulate qubits by passing them through quantum gates.

Mathematically this equates to multiplying the matrix representing the quantum gate to the matrix representing the quantum state of the qubit.

Also, a matrix can be used as a quantum gate if and only if it is a unitary matrix.

Unitary Matrix!! Now what in the hell is that?

If you take a matrix U, then it is a unitary matrix, if and only if it satisfies the following condition:

where,

Unitary matrices have certain properties that match with the characteristics of a quantum gate. We'll come back to what these properties are, but for now let's quickly dive into some basic quantum gates.

A single qubit gate is one that operates on only a single qubit, i.e, it just takes one input. Let's take a look at some single qubit gates and see how they operate.

1. NOT Gate / Pauli-X Gate

You might have seen a NOT gate in classical computing, which takes '0' as an input and outputs a '1', and vice-versa. For the same reason it's also called an 'inverter'.

The quantum NOT gate also works similarly. It takes the |0> quantum state as input and outputs the quantum state |1>, and vice-versa. It is represented by the symbol 'X' and it obviously has a matrix form as shown below.

But what about the superposition quantum state?

We know a qubit may be in a state of superposition between quantum state |0> and quantum state |1>. Applying the quantum NOT gate on a superposition state, gives a quantum state where the roles of |0> and |1> have been interchanged.

In  other words, the probabilities of finding |0> and |1> upon measurement get interchanged for a superposition state.

2. Pauli-Y Gate

The Y Gate when applied to a superposition state, behaves as given below:

3. Pauli-Z Gate

4. Hadamard Gate (H)  

  

These gates, Pauli-X, Y & Z and the Hadamard gates are some of the most important ones used in building quantum circuits.

Unlike classical computing, where the NOT gate is the only single bit gate, in quantum computing, there can be infinitely many single qubit gates possible, as there is no limit to the number of unitary matrices that can be formed.  

You can imagine, that with a single qubit in a superposition, we are able to work with 2 basis states (0 & 1) at the same time. With two qubits, we're able to work with 4 basis states (00, 01, 10 & 11) simultaneously and with 3 qubits, the capacity of simultaneous computation goes up to 8 basis states. Multiple qubits is the playground we want to be to make use of the immense power of quantum computing. 

Overall Effect of Gates in a Multi-Qubit Circuit

Let's try to see what a multi-qubit quantum circuit looks like. Consider two completely un-entangled qubits. Imagine them to be sitting inside a box without interacting with each other in anyway. Then imagine, we apply a single-qubit gate U on the first qubit and another single-qubit gate V on the second qubit without any interaction between the two processes. 

Now we know that applying the single-qubit gates individually to each qubit changes the states of the qubits as shown above.

But if we consider the two input qubits as forming a 'Multi-Qubit System', then how do we measure the overall effect of the two single-qubit gates on this qubit-system?

As we have proved above, you can see that,

the overall effect of the individual gates in the quantum circuit, has been equivalent to applying the tensor product of the individual gates on the overall state of the 2-qubit system at the input.

You may be able to visualize/represent the overall effect as the tensor product of individual quantum gates, but not always(like in the case of a CNOT gate).

Below are some of the cases whose equivalent tensor products are given alongside:

CNOT Gate

An interesting example of a multi-qubit gate is the 'Controlled NOT Gate' in short referred to as the 'CNOT Gate'. It is a 2-qubit gate, but its overall effect cannot be represented as a tensor product of two single-qubit gates.

Controlled NOT quantum gate

The overall effect is that when qubit-a is in quantum state |0>, we receive qubit-b as it is (with no changes), at the second output. But when qubit-a is in quantum state |1>, a NOT Gate gets applied to qubit-b and thus we receive NOT(|b>) at the second output. 

Thus, the second output on the whole, mathematically behaves like the modulo-2 addition of qubit-b and qubit-a.

Therefore we have a circular plus sign on the second quantum wire representing modulo-2 addition.

So far we have seen quantum circuits with qubits, quantum wires and quantum gates. But we have left out an essential part of the quantum circuit - the measurement instrument.

What are we measuring again? 
Well of course, the quantum state of the qubit, but, in reality, we are measuring the property that exhibits quantum behavior and that we have chosen to represent the quantum state of our qubit. So if our qubit is an electron, we might be measuring its spin; or if our qubit is a photon, we might be measuring its polarization.

So depending on the type of quantum mechanical system (electron or photon etc.), our measurement instrument may change. But the general representation of a measurement instrument (and naturally the act of measurement), is given below:

Measurement Device - Quantum Circuit Symbol

To the left is an incoming quantum-wire, drawn as a single line that is capable of transmitting qubits, whereas to the right is an outgoing normal wire (electrical, optical, etc.,) drawn as a double line, that is capable of transmitting classical bits.

Case 1 : Measurement of a Single Qubit

We have already seen that when a qubit's quantum state is measured, the superposition collapses to one of the basis states as per the respective probabilities. 

The observed result of measurement on a single qubit is thus as given below:

Single Qubit Measurement Results

Case 2 : Measurement of a Multi Qubit System

Making measurements on a multi-qubit system is quite similar to measurement of single qubits. The result is based on the probabilities associated with the basis states in the joint state of the system.

Consider below two qubits coming out of a quantum circuit, and each is measured simultaneously using measuring devices. 

The observed result of measurement is thus as given below:

Measurement of a Multi Qubit System

Case 3 : Partial Measurement of a Multi Qubit System 

Let's look at a very interesting case. 

What happens if we measure just one qubit in a two-qubit system? Does it have any effect on the measurement of the second qubit later on?

Well first of all, measuring the first qubit, does have an effect on the measurement of the second qubit later on. It basically changes the probabilities of observing a 0 or 1 for the second qubit. 

 Shown below is the setup for this arrangement.

Partial Measurement of a 2-Qubit System

Working out how the probabilities play out is just some basic conditional probability mathematics. Let's name the event of measuring the first qubit - event 'E', and the event of measuring the second qubit - event 'F'. On the same lines, let's use the following notations for the observed measurements:

Now let's make a small probability chart for different outcomes:

Probability Chart of different outcomes

Conditional probability has a simple formula for "Probability of A given B(already occurred)":

Once the measurement of the first qubit has been made, its result (0 or 1) becomes a given for the measurement of the second qubit. Therefore, the probability of the second qubit turning out to be 0 or 1, is given as below : 

We've been talking a lot about a qubit's quantum state and the probabilities of the outcomes being based on the quantum state the qubit is in. But how do we actually implement it physically.

A team of scientists from the University of New South Wales in Sydney, have devised a way of reading and writing the quantum state on a qubit (an electron) by irradiating it with microwaves. Check this video out:

What we've discussed so far, has just scraped the surface, an introduction to the basics of quantum computing, but understanding these basics - the behaviour of qubits, quantum gates and measurements is essential to understanding all that goes behind quantum algorithms used for performing complex calculations.

Quantum algorithms and computations, and some interesting experiments like 'Quantum Teleportation' could make for a great next guidebook.