Quantum computers offer us a tantalizing vision of our future. They will provide the future with high-performance computing and perhaps, will even replace classical computers. Despite the promise, they are neither widely available or in fact useful, as yet. Let’s delve into computer sciences’ “spooky” future, maybe.
In the following article, we’ll explore what they are, a little of their history, potential applications and of course we’ll address their potential short givings. A full appraisal of this field is clearly out the scope of the following text but let’s take a brief look at this potentially groundbreaking technology.
I am “da” law
In 1947 a bold prediction was made by Howard Aiken. He stated that “just six electronic digital computers would satisfy the computing needs of the United States”. Jump forward seventy years and we can see, clearly, this was somewhat of an understatement. Our hunger for knowledge and processing speed has clearly far exceeded this modest estimation. Aiken could never have predicted the amount of data processing required for the modern world. From the advent of the internet, gaming and of course the advent of social media, we can forgive such a low estimate.
Moore’s Law states, we paraphrase, that the number of transistors (or power) on microprocessors will double every 18 months and microprocessors between 2020 and 2030 will find circuits on a microprocessor that will be measured on the atomic scale. Holy cow! Clearly, this will require us to make a genuine, ahem, quantum leap, in technology. Logically this will require quantum computers harnessing the quantum “power” of atoms and molecules to perform processing and memory tasks.
Quantum computers would, potentially, provide the enhanced computing power needed that will vastly outstrip current silicon-based computers. Sounds great right? Hold your horses there “fella”, if only everything was that simple. Quantum computers may not be the cure-all we are led to believe.
[Image source: Pixabay]
Quantum computers: What are they?
You probably already have an idea about these devices but let’s start with a definition:-
“A computer which makes use of the quantum states of subatomic particles to store information.” – English Oxford Dictionary
Well, that tells us everything we need to know right? Great, you can skip the rest of the article.
Still here? Good for you, for those of us with a more enquiring mind let’s dig a little deeper…
Basic quantum computers have already been built to perform basic calculations. Actual practical examples are, sadly, years away. The origins of these mystical machines have been around for the most of the 20th Century. Quantum computers were first theorized about 30 years ago by Paul Benioff of the Argonne National Laboratory. He first theorized quantum theory as applied to computers in 1981. He suggested that we could create a Turing machine operating on the quantum scale. As a matter of fact, the computing device you are using right now is based on the Turing machine!
[Image source: Wikimedia Commons]
Turing you magnificent (insert expletive)
Alan Turing developed his famous machine in the 1930’s. This was (is) a theoretical device that consists of a never-ending tape divided into discrete portions or squares. Each segment held a value of 1 or 0, or of course was left blank. The tape is read by a device that translates the “code” to provide a set of instructions. We know this today as binary. This is, somewhat selling ourselves short as it turns out, well in theory.
In a quantum “upgrade” of this device, the “tape” exists in a quantum state, as does the reading device. This means that the machine can read either the values 1 or 0 or a superposition of 1 and 0. Superposition you say? Well, my friend that simply means you can read either 1 or 0 or any point in between the two or both. Oh and at the same time “to boot”!
Owing to the phenomena that a quantum computer can contain multiple states simultaneously, they have the potential to be orders of magnitude more powerful than conventional computers.
How quantum computers work
Quantum computing is, in essence, the fact that in the quantum realm things aren’t as clear-cut as you’d expect in our macroscopic world. Subatomic particles like electrons and photons can simultaneously exist in states that we would normally deem mutually exclusive. They can, in effect, be in several places at once. In the case of photons, for example, they could exhibit two kinds of polarization. In our everyday life we never actually observe this kind of superposition due to the phenomena described by Erwin Schrödinger and his sadistic habit of putting cats in boxes. Bad Schrödinger!
The strange and as yet unexplained elimination of superposition once you observe the system, for instance, when you attempt to measure the location of an electron, offers fantastic potential for computing. Superposition effectively liberates us from binary constraints. Quantum computers, in theory at least, take advantage of superposition.
You might think that this could be achieved with traditional physics, even using two ordinary bits simultaneously. If this was the case then quantum computers aren’t that impressive, right? In a system with more than one qubit, you need to remember that each individual component isn’t actually independent from the next. They are, in fact, entangled. When you measure or observe one of two qubits that are entangled you get one value. But…. you also, simultaneously get the value of the other. The particles don’t even need to be in the same place. Einstein once called entanglement “spooky action at a distance”. The following video from Veritasium gives us a good overview of quantum computers, enjoy.
Building the machine
Building a quantum computer will be no easy task. Although building traditional bits in classical computers is second nature to us now, producing qubits is far from easy.
We are not yet sure what the best way to make a qubit, as yet. Techniques vary from trapping ions, electrons or other subatomic particles. Others propose the use of superconductors to make microscopic quantum circuits. Others have suggested using photons and complex optical apparatus to produce the requiring “hardware”.
Whichever route we go down, or even a combination of all three, they all share something very important. They are all currently plausible on the small scale but are difficult to realize on a large scale. Until this issue is solved quantum computers are currently limited.
The main hurdle to overcome is something called quantum decoherence. Quantum systems will, in essence, need to be isolated from the rest of the world around it to work. Any tiny interactions will cause the entire system to decohere and collapse down to a binary state. This isn’t just limited to the main system but also its gubbins. Quantum gates, nuclear spins of qubits and lattice vibrations, for example, can also introduce decoherence effects. Ah man, so how could we solve this? Well, we could decide on an acceptable error rate, or rather, the amount of decoherence we are happy to “live with”. Then design the rest from there.
Although not a perfect solution even with small error rate we still get the bigger benefit of the quantum computer. It’s a trade off.
Entanglement means you can’t simply string together the descriptions of the individual qubits. You need to describe all the correlations between them. As you increase the number of qubits the relative correlations increase exponentially. For n number of qubits, the correlations grow exponentially. This means it quickly “explodes”. If you wanted to describe a system of just 300 qubits you’ll reach a number of possible correlations that exceeds the number of atoms in the known visible universe! Holy cow.
Can you imagine a number of possibilities that big? You simply couldn’t cope with “writing down” the information contained in such a system using classical bits. A computer running on qubits could perform tasks a classical digital computer could probably never hope to achieve. The potential is enormous and exciting.
Sounds fantastical right? There is, however, a problem. Any “reader” or algorithm would take data from superpositioned qubits as input. But the output would also be in a quantum state. Such information will also change as you attempt to observe it! “Nature pulls a trick here,” says Richard Jozsa, a pioneer of quantum computing at the University of Cambridge.
“She updates a quantum state, but then she doesn’t allow you to get all the information.”
Quantum computing’s solution is to provide methods of gaining as much information as possible from the unobservable.
Lead by example
Any computational device relies on algorithms to make calculations and follow programs. Richard Jozsa and David Deutsch have developed an example of an algorithm for quantum computers. Its task is a little odd but bear with us. To help explain let’s imagine a line of people waiting to enter a gate with a limited capacity venue. Overseeing the entrance is a beefy security guard who will allow your entry simply based on your pre-assigned wristband. Each wristband has strings of three 0’s or 1’s.
There are 8 people in the queue or two to the power of 3. Each of the “guests” has a unique string of 0’s and 1’s on their respective wristbands. The guard records his decisions by allocating a 1 to a particular bit-string if he decides to let someone in or a 0 if he won’t. This is called a boolean function, which is a rule that assigns a 0 or 1 to a bit string. They are the staple of computer science.
We don’t know what the guard will decide for each person but we do know that he is set in his ways. He will either let everybody in or he will let exactly half the people in. Your task is not to find what happens to each person but whether the guard is in a good mood and lets everyone in or just half of them. So, how many values of the guard’s boolean function do we need to look up to find which mood the guard is in?
Keep on looking
A classical computer would need to look at the wristbands at least five times to get an idea of the eventual decision. Even if you looked at the first four wristbands and they had a 1 on them you can’t be sure if that represents just half or all of the people waiting. You’ll need, therefore, a fifth wristband value. With a quantum computer, you can look up the values for all eight simultaneously and only need one lookup function.
“For the cost of running the program once with this funny superposition input, you have somehow computed all the [values at once],” explains Jozsa.
The advantage of quantum computers over classical ones is even more apparent when there are more and more people in our example above. With a line of 2n individuals and a classical computer would need 2n-1+1 times. This would grow exponentially, as you can imagine. A quantum computer only needs to do this once.
As previously mentioned, there is an issue we need to overcome with quantum computers and our above scenario. Your eight simultaneously looked up values will be encoded in a quantum state that we can’t read directly. Any measurement of the values would disturb them. Thankfully for us though, we are not trying to find out what will happen to each individual. We only need to find out if the guard is in a good or bad mood.
“That’s only one yes-no question,” explains Jozsa. “It’s a small amount of information about a lot of values.”
[Image Source: Pixabay]
House of cards
Jozsa and Deutsch show us that there is a possibility of performing an extra operation on our quantum state data. A step that teases the simple piece of information we are after into just the right places where we can read them. It’s a little like a house of cards that will collapse as soon as you look at it. We can never see it in its full glory, but, if it was constructed in just the right way, we would be able to rebuild it from the collapsed heap.
Even simple patterns or structures in systems of multiple components of a classical computer often have no choice but to evaluate all, well many, of the components individually. A quantum computer doesn’t, it can evaluate all of them at the same time. Although you can’t read all values individually you can extract enough information to get the bigger picture.
Jozsa and Deutsch developed this algorithm in 1992. It was the first that could be proven to work much faster than any previous algorithm designed for the same task. More interestingly these two gentlemen are not quantum engineers toiling in a lab but theorists. Their worked combined mathematical formalism for quantum mechanics and theoretical computing to find out what they can both achieve. This is currently purely theoretical as we haven’t yet built a fully fledged machine.
Will quantum computers replace classical computers?
For all the hype and mental elbow grease being applied to this technology, it may all be fruitless in the end. We may not be able to tell if the quantum computer’s calculation results are even producing the correct answer. Eh? How so?
Quantum computers could make calculations in days or hours that would take a regular computer thousands of years to complete. Some answers it produces will be verifiable, like say a complicated cryptographic key could be checked by using it (encrypting and decrypting a message say). But others might well have to be taken “on faith”. In essence, quantum computers are likely to be used for complex problems that we simply won’t be able to have a confirmation method. How would we double check the calculations and results?
[Image source: Pixabay]
Scientists at the University of Vienna have quantum computers’ back, however. They have developed a technique called “blind quantum computing” that might be able to help. It’s pretty simple and involves mathematical traps which are intermediate steps in the calculation, which can be predicted prior to running the calculation. If these predicted traps don’t match the actual result at that stage, then there is something wrong with the whole process. So instead of checking the whole process we simply “sample” it at points. A bit like quality control in a production line.
This team demonstrated that the technique can work, at least, on the small scale using four-qubit systems. These smaller units can be used to verify larger secondary or main computers. The team also claims these can be scalable and could be used on computers with hundreds of qubits. There is a snag, however:-
“Like almost all current quantum computing experiments, this currently has the status of a fun demonstration proof of concept, rather than anything that’s directly useful yet,” explained Scott Aaronson at the Massachusetts Institute of Technology.
Is it on?
The problem isn’t just verifying the results but also finding out if the machine is working in the first place. Currently available “quantum computers” haven’t actually been verified as working the way they are supposed to. They are, in effect, based on theory, hoping it works and judging the outputs.
This obviously raises a whole “truckload” of issues. Primarily, attaining the output can be messy. Coding the machine is also very difficult. By their very nature, quantum computers provide answers that are probabilistic rather than definite or absolute. This could mean that for many solutions the answer may not necessarily be correct and we would need to repeat it several times. Rinse and repeat until the “correct” answer is clear. Sounds a little like divination of old.
This means then, that depending on the problem, there may not be a huge advantage in using a quantum computer over a conventional one. Exploitation of the power of quantum mechanics would certainly improve the speed with which we gather solutions. To date, researchers have only been able to do this for a very small set of problems. For instance, finding prime factors of very large numbers. Pretty cool, if you like that sort of thing, and very useful for cryptography, but that’s a little limited.
If we could ever build fully fledged quantum computers, they will be invaluable for factoring large numbers and great for decoding and encoding messages, for example. If we could build one today, information on the internet’s security would be seriously compromised. Our current methods of encryption would not be fit for purpose compared to the decryption capabilities of quantum computing.
Database searching and querying would be performed in a fraction of the time it takes conventional computers to perform the same tasks. Quantum computers could also, of course, be used to help drive our understanding of quantum mechanics and design future improved quantum computers.
This field is still very much in its infancy and many scientists believe a functional one is years away. Useful machines must be at least several dozen qubits to be able to solve real-world issues and, therefore, be viable.
If we can figure out what to actually make qubits from, work out how to protect the machine from outside world interference, manage to verify the machine is functioning and make sense of the outputs, these computers will certainly offer us some interesting abilities in the future. If that wasn’t enough we will likely need checkers or “breaks” to verify the calculations are running as they should and improve our confidence in the final output. So, no pressure then.
In the first instance, we will probably see quantum computers replacing conventional machines for tasks like encryption and coded messages. They will probably have places in other forms of security such as forms of keys, perhaps for cars and our homes. A full-scale replacement of conventional computers is probably unlikely. Whatever the future holds quantum computers will likely form a not insignificant part.