Quantum Computing, Part I
Posted by on Saturday, April 16, 2016
I awoke this morning to a flood of emails and direct messages from people forwarding a link to a news video. By now most of you (or at least those living in Canada) will have also seen this video, in which the new Prime Minister of Canada is shown excitedly explaining quantum computing to journalists during a visit to the Perimeter Institute this week. In a world in which politicians increasingly ignore science, or in some cases actively wage a war against science, it is a hopeful sign that we now have a leader who not only respects science, but is excited by it!
It also lead to a few people asking me to provide more information on quantum computing, although I must admit that the explanations accompanying the video are already quite good and surprisingly accurate. However I will do my best to expand on this topic.
Normal (or classic) computing works on Boolean logic. Your desktop, laptop, tablet, cell phone, and most of your household appliances work by storing many trillions of individuals bits of data, each bit being a 1 or a 0 (or true or false), and then systematically operating on each bit. A modern computer can process billions of bits of information every second, making them very efficient for nearly every calculation that a person might ever want or need to do. But it still can only work with one set of data at a time.
A quantum computer works in an entirely different way. In a quantum computer, each bit is a mixture of a true and false state. A bit might be 20% true and 80% false. And only when the calculations are completed does it become definitely true or definitely false. At first glance this would seem to be less efficient, since there is a random component to the output instead of definite deterministic results, but it actually has an important benefit.
Because each bit can be a mixture of both true and false, each calculation that is performed can process both cases. A quantum computer can effectively divide itself into multiple virtual copies of itself, each performing calculations simultaneously, and then recombining into a single real computer to output the results. A quantum computer, if applied to the right kind of problem, can act as hundreds or thousands of classical computers operating in parallel.
Consider as an example the problem of calculating which prime numbers divide a given integer. In a normal computer, this is done by taking a list of all the prime numbers less than the given integer, and then the CPU divides the integer by the first prime in the list. If the integer is divisible by that prime number, then it is sent out as a prime divisor. Then the CPU takes the second prime number in the list and tries it. And then when that calculation is completed it takes the third prime in the list, and divides the integer by that number. And it keeps doing this, one prime number at a time, until all the prime numbers have been tested.
My desktop computer can test a few million prime numbers per second using this method, so it is efficient enough for most applications. However many encryption methods which are currently used online require testing trillions or even thousands of trillions of prime numbers in order to crack them. That means that my desktop computer, working non-stop on just this problem with no other tasks, would not be able to crack even the simplest such encryptions for several decades. Many of the RSA encryptions would not be cracked in billions of years!
However a quantum computer operates differently. A quantum computer can effectively create a few thousand or even a few million virtual copies of itself. Each virtual copy is assigned a much shorter list of prime numbers - maybe just a single prime - and then each virtual copy divides the original integer by its prime number. Any virtual computer that does not contain a prime divisor vanishes, and then the quantum computer is left containing only the prime divisors of the original integer. In a perfect world these could be read out from the quantum computer, and the integer that would take decades to factor on my desktop computer would be factorized in just seconds on a quantum computer.
I must add a disclaimer here that for simplicity of understanding the ideas of a quantum computer, I have greatly simplified the technical challenges. In practice, a quantum computer does not output a definite answer as in the classical case but instead has probabilities of producing each right answer. So you would be told that there is a good chance that the prime number you are given is a factor, but it is not certain. And where a classical computer can generate all of the prime factors on one run through, a quantum computer outputs a randomly chosen prime factor, and must be run multiple times to get them all.
So that is the (hopefully) simple explanation of why quantum computers are so interesting, and why they have the potential to open up new fields of science and computing. Unfortunately they also have several technical challenges, which I will cover in my next article.
It also lead to a few people asking me to provide more information on quantum computing, although I must admit that the explanations accompanying the video are already quite good and surprisingly accurate. However I will do my best to expand on this topic.
Normal (or classic) computing works on Boolean logic. Your desktop, laptop, tablet, cell phone, and most of your household appliances work by storing many trillions of individuals bits of data, each bit being a 1 or a 0 (or true or false), and then systematically operating on each bit. A modern computer can process billions of bits of information every second, making them very efficient for nearly every calculation that a person might ever want or need to do. But it still can only work with one set of data at a time.
A quantum computer works in an entirely different way. In a quantum computer, each bit is a mixture of a true and false state. A bit might be 20% true and 80% false. And only when the calculations are completed does it become definitely true or definitely false. At first glance this would seem to be less efficient, since there is a random component to the output instead of definite deterministic results, but it actually has an important benefit.
Because each bit can be a mixture of both true and false, each calculation that is performed can process both cases. A quantum computer can effectively divide itself into multiple virtual copies of itself, each performing calculations simultaneously, and then recombining into a single real computer to output the results. A quantum computer, if applied to the right kind of problem, can act as hundreds or thousands of classical computers operating in parallel.
Consider as an example the problem of calculating which prime numbers divide a given integer. In a normal computer, this is done by taking a list of all the prime numbers less than the given integer, and then the CPU divides the integer by the first prime in the list. If the integer is divisible by that prime number, then it is sent out as a prime divisor. Then the CPU takes the second prime number in the list and tries it. And then when that calculation is completed it takes the third prime in the list, and divides the integer by that number. And it keeps doing this, one prime number at a time, until all the prime numbers have been tested.
My desktop computer can test a few million prime numbers per second using this method, so it is efficient enough for most applications. However many encryption methods which are currently used online require testing trillions or even thousands of trillions of prime numbers in order to crack them. That means that my desktop computer, working non-stop on just this problem with no other tasks, would not be able to crack even the simplest such encryptions for several decades. Many of the RSA encryptions would not be cracked in billions of years!
However a quantum computer operates differently. A quantum computer can effectively create a few thousand or even a few million virtual copies of itself. Each virtual copy is assigned a much shorter list of prime numbers - maybe just a single prime - and then each virtual copy divides the original integer by its prime number. Any virtual computer that does not contain a prime divisor vanishes, and then the quantum computer is left containing only the prime divisors of the original integer. In a perfect world these could be read out from the quantum computer, and the integer that would take decades to factor on my desktop computer would be factorized in just seconds on a quantum computer.
I must add a disclaimer here that for simplicity of understanding the ideas of a quantum computer, I have greatly simplified the technical challenges. In practice, a quantum computer does not output a definite answer as in the classical case but instead has probabilities of producing each right answer. So you would be told that there is a good chance that the prime number you are given is a factor, but it is not certain. And where a classical computer can generate all of the prime factors on one run through, a quantum computer outputs a randomly chosen prime factor, and must be run multiple times to get them all.
So that is the (hopefully) simple explanation of why quantum computers are so interesting, and why they have the potential to open up new fields of science and computing. Unfortunately they also have several technical challenges, which I will cover in my next article.
I am a theoretical physicist & mathematician, with training in electronics, programming, robotics, and a number of other related fields.
