Quantum Computers - What are they, and what can they do?
A Quick Guide to Quantum Computers.
Simon Juba
Moore’s Law is a computing observation that claims that we can expect the speed and capability of our computers to increase predictably every two years while paying less and less for them. The trend in computing technology has continued to follow this observation for the last 60 years, but experts agree that computers are approaching and should reach the physical limits of this law at some point in the 2020s.
What this means is that unless a fundamental change in computing technology is realized, we will struggle to see significant improvements to computing power in the next few decades. This change has to be in the order of magnitude of the transition from vacuum tubes to transistors we saw in the 1950s.
What are Quantum computers?
This is where quantum computing comes in. This is a new a type of computing technology that uses the principles of quantum mechanics: superposition and entanglement, to perform calculations. Quantum superposition states that a quantum system can exist in multiple states or positions simultaneously until it is measured, at which point it “collapses” into one of those states. Entanglement, on the other hand, refers to the correlation between the states of two or more quantum objects, such that the state of one object is dependent on the state of the other(s) even when the objects are separated by great distances.
Unlike classical computers, which use bits (binary digits) to represent information, quantum computers use qubits (quantum bits) which can exist in multiple states at once, enabling them to perform certain types of calculations much faster than classical computers. Thanks to the superposition of their states, n number of qubits can be used to represent 2ⁿ different states as opposed to just n states in the case of classical computers.
While a classical bit can be 0 or 1 at any given point, qubits can exit as a combination of 0 and 1 and, when measured, collapse to one of the states based on probabilities determined by the constants ⍺ and β.
This increased amount of information they can represent enables them to achieve computing speeds exponentially better than the current standards giving them the potential to solve certain types of problems much faster than classical computers. They are of particular interest in the areas of cryptography, optimization, and simulation.
What can we do with them?
There are numerous ways researchers are hoping to utilize these computers, but there are two fundament quantum algorithms of huge importance in the quantum field.
The first one is Shor’s algorithm; capable of finding prime factors of large integers in polynomial time. This has the potential to break public-key cryptography schemes, such as RSA, on which internet security is heavily reliant. The second one is Grover’s algorithm, used in the linear search of unstructured data; this has possible benefits in improving database search speeds, among other search tasks. Both these algorithms are exponential and quadratically faster than the best possible counterparts using the current computing technologies.
I got to learn a bit about quantum computers during my university days and I found it both fascinating and incredibly complex. It was definitely hard to explain to my friends, but I found the amplitude amplification method used in Grover’s search algorithm quite intuitive, so I will attempt to introduce it in this article.
The problem definition.
Let us consider the task of locating a particular item in an unordered list of N items. In the classical approach, you would look at each item individually and check if it matches what you are looking for until you find the target. In the worst-case scenario, the target is at the back of the line, and you have to visit all N items before finding the target; this is expressed as a linear time complexity of O(N). Grover’s algorithm, on the other hand, finds the solution with high probability in O(√N). This might not seem like much when dealing with small figures but it becomes quite significant as we scale up to larger numbers.
Grover’s algorithm.
The amplitude amplification algorithm is visualized below and follows the following steps:
Initialization : We first create a superposition of all possible states with equal amplitude, this means we create an equal chance of measuring any of the states. We will map the items in the list to one of the states a qubit can hold.
Oracle : We then utilize an especially designed black box called an oracle whose purpose is to flip a state’s amplitude to negative if a state is our target or otherwise leave it unchanged. This has the effect of marking the target as different from the rest but not yet noticeable.
Amplification : We then calculate the average amplitude of all the states and flip each of their amplitudes about the mean. This has the net effect of amplifying the target while diminishing the amplitutes of the rest of the states. This makes it more likey to land on the target when measuring.
Repeat : We then repeat the above 2 steps until we have a high enough probability of measuring the target. For a large enough number of states N this requires on average √N repetitions.
Measure : After an appropriate amount of repetitions, we then measure the circuit with the resultant final state returning the correct solution with near-certainty.
Interesting applications.
Travelling salesman problem.
The Travelling Salesman Problem (TSP) describes a salesman who must travel between N cities. The order in which he does so is something he does not care about, as long as he visits each once during his trip and finishes where he was at first. Each city is connected to another close by towns, nodes, aeroplanes, or roads or railway. The idea is to find the fastest, cheapest and less expensive way to reach those cities.
The simple example of the TSP can be used to describe many situations, such as the optimization of electric wiring or business scheduling. This is typical of a large “hard” optimisation class defined in the 1800s based on finding a Hamiltonian cycle. Although not the most efficient solution, a quantum heuristic algorithm based on Grover’s algorithm was proposed as a way to solve the TSP.
The collision problem.
The collision problem is a fundamental problem in computer science that involves finding two inputs that produce the same output when passed through a hash function. Given a hash function h(x) that maps an input x to an output in a finite range, the collision problem is to find two distinct inputs x and y such that h(x) = h(y).
The problem is complex and challenging to understand, but in quantum computing, the Brasard-Hoyer-Tappar algorithm or BHT algorithm is a quantum algorithm capable of solving the collision problem.
Wrapping up.
Quantum computing technology is quite promising but it is far from being perfected. For instance, despite all the research that has gone into the field over the last decade, the largest quantum machine available today — the Osprey chip, announced in November 2022 by IBM — has 433 qubits. In contrast, researchers say it might take one million plus qubits to crack RSA using a method like Shor’s algorithm for factoring large numbers.
Despite the massive size of these machines at around 3 meters in height, their beating heart is a processor the size of a small coin. So what makes up the rest of these towering machines? Well, each of these processors requires an extreme amount of cooling, being housed in a dilution refrigerator that gets to a temperature of around 10 to 15 milli-Kelvin, which is roughly -273 °C and the technology and physics required to maintain these temperatures are both expensive and incredibly challenging.
Building and maintaining qubits in the required environment is, therefore not an easy task and it will be a while before you can use these machines for your gaming or programming purposes but I am excited to see how the technology develops in the coming years.
If you are curious enough to learn more and try out this new technology, you can head over to the Qiskit website for detailed tutorials and documentation on one of the more popular quantum programming languages out there.
At HENNGE, we are looking for software engineers to join our Cloud Product Research and Development Team. To find out about more opportunities at HENNGE, check out our recruiting site.