Quantum Computing for Everyone - Part I: Classical vs. Quantum Computing

Dominick Marciano

5.00/5 (5 votes)

16 Jun 2018CPOL13 min read

25.1K

An introduction to quantum computing and the differences between classical and quantum computers.

Series Overview

Quantum computing can be a difficult subject to grasp initially. Not because the math, which is only slightly more complicated than high school algebra, but because some of the concepts are counterintuitive based on our daily experiences. Therefore, this article has been broken up into four parts starting with the difference between classical and quantum computers and ending with a demonstration of running an algorithm on a real quantum processor. If you already have some knowledge of quantum computing, you may be able to skip one or more of the parts. However, if you are new to this subject, I recommend going through the articles in order as each part builds on the concepts from the previous parts. Below is a quick overview of the articles in this series:

Part I - Introduction to Quantum Computing (this part): This part will go over the difference between classical computers and quantum computers, explaining how quantum computers are able to achieve the power that they have. The qubit, the fundamental unit of information (analogous to a bit), will also be introduced
Part II - Quantum Gates: This part will introduce the concept of quantum gates and how they operate on qubits to change their states. A description of the most common gates is also provided, along with some examples worked out in detail to show how to figure out the final state of a qubit being operated on by a quantum gate. As this section makes heavy use of matrix algebra, a review of matrices is provided at the start of the article (including matrix multiplication, transposing matrices, and getting the complex conjugate of a matrix).
Part III - Quantum Circuits and OpenQASM: The third part of this series will go over quantum circuits and how they are represented. Some example circuits will be constructed for specific problems. In addition, OpenQASM will be introduced, which is an intermediate programming language used to describe quantum circuits. Using OpenQASM, two programs will be written that will be simulated, and ran on a real quantum processor, in Part IV.
Part IV - IBM Quantum Experience: This part will introduce the IBM Quantum Experience platform. It will introduce the composer, which allows the building of quantum circuits graphically, as well as the OpenQASM editor. The OpenQASM programs created in Part III will also be simulated on this platform as well as ran on a real quantum processor.
Part V - IBM Quantum Experience API (planned): This part will introduce the IBM Quantum Experince RESTful API which allows an OpenQASM program to be submitted and either simulated, or run on the actual quantum processor, with the results returned in JSON format.
Part VI - Simulating Quantum Circuits (planned): This part will show how to simulate a quantum circuit by parsing, and interpreting, an OpenQASM program.

The fifth and sixth parts are currently in the planning stages. If/When they are completed, the links above, and at the end of Part IV will be updated. If there are any other parts that you think should be added, or would like to see, please feel free to leave a comment. I may not respond to all comments, but I definitely read all of them.

Quantum computing is a broad subject which fills large textbooks. In an attempt to condense the information, some details will be left out and there will be concepts presented without any proof for which I ask the reader to simply accept it. However, I will try to give enough information that for the problems that are not fully worked out, and just an answer provided, that the reader should be able to solve themselves (if they are so inclined). If there is anything that you felt was left out of this series and should be included, or something that needs further clarification, feel free to leave a comment on the articles page. I will do my best to accommodate everyone, but please remember that it is impossible to cover everything. When going through this series, if you ever feel lost or just can't understand why some of the things in quantum mechanics happen the way they do, just remember the following quote from famous physicist Richard Feynman:

I think I can safely say that nobody understands quantum mechanics.
-Richard Feynman, The Character of Physical Law (MIT Press: Cambridge, Massachusetts, 1995)

Introduction
Quantum vs. Classical Computers
The Qubit
Visualizing a Qubit
Conclusion
Acknowledgements
References

Introduction

Five Key Laws of Quantum Mechanics

For those who want some more indepth information regarding quantum mechanics, below is quantum physics distilled down into five laws. This information can be found on IBM's Quantum Experience website. For the rest of this series, I will simply refer to this as QX.

Quantum is a system like everything else.
To each physical system there corresponds a Hilbert space of dimensionality equal to the system's maximum number of reliably distiguishable states. A Hilbert space is a linear vector space with complex coefficients and inner products:

$\begin{aligned} \langle \phi | \psi \rangle = \displaystyle\sum_i \phi_i^* \psi_i \end{aligned}$

For a single qubit, there are two standard orthogonal states (computational basis states) that are conventionally denoted as $|0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ and $|1\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix}$
A quantum state is a configuration of the system.
Each direction (ray)in the Hilbert space corresponds to a possible state of the system, with two states being reliably distinguishable if and only if their directions are orthogonal (inner product is zero). Other qubit states include $|+\rangle = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 1 \end{pmatrix}$, $|-\rangle = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ -1 \end{pmatrix}$, $|\circlearrowright\rangle = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ i \end{pmatrix}$, and $|\circlearrowleft\rangle = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ -i \end{pmatrix}$
A quantum state changes; it naturally wants to evolve, but it can always be undone.
Evolution of a closed system is a unitary transformation on its Hilbert space. Unitary means linear and inner-product-preserving.
Scaling - how parts make a whole.
The Hilbert space of a composite system is the tensor product of the Hilbert space of the parts. A two-qubit system can exist in a product state such as $|00\rangle$ or $|0+\rangle$ but also in an entangled state $\frac{|00\rangle + |11\rangle}{\sqrt{2}}$, in which neither qubit has a definite state, even though the pair together does.
Quantum measurements are probabilistic.
Each possible measurement on a system corresponds to a resolution of its Hilbert space into orthogonal subspaces $\{ \Pi_{j} \}$ where $\displaystyle\sum_j \Pi_{j} = 1$. On state $|\psi\rangle$ the result $j$ occurs with probability $P{(j)} = \langle\psi|\Pi_j|\psi\rangle$ and the state after the measurement is $|\psi_j\rangle = \Pi_j|\psi\rangle/\sqrt{P(j)}$. Measurement causes the system to behave probabilistically and forget its pre-measurement state, unless that state happens to lie entirely with one of the subspaces $\Pi_j$.

Ever since quantum computers were proposed in the 1980's (from people like Yuri Manin and Richard Feynman), slow but steady progress has been made. These advances were only accessible to quantum physicists in dedicated labs with state-of-the-art equipment. However, that all changed in May 2016 when IBM announced that it would be making a 5 qubit quantum computer available over the internet for members of the public to access and run experiments on. This is the first time that a quantum computer was made available to the general public and it has the potential to change the face of programming.

Before being able to design experiments to either run or simulate, we need to understand what makes a quantum computer different from a classical computer (such as the one you are likely reading this article on) and how quantum computers work. The math and physics behind quantum computing can be very complex and difficult to understand. However, this article will try to keep things as simple as possible and avoid as much math/physics as possible. Unfortunately, this cannot be avoided completely, so as much detail as possible with be given and some math examples worked in an attempt to make it as understandable as possible.

Quantum vs. Classical Computers

All computers today (laptops, notebooks, even cell phones) are all classical computers. They all function by using transistors as switches and operating on electrical current. When the switch is open, and no electricity is flowing, it represents a 0 bit. If the switch is closed, and electricity is flowing, it represents a 1 bit. Everything a computer is able to do, is done by operating on one or more bits at a time very quickly. At any time while the computer is running, it can be in one of $2^n$ possible states, where $n$ is the total number of bits, ranging from $00..0$ to $11..1$.

Quantum computers also have bits, called qubits (pronounced CUE-bits). The difference between a qubit and a bit is that while a bit can be either 0 or 1, a qubit can be either 0, 1, or a mixture of 0 AND 1 at the same time. When the qubit is a mixture of a 0 and 1, this is known as a superposition. This allows the quantum computer to exists in exponentially many logical states simultaneously.

By Original reproduction: Jbw2, SVG version: WhiteTimberwolf - adapted from Nanocomputers and Swarm Intelligence (page 157) ISTE, Waldner, JB (2007), ISBN 2746215160. Reproduced with author's authorization, CC BY 3.0, Link

This image is a visual interpretation of a superposition state. Image each ball is an electron who's spin can either be up (repsented by an up arrow or $\vert 1 \rangle$) or down (repsented by a down arrow or $\vert 0 \rangle$). If the spin is down it represents a binary 0 and if the spin is up it represents a binary 1. Assuming the least significant bit is to the right, the first four electrons represent 5 in binary.

However, in the second case we can see that the electron in the least significant space is in a superposition of both up and down at the same time. Once a measurement is performed, this superposition will collapse and the electron's spin will either be up or down. If the spin is measured to be up, then the second set of electrons also represents 5 in binary. If the spin is measured to be down though, then the second case represents 4 in binary.

This is part of where quantum computers get their power. By being able to have objects in multiple states at the same time.

Along with exploiting superposition, quantum computers also take advantage of another unusal feature of quantum mechanics called entanglement. When individual qubits become entangled, they can no longer be described individually; they can only be described as part of the system as a whole. There is also a correlation between entangled particles even if they are separated by immense distances. Measuring one of the qubits immediately affects the other entangled particle.

Both of these features, superposition and entanglement, have no classically analog. They are both counter-intuitive (an object existing in more than one state at the same time and separated objects have an effect on each other with nothing connecting them), but they are what give a quantum computer its power.

The Qubit

Now that we know qubits can exist in more than one state at the same time, we need some notation to represent this so we can work with them. Similar to how a classical bit can be represented by either a 0 or a 1, qubits can be represented as $|0\rangle$ (known as the "ground state") or as $|1\rangle$ (known as the "excited state"). This notation is known as Dirac's bra-ket notation. The $|0\rangle$ (or $|1\rangle$) is known as a "ket" and represents a two-dimensional column vector over the complex numbers ($\mathbb{C}^2$):

$\begin{aligned} |0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \\ |1\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \end{aligned}$

The "bra" is written as $\langle0|$ (or $\langle1|$) and represents a two-dimensional row vector over $\mathbb{C}^2$:

$\begin{aligned} \langle0| = \begin{pmatrix} 1 & 0 \end{pmatrix} \\ \langle1| = \begin{pmatrix} 0 & 1 \end{pmatrix} \end{aligned}$

However, we also need to have a way to represent a qubit when it is in a superposition (i.e. a mixture) of both $|0\rangle$ and $|1\rangle$. We do this by written a linear combination of the two states:

$\begin{aligned} a|0\rangle + b|1\rangle \end{aligned}$

Where $a$ and $b$ can be positive, negative, fractional, or even a complex number. If we take the square of the absolute value of $a$ and $b$ (that is $\lvert a \rvert^2$ and $\lvert b \rvert^2$) we get the probability of measuring either a $|0\rangle$ or $|1\rangle$, respectively. This also means that

$\begin{aligned} \lvert a \rvert^2 + \lvert b \rvert^2 = 1 \end{aligned}$

That is to say the probability of measuring a $|0\rangle$ plus the probability of measuring a $|1\rangle$ is $100\%$ (i.e. we must end up measuring either a $|0\rangle$ or $|1\rangle$, those are the only possibilities).

So, if the qubit was in a superposition where it had a $50/50$ chance of being $|0\rangle$ or $|1\rangle$ it would be represented as $\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$. In matrix form it would be:

$\begin{aligned} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{pmatrix} \end{aligned}$

Why is the value of $a$ and $b$ both equal to $\frac{1}{\sqrt{2}}$ and not $\frac{1}{2}$ if there is a $50/50$ chance of $|0\rangle$ or $|1\rangle$ being the result? Remember that $\lvert a \rvert^2 + \lvert b \rvert^2$ must equal $1$. If $a$ and $b$ were both $\frac{1}{2}$, then:

$\begin{aligned} \lvert \frac{1}{2} \rvert^2 + \lvert \frac{1}{2} \rvert^2 = \frac{1}{4} + \frac{1}{4} = \frac{2}{4} = \frac{1}{2} (\neq 1) \end{aligned}$

However, with $a$ and $b$ both equal to $\frac{1}{\sqrt{2}}$:

$\begin{aligned} \lvert \frac{1}{\sqrt{2}} \rvert^2 + \lvert \frac{1}{\sqrt{2}} \rvert^2 = \frac{1}{2} + \frac{1}{2} = \frac{2}{2} = 1 \end{aligned}$

Visualizing a Qubit

Superpositions of qubits is not something that can be easily visualized as there is nothing similar in our daily lives. In order to make it easier, a tool has been developed called a Bloch Sphere. A Bloch Sphere is exactly what it sounds like; it is a sphere with a radius of 1 and any possible state that a qubit can be in corresponds with a point on the surface of the sphere.

A Bloch Sphere looks like this:

By Glosser.ca - Own work, CC BY-SA 3.0, Link

With $|\psi\rangle$ representing the state of the qubit. With this representation, we can also describe the state of the qubit using angles and the following equation:

$\begin{aligned} |\psi\rangle = \cos(\frac{\theta}{2})|0\rangle + e^{i\phi}\sin(\frac{\theta}{2})|1\rangle = \cos(\frac{\theta}{2})|0\rangle + (\cos \phi + i\sin\phi)\sin(\frac{\theta}{2})|1\rangle \end{aligned}$

Where $0\leq\theta\leq\pi$ and $0\leq\phi<2\pi$. This notation, and representation, will help when we discuss quantum gates and how they change a qubit's state (i.e. changing the location of the qubit on the Bloch Sphere).

The $e^{i\phi}$ value is known as a phase factor. The phase factor does not have any physical meaning in of itself. That means $|\psi\rangle$ and $e^{i\phi}|\psi\rangle$ are the same. However, when measuring two quantum states that are interacting, the differences in the phase factor can sometimes be measured and have important consequences.

Conclusion

This wraps up Part I of this series. We have seen the difference between a classical and quantum computer, introduced the qubit, and how to represent/visualize a qubit for the purpose of quantum computing. In Part II we will look at how qubits can be manipulated and used to perform calculations.

Acknowledgements

I wanted to thank Dominick Marciano Sr. for their review and feedback on this series. Also, a special thank you must be given to Sean Ewington, without who this article series would not have been possible.

References

The following are a list of links for further information. Most, if not all, are contained within the article but are included here for easy reference.

History

June 26, 2017: First version

Part II: Quantum Gates

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)