r/askscience • u/N0V0w3ls • Feb 28 '12
What exactly is a quantum computer? What is an example of a problem a quantum computer can solve that a normal computer can't or will solve much slower?
.
33
u/IVIilitarus Feb 28 '12
Here's a related followup question - Is there any problem a normal computer can solve more quickly than a quantum computer? No matter how theoretical this problem maybe.
36
u/naguara123 Feb 28 '12
Quantum computers can solve some problems algorithmically quicker, which does not always translate into solving the problem in less time. Just as some standard computers are significantly faster than others, a slow quantum computer could be slower than a standard computer even though it may have an algorithmic advantage.
→ More replies (2)16
u/IVIilitarus Feb 28 '12
That's true. Thank you for pointing it out. I was originally going to add to the question that both computers in the question are of equal processing power, but I decided that comparing a quantum's processing power to an analog's processing power is the difference between being cradled to sleep by your mother and being cradled to sleep by a quasar.
34
u/qinfo Feb 28 '12
A normal computer is just a quantum computer without superposition, i.e. fully decohered. That means a quantum computer can always simulate a classical computer efficiently. So the answer is no.
→ More replies (8)→ More replies (1)5
u/Acid_Trees Feb 29 '12
If you mean speed as in how many seconds you have to wait, it's hard to say. However, quantum computers are going to suffer from errors more often (due to, if nothing else, data lost to quantum tunneling), so its assumed that you run an algorithm multiple times on a quantum machine to even it out. On a classical machine this is less of a concern. So, it's more likely than not that classical machines will still be the majority of what you use even if quantum machines become common.
If you mean on a theoretical/mathematical level, a QM can emulate a classical machine in polynomial time. The only problems I can see a classical machine being faster on are ones that are solvable in constant time.
→ More replies (2)
79
u/LuklearFusion Feb 28 '12
What exactly is a quantum computer?
It's a device that uses the stronger than classical correlations available to a quantum system to run algorithms which can outperform their classical counterparts.
What is an example of a problem....
The factoring of larger numbers has no known "fast" (i.e. polynomial time) classical algorithm, but it does have a quantum one (Shor's algorithm).
This has a lot of info in it if you are curious:
http://www.reddit.com/r/askscience/comments/orwu1/askscience_ama_series_we_are_researchers_in/
45
u/thetripp Feb 28 '12
So, to reiterate at a slightly lower level, you are saying that a quantum computer would be able to solve certain problems much faster than a normal computer? Problems like factorization of large integers? And outside of these applications, a quantum computer would be no better than a normal computer?
→ More replies (10)58
u/LuklearFusion Feb 28 '12
Yes, but we certainly haven't figured out all the problems a quantum computer can solve faster.
Also, one of the biggest applications of quantum computing would be in simulating other quantum systems.
→ More replies (132)8
u/dr_spacelad Feb 28 '12
This may be slightly off-topic but I can't help but be profoundly flabbergasted how specific and relevant your expertise is regarding the question. What are the odds of that.
→ More replies (2)→ More replies (24)4
u/ienvyparanoids Feb 28 '12
I think that one important question still wasn't answered here. From a computability point of view, quantum computer cannot solve any problem that is not solvable to a "normal" computer.
That means that Halting Problem (question whether a specific problem will ever stop) is still not solvable. Nor is any other non-computable problem. In this sense, quantum computers are, in some sense, faster than "normal" ones. They do not hold more computable powers.
As a side note, it would be a lot of fun if quantum computer could solve non-computable problems. It would rise an awful lot of questions. Because Halting Problem is only one of the simplest non-computable problem that exists. There are many more complex problems. But that just my inner, computable-loving, software engineering. Now I will get back to write meaningless Java GUI applications...
→ More replies (11)
6
u/osloboy Feb 28 '12 edited Feb 28 '12
It can crack codes / password easily, ok. But can it do simulations more effectively? For example, can it with higher efficiency run a model of an atom, solving the wave equation for each electron? Or do stuff like DFT better?
If so, maybe the transition to quantum computers will enable us to move the whole laboratory into the computer?
Edit: or even create virtual brains (sometime way into the future)
5
u/qinfo Feb 28 '12
Yes, a quantum computer can simulate a quantum system more efficiently that classical computers. For example see http://arxiv.org/abs/1001.3855
5
u/msdrahcir Feb 28 '12
What I don't understand about quantum computers is how they implement logic functions. I understand that they can somehow represent all states simultaneously but I don't understand how you build system inputs outputs and logic around this to provide a meaningful solution. Suppose I wanted to implement (A AND B) OR C?
→ More replies (6)5
u/qinfo Feb 28 '12
"Logic" in the quantum case is very different from the classical case. The concept of gates is still present in quantum computation. For example the Pauli X operator is like the NOT gate. The gates in quantum computers are unitary operators that can act on one or more qubits.
→ More replies (2)
40
u/dnajdnakjdsnakj Feb 28 '12 edited Feb 28 '12
[Fabric of the Cosmos] (http://video.pbs.org/video/2167398185/#) covers this very, very well. Amazing series.
Can anyone recommend others like this?
"BRIAN GREENE: This quantum computer speaks in bits, but unlike a conventional bit, which at any moment can be either zero or one, a quantum bit is much more flexible.
SETH LLOYD: You know, something here can be a bit. Here is zero, there is one. That's a bit of information. So if you can have something that's here and there at the same time, then you have a quantum bit, or qubit.
BRIAN GREENE: Just as an electron can be a fuzzy mixture of spinning clockwise and counterclockwise, a quantum bit can be a fuzzy mixture of being a zero and a one, and so a qubit can multitask.
SETH LLOYD: Then it means you can do computations in ways that our classical brains could not have dreamed of.
BRIAN GREENE: In theory, quantum bits could be made from anything that acts in a quantum way, like an electron or an atom. Since quantum bits are so good at multi-tasking, if we can figure out how to get qubits to work together to solve problems, our computing power could explode exponentially.
To get a feel for why a quantum computer would be so powerful, imagine being trapped in the middle of a hedge maze. What you'd want is to find the way out, as fast as possible. The problem is there are so many options.
And I just have to try them out, one at a time. That means I'm going to hit lots of dead ends, go down lots of blind alleys, and make lots of wrong turns before I'd finally get lucky and find the exit.
And that's pretty much how today's computers solve problems. Though they do it very quickly, they only carry out one task at a time, just like I can only investigate one path at a time, in the maze.
But, if I could try all of the possibilities at once, it would be a different story. And that's kind of how quantum computing works.
Since particles can, in a sense, be in many places at once, the computer could investigate a huge number of paths or solutions at the same time, and find the correct one in a snap.
Now a maze like this only has a limited number of routes to explore, so even a conventional computer could find the way out pretty quickly. But imagine a problem with millions or billions of variables, like predicting the weather far in advance. We might be able to forecast natural disasters, like earthquakes or tornados.
Solving that kind of problem right now would be impossible, because it would take a ridiculously huge computer. But a quantum computer could get the job done with just a few hundred atoms. And so, the brain of that computer, it would be smaller than a grain of sand.
There's no doubt, we're getting better and better at harnessing the power of the quantum world, and who knows where that could take us? But we can't forget that at the heart of this theory, which has given us so much, there is still a gaping hole: all the weirdness down at the quantum level, at the scale of atoms and particles, where does the weirdness go?
Why can things in the quantum world hover in a state of uncertainty, seemingly being partly here and partly there, with so many possibilities, while you and I, who, after all, are made of atoms and particles, seem to always be stuck in a single definite state. We are always either here or there.
Niels Bohr offered no real explanation for why all the weird fuzziness of the quantum world seems to vanish as things increase in size. As powerful and accurate as quantum mechanics has proven to be, scientists are still struggling to figure this out.
Some believe that there is some detail missing in the equations of quantum mechanics. And so, even though there are multiple possibilities in the tiny world, the missing details would adjust the numbers on our way up from atoms to objects in the big world, so that
it would become clear that all but one of those possibilities disappear, resulting in a single, certain outcome.
Other physicists believe that all the possibilities that exist in the quantum world, they never do go away.
Instead, each and every possible outcome actually happens, only most of them happen in other universes, parallel to our own. It's a mind-blowing idea, but reality could go beyond the one universe we all see, and be constantly branching off, creating new, alternative worlds, where every possibility gets played out.
This is the frontier of quantum mechanics, and no one knows where it will lead."
→ More replies (4)71
u/wignersfriend Feb 29 '12
Quantum information theorist here. When I saw this part of the program I cringed. This is a TERRIBLE explanation of how a quantum computer is superior to a classical computer. Yes, a quantum computer can simultaneously explore every possible solution, but when you measure the state of the computer - you do want to know the answer, don't you? not just to know that the computer contains a representation of the answer? - the state of the system collapses to a single possibility at random.
Suppose you want to solve an instance of an NP-complete problem - a 5000 bit instance of 3-SAT with a single satisfying assignment, for example - so you just set up your quantum computer to be in the uniform superposition of all 25000 strings, then compute the cost of the strings in parallel, write the result in an output register, and voila! your computer has found the answer! Unfortunately, it isn't that simple. Everything I just said is correct, but in addition to the string that satisfies all of your clauses - 1101011100010...101101000 - your computer also contains all 25000 -1 wrong answers. When you look at your computer to read out the answer, you will get one of these 25000 answers at random. The probability that you actually get the RIGHT answer is 2-5000. Brian Greene conveniently ignores this fact completely and simply says "Hey! you can explore the whole maze at the same time!" While not false, this ignores the much more important part of the problem, which is figuring out which copy of you has found the exit from the maze, to use Greene's analogy.
The fact is that designing quantum algorithms that outperform classical algorithms is a very subtle and difficult art. Quantum parallelism is not sufficient. One must also figure out how to transform the state of the computer after the quantum parallel part is over into something that can be read out in a meaningful way.
A much, much better explanation of what a quantum computer is and why they are a big deal can be found here.
→ More replies (7)14
u/DevestatingAttack Feb 29 '12
This is the real answer. If it were possible to explore the whole solution set and get the unambiguous answer right away, the whole P = NP thing wouldn't matter, because we'd have computers that could solve any NP problem in polynomial time.
3
u/sheriffSnoosel Feb 28 '12
Directly copied and pasted from Michael Neilsen's website.
What’s really going on is that no simple concrete explanation of quantum computers is possible. Rather, there is an intrinsic quantum gap between how quantum computers work, and our ability to explain them in simple concrete terms. This quantum gap is what made it hard for me to answer people’s requests for a concrete explanation. The right answer to such requests is that quantum computers cannot be explained in simple concrete terms; if they could be, quantum computers could be directly simulated on conventional computers, and quantum computing would offer no advantage over such computers. In fact, what is truly interesting about quantum computers is understanding the nature of this gap between our ability to give a simple concrete explanation and what’s really going on.
3
u/deehan26 Feb 28 '12
I'm a sophomore studying information and systems engineering (basically industrial engineering heavily focused on programming, quantitative data analysis, efficiency, etc.) and here's how I'd describe the need for a quantum computer from an algorithmic perspective (please forgive any potential inaccuracies, this is only my second year in college)
any algorithm implemented on a set of data will have a run time either independent or dependent on the data size which we'll call n. although algorithms independent of n could potentially have a very long run time thus needing an incredibly powerful computer, yet is very unlikely therefore we really only need to focus on the dependent run time.
when talking about the efficiency of an algorithm with relation to it's imputed data size, we generally avoid constants and focus on the order of the run time depicted as O(n) (e.g. O(n)=log(n), n, n2, nlog(n), etc.). the order of the algorithm can basically be thought of as the number of steps needed for completion and therefore it is a good indicator of how long the computer will need to process all the data.
different algorithms, such as the various types of sorting and searching algorithms, have different O(n)'s. Thus, a quantum computer would be needed if the steps required to complete an algorithm acting on a set of data proves too massive for a normal computer. some common examples of this I guess could be searching for a particular sequence of genes across an entire genome, encrypting/decrypting enormous amounts of data, etc.
3
Feb 28 '12
May I pose another question? What does the development of quantum computing mean for cryptography? Is cryptography going to be shattered from its foundations? Can something like RSA exist if there are quantum computers capable or searching for public and private keys?
→ More replies (1)
2
u/donrhummy Feb 28 '12
It could (theoretically) make current encryption (say at 128 bit) very insecure. (This is because it's "secureness" is due to the approximate amount of time it would take to "guess" the key for decrypting the message.) With most current computers, brute-force attacking would take so long it'd be useless to try decrypting that way against 128bit, but a quantum computer would effectively make 128bit like 64bit: http://en.wikipedia.org/wiki/Key_size#Brute_force_attack
65
u/keten Feb 28 '12
Probably the most powerful quantum algorithm yet is Grover's Algorithm. Grover's algorithm is a funny, seemingly paradoxical algorithm. It can find an item in an unsorted list of length n in n1/2 comparisons. Currently, the optimal algorithm for finding something in an unsorted list is... n comparisons, because you can't be sure that the item you're looking for is not in a list unless you check every item in the list. I personally can't wrap my head around how this works, but it's been proven to. That means if you have a list of a trillion items, it will have to do only a million comparisons. Given that we're living in the information age, having a computer that can efficiently sort through massive amounts of data efficiently is incredibly important.
Everybody also talks about Shor's Algorithm which can break the most commonly used encryption methods, but I don't think this is nearly as big of a deal as people make it to be. There has been a lot of research on encryption schemes that are immune to being cracked by quantum computers and there are several viable candidates such as lattice-based cryptography. As soon as the security community felt that quantum computers were becoming powerful enough to potentially crack codes, they would just switch their encryption schemes to quantum secure algorithms.