I am a Quantum Computing Sceptic.
But last week at Dalhousie I met Jordan Kyriakidis who explained one feature of Quantum Computing that I had not appreciated. That even if a quantum computer only gave the right answer one time in a million operations, it might still be useful.
His insight made me believe that Quantum Computing just might be possible.
[Please be aware that I am not an expert in this field. And I am aware that experts are less sceptical than I am. Indeed many consider that the power of quantum computing has already been demonstrated. Additionally Scott Arronson argues persuasively (in his point 7) that my insight is wrong.]
Conventional digital computers solve problems using mathematics. They have been engineered to perform electronic operations on representations of numbers which closely mimic equivalent mathematical operations.
Quantum computers are different. They work by creating a physical analogue of the problem which requires solving.
An initial state is created and then the computational ‘engine’ is allowed to evolve using basic physical laws and hopefully arrive at a state which represents a solution to the problem at hand.
There are many conceivable implementations of a quantum computer and I am sceptical about them all!
My scepticism arises from the analogue nature of the computation. At some point the essential elements of the quantum computer (called ‘Qubits‘ and pronounced Q-bits) can be considered as some kind of oscillator.
The output of the computer – the answer – depends on interference between the Qubits being orchestrated in a precise manner. And this interference between the Qubits is completely analogue.
Analogue versus digital
Physics is fundamentally analogue. So, for example, the voltages present throughout a digital computer vary between 0 volts and 5 volts. However the engineering genius of digital electronics is that it produces voltages that are either relatively close to 0 volts, or relatively close to 5 volts. This allows the voltages to be interpreted unambiguously as representing either a binary ‘1’ or ‘0’. This is why digital computers produce exactly the same output every time they run.
Quantum Computing has outputs that can be interpreted unambiguously as representing either a binary ‘1’ or ‘0’. However the operation of the machine is intrinsically analogue. So tiny perturbations that accumulate between the thousands of operations on the Qubits in a useful machine will result in different outputs each time the machine is run.
To my surprise Jordan acknowledged my analysis was kind-of-not-wrong. But he said it didn’t matter for the kinds of problems quantum computers might be good at solving. The classic problem is factoring of large numbers.
For example working out that the number 1379 is the result of multiplying 7 × 197 will take you a little work. But if I gave you the numbers 7 and 197 and asked you to multiply them, you could do that straightforwardly.
Finding the factors of large numbers (100 digits or more) is hard and slow – potentially taking the most powerful computers on Earth hundreds of years to determine. But multiplying two numbers – even very large numbers – together is easy and quick on even a small computer.
So even if a quantum computer attempting to find factors of a large number were only right one time in a million operations – that would be really useful! Since the answers are are easy to check, we can sort through them and get rid of the wrong answers easily.
So a quantum computer could reduce the time to factor large numbers even though it was wrong 99.9999% of the time!
I can easily imagine quantum computers being mostly wrong and I had thought that would be fatal. But Jordan made me realise that might still be very useful.
Thanks Jordan 🙂
By the way, you might like to check out this web site which will factor large numbers for you. I learned that the number derived from birth date (29/12/1959>>>29121959) is prime!
Tags: Quantum Computing