Quantum Computing Explained using Q#

Summary: 

As I’ve promised in my first article (The Truth about Neural Networks) the next topic is Quantum Computing. In this post I will explain the basics of quantum computing as clearly as possible, without too much math, only the main idea and the main  concepts. To easily understand the main concepts, I will compare Quantum Computers with Classical Computers (analogy is always good to understand new concepts). At the end of the post you can find an example code which can run on Quantum Computers. For this I will use Q#, a new development kit produced by Microsoft. I’ve chosen the new Q# programming language, because, as you will see, it is very easy to understand the code. If you are familiar with C# or F# then it will be straight forward. If you want to jump ahead and see the example and the code, without reading the theoretical part, then click on this link Q# Example.

Quantum Computers

Conventional Computers are strictly digital, and rely purely on classical computing principles and properties. So in this conventional world we talk about black and white, yin and yang, good and bad and in the case of classical computer 1 and 0 as bit values. But there is another world inside our macro world, which is governed by other rules, where theoretically a bit can have infinite number of values and communication can be instantaneous, information can travel faster than light. So we can say that this kind of bit it’s a super bit, which have all the classical values (1 and 0) but it can have values between 1 and 0, which are called Superpositions. This bit is called Qubit. Another interesting concept is Entanglement, which is the basis of sending information at a speed much faster than light speed.

Theoretical background

The easiest way to understand Quantum Programming and Quantum Computer is by comparing it to a Classical Computer.

The limitations of Classical  Computers

For several decades now, speed and computational power of conventional computers has been doubling every two years. This is really fascinating and it is a great achievement, but it’s not enough, there are lots of problems from the field of mathematics (like prime number factorization), physics and chemistry (like molecular modelling) which can’t be addressed with classical computer. These problems have exponential growth, which means that it grows faster than the computational power of a classical computer, so with classical computers we will never be able to solve these problems.

Another problem with classical computers is that they have an important limitation, namely transistors. Physically, the binary numbers 0 and 1 can be represented using any two-state entity like a coin (head and tail) or a switch (on or off). In computers, bits are the presence or absence of voltage (1 or 0). Computation is done by logic gates which are typically made up of transistors that controls the passage of electronic signal. If it allows the signal to pass through, it’s the bit 1 and if the signal is cut off, it’s 0. The size of transistors can continue to shrink but eventually, they’ll hit a physical limit where electrons will just tunnel through them and there’ll be no control over the electronic signal flow.

To solve all these problems we have to rethink the architecture of a computer! This is why we need Quantum Computers. Quantum Computers will have speed and computational power way beyond classical computers. Even if we don’t have a working Quantum Computer now, or we have some quantum computers with high error rate and small number of qubits, big companies like Microsoft, IBM or Google are working on it and it is just a matter of time to solve the problems and create a working Quantum Computer.

Quantum Physics Behind the Scenes

To understand quantum computing the first step is to understand what is a qubit, what is the difference between a qubit and a classical bit and how can we read or set the value of a qubit.

The main difference between a bit and a qubit is that a bit can have only two values, 1 or 0, but a qubit can have 1 and 0 (so a quantum computer can run also classical programs and it is compatible with classical ones, basically the quantum computer will work side-by-side with classical computers, but we will see this later) and infinite number of values, which are located on the Bloch Sphere, called Superpositions. Wait what? How is this even possible?

To explain the Superposition, the easiest and most intuitive way is to visualize it. To visualize all the values that a qubit can have, we have to use a so-called Bloch Sphere.

As you can see, the Bloch Sphere is a simple sphere used to model a spin of an electron or to model the values of a qubit. A Qubit can have any value from the surface of the sphere, so basically, it’s value is determined by 4 complex parameters, the probability and phase of state 1 and the probability and phase of state 0. The formula which describes the state of a qubit is a * e^iχ * |0⟩ b * e^iϕ * |1In this formula a and b are the probabilities while χ and ϕ are the phases . This article is a high level introduction to quantum computing, so I don’t want to bother you with too much math. If you want more information about the formula, what is the phase of a qubit, then watch this video: Concepts of Superposition.  You can find another good explanation for why do we have a sphere and not (for example) a cylinder here: Understanding the Bloch Sphere.

Here is how can we visualize a qubit and a classical bit in comparison:

The main idea is that a bit can have two values, so it can be mapped to the poles of the Bloch Sphere while a qubit can have infinite number of values. The value of a qubit is statistical, it can be represented as a * |0> + b * |1> (we use |value> to note that this is a qubit value and not a classical bit value) , where |a|^2 + |b|^2 = 1. This means that, when we measure the value of a qubit it will behave like a flip of a loaded coin, it will give 0 with a probability of a% and 1 with a probability of b%.

So why is this so important if after measuring, a qubit can have only two values just as a classical bit? The answer is that the important par of the calculations will take place when we are not measuring the qubits (see the Measurement Problem). So an algorithm with multiple qubits will run all the possibilities in one step while a classical computer have to analyses all the possibilities step-by-step. (See figure below, the classical computer has to analyse all the paths, while in the case of the quantum computer we have only one path).

The result of the Quantum Computer will be probabilistic, so we have to run the same algorithm multiple times, but it is still much faster than analyzing all the possible paths.

But this is not the only advantages of quantum bits. Another important concept is Entanglement. It basically refers to quantum particle’s properties that get entangled and become dependent on each other and thus cannot be changed separately. They act like a single system with an overall state. The important part is that the state of one system will give you precise information about the state of the other system, no matter how far the two are from one another. So if we change the spin of one qubit, the entangled partner will immediately change its spin even if the entangled partner is in another universe. This means that the communication between two entangled qubit is much faster than the speed of light, even if Einstein stated that nothing can be faster than the speed of light. This property of entangled quantums can be used for Teleportation (you can find a conceptual implementation of teleportation in Q# here: Teleportation).

How can two entangled quantum communicate with each other faster than the light speed? It’s a big question and we don’t know yet, but a possible explanation can be the Simulation Hypothesis (other interesting video:  What if the Earth doesn’t exist).

If you want more technical information about Quantum Computing and Quantum Physics a good starting point are the following links:

A really good video was made by Máté Galambos, check out his YouTube channel!

Similarities between Classical and Quantum Computers

The main and most important similarity is the way we can change the state of a bit or a state of a qubit. Classical logic gates and quantum logic gates are both logic gate. 

A logic gate, whether classical or quantum, is any physical structure or system that takes a set of binary inputs  and spits out a single binary output. What governs the output is a Boolean function. The gates are then combined into circuits, and the circuits into CPUs or other computational components.

Ok, that is easy, we are talking about logic gates. To understand the way-of-working of a Quantum Computer, we have to understand the logic gates and how does they work.

In the case of Classical Computers we have logic gates like AND, OR, NOT, XOR, etc.

Similarly in the case of Quantum Computers have other gates like Pauli-X, Pauli-Y, Pauli-Z gate which are used to rotate the value of a qubit on the Bloch Sphere (one gate for each dimension), we have the Hadamard gate, which is used to create a superposition and we have controlled gates like CNOT and Toffoli or CCNOT gate.

Another interesting gate is the T gate, which will rotate the value of the qubit with a specified degree grades around the Z-axis.

Other less commonly used gates are S, SWAT gate, XX gate etc. (for more information click the following link Quantum Logic Gates)

Now lets explain the most important gates and visualize them in the Bloch Sphere!

Pauli-X Gate

It is basically equivalent with the classical NOT gate. So this gate will rotate the value of the qubit with 180 grades around the X-axis. If the state is 1 then after applying the gate it will be 0 and vice-versa.

Pauli-Y Gate

This gate also rotates the value of the qubit on the Bloch Sphere, but using the Y-axis and not the X-axis. Its value is a complex number and the state can be described as a*i*|1> – b* i*|0>. Basically it changes the value of the qubit in a controlled way.

Pauli-Z Gate

Similar to the Pauli-Y gate, it will rotate the value of the qubit using the Z-axis. This gate flips the sign of the second term so the result will be a*|0> – b*|1>. This is also called the flip-phase gate.

So visually we can represent these gates on the Bloch Sphere like this:

Hadamard Gate

This is another important gate, because this has the capacity to transform a definite quantum state, such as spin-up, into a murky one, such as a superposition of BOTH spin-up and spin-down at the same time. After applying, from |0> we will get  \frac{|0\rangle + |1\rangle}{\sqrt{2}} and from |1> we will obtain \frac{|0\rangle - |1\rangle}{\sqrt{2}}.  This means that the qubit becomes like a penny standing on its end, with precisely 50/50 odds that it will end up heads (spin-up) or tails (spin-down) when toppled and measured.

This H-gate is extremely useful for performing the first computation in any quantum program because it transforms preset, or initialized, qubits back into their natural fluid state in order to leverage their full quantum powers.

In the Bloch sphere representation, it is easiest to think of this as a rotation of |ψ degree around the X-axis by π radians (180) followed by a (clockwise) rotation around the Y-axis by π/2 radians (90).

Phase Shift Gates

These gates “twists” the |1> state by an angle. It is just a simple rotation around an axis with a specific angle. The Pauli-Z gate is also a phase shift gate, because if the angle is 180 grades then the phase shift gate is equivalent with the Pauli-Z.

T gate

The result of this gate is a rotation around the Z-axis with a specified value, so the input is an angle.

CNOT Gate

As we can see, the CNOT gate has two output. On the first output the value of |X> won’t be modified, while the second output is equivalent with the classical XOR gate.

CCNOT or Toffoli Gate

This is a very important gate and it has lots of practical usages.

The quantum Toffoli gate is defined for 3 qubits. If the first two bits are in the state |1>, it applies a Pauli-X (or NOT) on the third bit, else it does nothing. It is an example of a controlled gate. Since it is the quantum analog of a classical gate, it is completely specified by its truth table. The Toffoli gate is universal when combined with the single qubit Hadamard gate.

The truth table of the Toffoli gate:

As in the case of classical computers (where the universal set of gates consists of {AND, NOT} or {OR, NOT}), we can define universal set of gates also for the quantum computers. Because in the case of the quantum computer the possibilities are infinite, this universal set of gate will be just an approximation, but for practical purposes it is more than enough.

A universal set of gates for quantum computers is composed of the following gates: CNOT, Hadamard, Phase and T(π /8).

With these things in mind, we will implement a simple Half Adder in Q#.

Why is Quantum Computing so amazing?

The amazing part of this story is that combining Quantum Computers computation power with Artificial Intelligence there is a possibility to reach General Artificial Intelligence and solve our society biggest problems. This would influence everything, with Molecular Modelling scientists could better understand and solve diseases, digital security would be totally changed,  all the main cryptography algorithms would be useless, but quantum cryptography would be much stronger etc.

In my opinion, not AI but Quantum Computing will be the next technological revolution, this can change all what we know about the universe, this can change all our life, so whoever (or which company) will create the first stable Quantum Computer will be the leader (at least technologically) of our world.

Example using Q#

In this example we will implement a simple Half Adder using Q#.

What is a Half Adder? It is a circuit that adds two bits, without considering the input carry. So the input of this circuit is two bits x0 and x1 and the output is the Sum of these two bits and the Carry.

The truth table of the half adder is the following:

The classical circuit for the Half Adder can be defined as follows:

This means that the Sum = x0 XOR x1 and the Carry = x0 AND x1. As we mentioned in the theoretical part of this article, we can obtain an XOR gate using a CNOT gate, so the Sum will be easily calculated.

To simulate an AND gate we can use a Toffoli gate. How can we do that? As we know if the first two bits of the Toffoli gate is 1 then it will flip the value of the third bit. So if we put on the third bit a 0, this means that the 0 will be flipped to 1 if and only if the first two bits are 1. This is exactly how the AND gate works, the output will be one, if and only if all the inputs (here we have two inputs) are 1. As a conclusion, the Quantum Half Adder circuit will look like this:

Now lets see the implementation of this circuit using Q#!

Before diving in the code, I want to mention the Q# library was built to eventually create a full software stack that will give interested developers a chance to learn about quantum computing programming before the technology becomes more readily available.

Q# is a high-level programming language meant for writing scripts that will execute its sub-programs on a quantum processor that is linked to a classic host computer which receives its results. Developers using the language need not have in-depth knowledge of quantum physics.

For the interested, Microsoft does provide a primer on essential quantum computing concepts, covering vector and matrix mathematics, the qubit, Dirac notation, Pauli measurements, and quantum circuits.

Using Q# does not require in-depth knowledge of quantum physics or mathematics, because this library defines all the gates and all the concepts as classes, operations ad functions, so the only real knowledge that is required is what to use and when to use it. For this Microsoft provides a very well organised, detailed and easy to understand documentation. So thank you Microsoft for the good job and thank you for making developer’s life easier!

Each Q# program has one or many .qs files which contains the quantum operations and at least a .cs file, called Driver, which calls the operations implemented in the .qs files. This way Q# can be used in C# code, so the quantum operations can be used for example in a WPF or an ASP.NET project by calling the Driver of the operation.

Q# program is composed of one or more operations, one or more functions, and user defined types. Operations are used to describe the transformations of the state of a quantum machine and are the most basic building block of Q# programs.

In contrast to operations, functions are used to describe purely classical behavior and do not have any effects besides computing classical output values.

You can find more information about Q# here Q# Development Techniques, but now lets see the code that I wrote to implement a simple Half Adder (other good example can be found here Teleportation):

The first operation, Set checks if the quantum is in the desired state (which can be One or Zero) and if not then applies the X gate, which flips the state, this way initializing the qubit with the desired state.

The second operation, SetQubitState translates a Boolean value to a desired state of One or Zero and calls the Set operation.

The third operation, ConvertQubitStateToBool converts a Qubit state to a Bool value.

The last operation is the main operation, HalfAdder firstly creates two mutable variables Sum and Carry for the result of the operation. By default in Q# every variable (defined with let) is immutable so if the value of the variable will change after initialization, we should declare it with the mutable keyword.

In the next step it allocates three qubits (two inputs and the 0 qubit necessary for the and operation AND).

The qubits are disposable objects so we should use them in a using statement and to clear the possible entanglements between the qubits, after using them we should reset their state using the ResetAll function. Inside the using statement firstly we set the state of the qubits and then we construct the circuit.

As we can see in the half adder circuit design, the first gate is the Toffoli gate so we will use the inbuilt CCNOT gate, which takes 3 qubits, two control qubit and on target qubit. The target qubit will be Zero, this way constructing the AND gate.

In the next step we use the inbuilt CNOT gate to calculate the XOR between x1 and x2.

In the last step we convert the qubit result states to boolean values and set the value of the Sum and the Carry variable, which will be the return value of the operation. Note that in Q# we use tuple values, so we can return multiple values from an operation.

The C# code for the Driver looks like this:

In this code, firstly we construct all the possible combinations of two bits and then we run the Quantum Half Adder for each of those values. Note that if we run the code locally, we have to use a QuantumSimulator object which will simulate the behavior of the actual quantum computer.

The result of this experiment is the following:

This demonstrates that our code, our circuit is working correctly!

As we saw the Q# is very similar to C# or even to F#, we use namespaces, we use well-known primitive values, tuples are present also in C# and every gate is already implemented. Every operation necessary to set or cleanup a quantum state is already included in the development kit, so we don’t have to know all the hard mathematics and physics.

Learning Q# code won’t be harder than learning C#, F# or other languages, it is a high level language, so programmer’s life will still be easy also in the quantum world, thanks to Microsoft and Visual Studio!

Even if now this code is just a simulation of the actual Quantum Computer, Microsoft already have a small-scale Quantum Computer, with few qubits (because of physical limitations, but I am convinced that they will resolve those limitations) so this code can actually run on a real Quantum Computer made by Microsoft!

Observation: I want to mention that the example above is just a simple translation of a classical circuit to a quantum circuit, it doesn’t show the real power of a quantum computer. It has didactic purposes, just to show how easy is to write a quantum program, to demonstrate that it won’t be much harder than a classical programming language. The true power of quantum computing will be teleportation, molecular modelling, fast number factorization etc. 

Conclusions

As we saw in this article Quantum Computing is not just science-fiction, companies and researchers are already working hard to build such a computer. The impact of such a computer will be very high, it will change our world or our universe.

A Quantum Computer can solve much of the problems which are considered impossible using classical computers, it can boost the performance of the AI algorithms possibly leading to a general AI, a human like or better-than-human robot. In my opinion Quantum Computers can bring a new era in the history of humanity because with better tools (and of course with proper usage of those tools) comes greater inventions.

I think that the first step to obtain general artificial intelligence is quantum physics and quantum computing. The first who can build such a computer will be the leader of the technical world so the leader of our world!!

References

  1. Q# Development
  2. Demystifying Quantum Gates
  3. Quantum Logic Gates
  4. Basic Concepts in Quantum Circuits
  5. 6 Things Quantum Computers will be incredibly useful for
  6. Introduction in Molecular and Quantum Computation
  7. Theory Caltech Course

Future

SUBSCRIBE to my blog, because in the future articles I will talk about Blockchain, Quantum Cryptography and I will start a SERIES OF ARTICLES in which I will explain all the popular AI algorithms, how do they work, why and when should you use them. Each article will contain an interesting practical example, so you will see the practical part of the AI algorithms.