Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I'm currently reading a book (and a lot of wikipedia) about quantum physics and I've yet to understand how a quantum computer can be faster than the computers we have today.
How can a quantum computer solve a problem in sub-exponential time that a classic computer can only solve in exponential time?
A quantum computer by itself isn't faster. Instead, it has a different model of computation. In this model, there are algorithms for certain (not all!) problems, which are asymptotically faster than the fastest possible (or fastest known, for some problems) classical algorithms.
I recommend reading The Limits of Quantum by Scott Aaronson: it's a short popular article explaining just what we can expect from quantum computers.
The basic idea is that quantum devices can be in several states at the same time. Typically, a particle can have its spin up and down at the same time. This is called superposition. If you combine n particle, you can have something that can superpose $2^n$ states. Then, if you manage to extend, say, bolean operations to superposed states (or superposed symbols) you can do several computations at the same time. This has constraints but can speed up some algorithms. One major physical problem is that it is harder to maintain superposition on larger systems.
its an open problem subject to cutting edge research whether quantum algorithms will ever be faster than "classical" algorithms both on the theoretical and applied levels. in complexity theory it is reflected in the question eg BQP =? P ie whether quantum computing "P" class is equivalent or not to the classical P (Polynomial time) class & there are many other related open questions.
there is one very intriguing & significant datapoint: the award-winning Shors algorithm factors numbers in P quantum time, but it is still not known whether there exists a P-time classical factoring algorithm.
a new direction over last few years is work in adiabatic quantum computing which is easier to implement/engineer than other standard methods involving qbit transport (but yet still extremely difficult to implement).
the only quantum computer(s) ever built to date is by Dwave systems and is currently subject to intense scientific scrutiny and controversy regarding its actual quantum effects & performance; it is very expensive and basically does not outperform a desktop computer, when the classical code is fully (human-/hand-) optimized. however it can be fairly stated no other corporate, government, or university research entities appear to be anywhere close to their level of applied/technical/engineering advancement so far.
the scientific outlook is cloudy at the moment & some scientific experts/critics/skeptics eg Dyakonov have long believed/argue strongly that scalable QM computers will never materialize due to insurmountable technical difficulties and/or barriers.
Think of it this way: There are problems that can be solved by solving a whole lot of individual sub-cases [example: factoring by trial division]. These problems take a long time to solve if one has to solve the sub-cases one after another. They can be solved much faster if one can provide enough hardware to solve all of the sub-cases in parallel, but that is not practical because the amount of hardware needed increases with the problem size. Quantum computing exploits the superposition-of-states feature of Quantum Mechanics to simulate providing enough hardware - i.e each state in the superposition is 'the machine' for one of the sub-cases. Note that this simulation is done NOT by software, but by Nature itself.
(Note: my English might be insufficient at some points. Sorry if it's distracting.)
A good analogy of how they work would be this seemingly unrelated video. We see salt particles on a limited flat surface, navigating themselves into a certain pattern when they "hear" a sound with a specific wavelength. (It's all about the small integer ratios of the wavelength and the plane size; much like steady Lissajous curves, or chords in music.) The point is, they move around until they reach a state where they "like to stay".
Quantum Computers, according to their believers (and to the best of my knowledge), work similarly. They are a network of qbits taking every possible state (at once!) but they only get stable in a certain constellation - the one that satisfies your criteria. Then you go read their final state, and it should be the answer itself, or one of the likely answers. It's as if you calculated all points of a curve with the salt-and-sound method. Classical computers would do this like a particle emulator where you'd have to calculate every grain of salt; with this sound wave thing, you get an instant answer because salt is "everywhere" at the beginning, just as qbit states.
And this is nice - in theory.
The problem is, you can't communicate with quantum bits. I mean, not really. Physicists have a theory, merely a theory, that such thing as superposition even exists. It's not a thing, it's an attempt to explain something we don't know. It's a method of working with unsure data. It's like saying "until you solve this equation, x has all the possible values, and then it suddenly collapses and takes on only one". Sure, it's one way to look at things; but it's not reality itself, it's just a side effect of missing information. If you already know x and I don't, then only I will have this uncertainty, and x, in fact, has a very specific value all along.
The same is true for quantum entanglement. According to the mainstream theory, when you observe one of the pairs, you gain instant information of the other. This sounds like magic, but it's like a pair of gloves: if we put them in two bags, then we both take one of the bags (random) and travel to the opposite ends of the galaxy, you will still know that if you have the left one in yours, then the right one was in mine. No information travels thru spacetime, nothing happens, only we know something on both sides - as soon as we "make the glove function collapse", aka check the bag. Yes, they say there's a wave function that collapses when you observe an entity; but again, this is not how it is, it's how we imagine it might as well be.
There's the very concept of superposition, somethng being in more than one state at the same time, that's constantly being referred to and is already too much for common sense. It all goes back to the Copenhagen Interpretation, with a lot of debate around it, and honestly I'll open a champagne when they finally admit there's a better explanation. Even Schrödinger himself insisted that the probability approach to the poor cat's wellbeing is just wrong; it was a disproval of an explanation attempt, he said "guys, this must be false because it leads to a contradiction in this simple thought experiment, the cat is dead and alive which is impossible"; instead, they accepted the impossible. Multiple values for the same thing at the same time. Against the very reason to use variables in the first place - to have one exact meaning. Against the concept of proving or disproving theorems where two values for x means your statement is wrong.
However crazy this may sound, however you want to believe "they didn't give all that money for nothing" and "big companies know what they're doing" - superposition is probably a misunderstanding, and quantum computers will probably fail to deliver anything reliable. Also they're very-very specific to a problem, you have to rewire them each time you want to add different numbers together, and even then, it's a very unstable way. It's like calculating the ratio of two numbers by cutting a plane to the right size, put salt on it, and then turn up the music.
A quantum system is a system that exists in a quantum state(s) at different probabilities determined by environmental constraints. Assuming that a quantum computer contains all the states of an n-bit quantum system the extraction of one of these states collapses the system to one of the states. This is akin to a hash function using O(1) to search for a bucket without iteration. Two things are needed, quantum storage of the n-bit systems and a hash-like function to collapse the state that is needed. The constrains play the role of different hashing functions for collapsing the n-bit system into the wanted state.
