Computing with Dead Cats and Dice
Computing with Dead Cats and Dice
By: Aled Catherall
Technology Lead, Defence
19th April 2017
In the last year or so, you may have come across the term “Quantum Computing”. Unless you are old enough to have used punch cards, every computer you have ever used relies on quantum mechanical effects – be it the orientation of the spin of atoms in magnetic hard drives, or the flow of electrons through the crystal lattice of silicon.
However, they are considered conventional computers which perform computations in a classical manner. So what exactly is meant by quantum computing? Why is it different to conventional computing and why is it generating so much excitement in certain circles? The answer is that quantum computing is a complete paradigm shift in the way computational problems are solved and has the potential to offer massive increases in computational speed and efficiency.
Conventional computers perform computations and store information in binary units called bits, which can be either a “1” or a “0”. Quantum computers, however, use qubits. Qubits differ from ordinary bits in that they can represent a “1”, a “0” or a complex superposition of both.
But what does this actually mean? To think of it in another way, lets visit the thought experiment devised by one of the pioneers of quantum mechanics, Erwin Schrodinger. Imagine a sealed box, and, inside this box, there is a cat. A classical interpretation is that the cat is either dead (“0”) or alive and well (“1”). In the mainstream quantum interpretation, the cat can be dead, alive, or a mixture of both dead and alive (e.g. 25% dead and 75% alive).
But don’t worry about opening the box to find a cat that is barely hanging on in there – fortunately, the act of opening the box and observing the cat forces it to be either alive or dead, and not a combination of both.
This is because quantum systems shouldn’t be thought of as exact entities, but rather as probability distributions, where all possible states exist to some degree or another. When the quantum system is examined, it reveals itself in a particular state with a certain probability (and uncertainty).
Ok, great, fantastic! So how is a cat, which you can’t actually observe, of use to anybody? As it turns out, this can be surprisingly useful for solving certain types of problems.
Take the travelling salesman problem for example – the salesman needs to visit N separate destinations and needs to determine the optimal route to take. This could be achieved through brute force by examining all possible route permutations. However, the problem with this is that by the time N reaches 60, there are more permutations than atoms in the universe, which makes this approach far too difficult for conventional computers.
More efficient techniques are available to find the best route, but even these tend to become impractical for most computers as N approaches a few hundred. For larger problems (e.g. the optimal circuit design for an integrated circuit containing millions of components), conventional computers have to rely on heuristic and approximate algorithms. These will yield good, but not optimal answers. A quantum computer, using qubits, however, could simultaneously examine all possible routes and, in very few computations, find the optimum. This relies on the fact that quantum systems like to relax to their lowest energy configuration and can use mysterious processes such as quantum tunnelling to avoid having to climb over a nearby higher energy state in order to reach a lower energy state that is further away.
In a sense, quantum computers can be thought of as massively parallel. They can compute millions of calculations simultaneously as opposed to sequentially, one at a time, as conventional computers do. So, is quantum computing going to revolutionise computing?
Quantum computers, as we currently understand them, are only beneficial for solving certain types of problems where the inherent parallelism are beneficial – typically those that can be expressed in terms of minimising some energy function or searching for a match. We know that they should excel at prime factorisation (basically breaking modern encryption), route optimisation and database searching. However, for problems which cannot be expressed in an appropriate manner (e.g. those which require iterative calculations), their benefit over conventional computers will be limited if at all.
Another problem with quantum computers is that they rely on a property called “entanglement”. This is where spatially separated particles are highly correlated (“spooky action at a distance” according to Einstein). Maintaining high correlation requires very cold temperatures – typically requiring a bath of liquid helium, which is a resource not generally available in most workplaces. However, with the advent of cloud computing, there will no doubt be providers of quantum cloud computing in the future to save you the hassle of acquiring liquid helium.
Furthermore, to Einstein’s disbelief, God does, in fact, play dice. What does this mean? An algorithm on a conventional computer will always give the same output when given the same input, regardless of how many times you run it. You can always predict what the outcome will be for a given set of inputs – i.e. it is deterministic.
However, things are far murkier in the world of quantum mechanics. An algorithm on a quantum computer will sometimes give you the right answer, and will also sometimes give you the wrong answer. It may even give a different answer each time you run the algorithm. There is a degree of chance in the final state that the qubits will relax to and it cannot be pre-determined based on the input.
The statistical distribution of the output from many runs can be predicted, but not the output from a single run. Therefore, you need to run a quantum algorithm multiple times and review the outputs before settling on what you believe to be the correct answer. This reduces some of the efficiency benefits and could be problematic where precise solutions are required. It may also give software engineers headaches – how do you debug and benchmark code which can’t be relied upon to give a consistent output?
So, to answer the question of whether or not quantum computers will revolutionise computing – the answer is yes, no, and a mixture of both yes and no (sorry!).
Nevertheless, technology companies such as us should take notice of developments in areas such as quantum computing. The pace of technological change in the modern world is rapid and accelerating. We need to be proactive rather than reactive to the emergence of new technologies and processes, and not be afraid to embrace them if we wish to remain relevant and competitive.