maccyjj ยท 55 points ยท Posted at 04:44:04 on April 21, 2013 ยท (Permalink)
Quantum physicist here - a classical computer encodes information in bits, which can either take the value 0 or 1. A quantum computer instead uses a qubit, which physically can be something like a photon or an atom. The qubit can be in the state 0 or 1 (like a classical computer), but also in a superposition of these two states. Say we have a sequence of three classical bits, then we can only store 1 out of 8 possible numbers at a given time. However if we have a sequence of three qubits, all 8 numbers can be stored in a quantum superposition at the same time! This gives the quantum computer great power, because it can perform calculations on these superpositions in parallel. A system of N qubits can make 2N calculations at the same time. So our system of three qubits make 8 calculations simultaneously, while the classical computer is only making one. This computational power means that large tasks can be performed 2N times as fast, and there are special algorithms for things like factoring large numbers (Shor's algorithm) and searching databases (Grover's algorithm) that are only possible with a quantum computer.
The main difficulty in making a quantum computer is that whenever a quantum state is measured, it collapses. So we must find a way of making the qubit perform calculations, which we do with quantum gates, and then measuring it without destroying the state. This is done in complicated ways by a process called entanglement, which for now is difficult to do with many qubits. (However this destruction of the state is sometimes useful for cryptography, because it allows the receiving end to know whether someone has looked at the information somewhere along the path. If someone has seen it, the state is destroyed and they know that their information has been breached). The qubit is also easily affected by the environment, called decoherence, and so many accidental errors occur when making computations. This is what most research is about and because of these difficulties, the quantum computer is still quite a few years off.
Tl;dr - Quantum computers are super fast because they use qubits to perform multiple calculations at the same time. It is also useful for carrying secret information, beause it is immediately obvious if someone has seen it. Both of these are impossible with classical computers.
sooneday ยท 10 points ยท Posted at 07:12:12 on April 21, 2013 ยท (Permalink)
My understanding is that quantum computers don't make classical computers obsolete. Quantum Computers are better at specific tasks, but classical computers are simpler to make and good enough for general use. Do you think quantum computers will replace classical computers for personal use?
Personally I think it will lean towards a hybrid design with a classical and quantum part. While you're right that quantum computers are much better at some tasks, I believe they're also worse at certain types of tasks. That's why I think we'll end up with hybrid devices, not because classical computers are simpler and good enough. With that mentality we might as well be using MSDOS with a black and white CRT screen. It's easier and good enough for general use.
aerfen ยท 7 points ยท Posted at 09:55:14 on April 21, 2013 ยท (Permalink)
I've always thought that eventually we'll end up with a discrete quantum card in an otherwise classical computer. Much like a graphics card is way better at certain massively parallel tasks, but not general purpose computation.
Yes, this is exactly what I believe will happen. There are already all kinds of weird PCI cards like quantum mechanical random number generators so a "QCU" (Quantum Computing Unit) doesn't seem to improbable for the future. However, I reckon it would take us at least another 25 years to get there.
owieo ยท 2 points ยท Posted at 14:45:44 on April 21, 2013 ยท (Permalink)
With cloud computing growing like it is I would guess that regular consumers would continue to use computers much like they exists today and datacenters would be the users of quantum computers. The fact that the heavy lifting is being done by a quantum computer wouldn't be apparent to the end user.
I look at it kind of like it's a lightswitch, constantly flicking up and down, impossibly fast. The measurement comes in like a big giant foam finger, and pins it down into one of the positions.
You might think that there were some hidden variables that, earlier, would have let us time the finger, so that we could make it one measurement or the other, but quantum physicists don't believe that's the case (for a bunch of good reasons that I, as a non-physicist, don't understand).
Hah. The thing is "whenever a quantum state is measured, it collapses" refers to a piece of math. Your problem only arises when you try to map it to reality. It's not agreed on what it means. Can't even agree upon if the quantum state really can collapse or if it is a real physical thing.
Alpha_Q ยท 2 points ยท Posted at 10:39:00 on April 21, 2013 ยท (Permalink)
By abstracting the processes of QCs into mathematical operations/operations on a Turing machine, could you tell me what 'new' phenomenon is it that adds the extra speed? I read somewhere that QCs basically are probabailstic machines with complex/negative probabilities or something.
Edit: Another question - If a QC can do many operations in parallel, how is it different from a multi-headed Turing machine?
To naively simulate a quantum computer as described by OP you'd need 2N turing machines for a N bit input. As the quantum computer (in a sense) can run all possible inputs at the same time, giving you all possible outputs in one run. Problem is that when you measure the output the state collapses and you only get one of the outputs. And the process is even random, so you can't choose which. However, you can make the different outputs 'interfere' with each other before you measure. So you can get something that's a property of all the outputs.
The DeutschโJozsa algorithm is the simplest example I know. Consider having a function f. f takes a N-bit input and outputs 0 or 1. Now the question is. Is f constant or balanced? That is, does it always output the same or does it output half 0's and half 1's? To be sure of this you'd need to run it 2N-1 times or have that many turing machines. A quantum computer can do that in one single run.
But a Turing machine, even a single-tape one, CAN simulate an arbitrary finite number of Turing machines. A quantum Turing machine can't compute anything that isn't (classical) Turing machine computable, it can just do so much, much more efficiently in some cases.
Quantum computers don't do multiple computations at the same time, and I'm not sure how (as a 'quantum physicist') you could have made that mistake. They can perform rotations over Hilbert spaces but it's unclear exactly how much computation power you gain from that (and getting exponentially as much is definitely not the case, as BQP is most certainly in PSPACE and PSPACE is most certainly in EXPTIME).
Quantum computers don't do multiple computations at the same time
I think that's a perfectly fine ELI5-way of putting it. In the MWI you literally have a different parallel universe for each computation. Obviously you need make these realities to interfere before measurement.
He does seem confused about the role of entanglement, which makes me wonder about his credentials.
Also, we do appear to get exponential speedup in some cases (factoring being famous).
maccyjj ยท 4 points ยท Posted at 08:19:15 on April 21, 2013 ยท (Permalink)
Okay, thank you, I am trying to explain this stuff like it was for a 5 year old, so yes I did simplify some things. If you would like to have an attempt at explaining these difficult concepts to the layman then please feel free. I feel like perhaps I didn't do such a great job and you are taking my attempt at a simplified explanation as what I believe as fact, this is ELI5 not AskScience nor a conference. Also, not a dude.
I agree it's hard to explan and simplifying is fine. Problem is that this
measuring it without destroying the state. This is done in complicated ways by a process called entanglement
is not just simplified but incorrect. Entanglement is required for the first part of your description('parallel' computing). Measurements are actually the easy part.
HrBingR ยท 0 points ยท Posted at 20:22:56 on April 21, 2013 ยท (Permalink)
That was eli5? Holy shit, no offense, but I couldn't understand that.
Of course the exponential speedup is important, otherwise we wouldn't care so much for quantum computers. But yeah, I doubt his credentials somewhat.
As a side note the interpretation is kind of irrelevant, what matters is our manipulations of states. I don't think it's reasonable to say it does multiple computations at the same time, to be honest, it gives a very flawed impression of what quantum computers do. Something like manipulating vectors instead of bits maybe, I'm not sure. The general computation time hierarchy is pretty sacred though.
(I'm a grad student in quantum complexity theory, which is why these things irk me so much)
I just mentioned the MWI to point out that saying 'multiple calculations at the same time' is consistent with the theory. Quite a few people in the area wouldn't mind putting it like that.
As long as BQP is not contained on P we could get exponential speedup, so I don't understand your argument with BQP being contained in EXP.
Talking about unitary rotations of vectors in multidimensional complex vector spaces might be too complicated for ELI5.
The argument implies that you can do exponentially many calculations at once, which isn't true. There are some problems that get exponential speedup (hidden subgroup for finite abelian groups is the most famous example) but that is a pretty far cry from being able to compute exponentially many things at a time.
I just think it's misleading. Quantum computers aren't necessarily exponentially faster than classical ones, for most problems they probably aren't.
However this destruction of the state is sometimes useful for cryptography, because it allows the receiving end to know whether someone has looked at the information somewhere along the path. If someone has seen it, the state is destroyed and they know that their information has been breached
Interesting. This doesn't work for entanglement, does it? It couldn't, right? That would violate....well, a lot.
The main difficulty in making a quantum computer is that whenever a quantum state is measured, it collapses. So we must find a way of making the qubit perform calculations, which we do with quantum gates, and then measuring it without destroying the state. This is done in complicated ways by a process called entanglement,
I'm a little confused here. You seem to claim that entanglement is used to make non-destructive measurements. That doesn't sound right. Entanglement is needed for doing the calculations, not the measurement as such. Maybe I misunderstood you?
maccyjj ยท 6 points ยท Posted at 05:03:57 on April 21, 2013 ยท (Permalink)
Perhaps my wording was a bit off, you are correct that entanglement is not an actual physical measurement, but rather entanglement is when a second qubit mimics the properties of a first qubit, providing a mechanism to indirectly measure the quantum state of the first.
No, I think you misunderstood the point of entanglement. Two entangled qubits are not in two seperate states, but in one joint state. That's literally the definition of entanglement. You can't use one half to figure out the state of the other half, that's non sensical and violates all kinds of principles(eg. No cloning theorem).
maccyjj ยท 3 points ยท Posted at 05:24:24 on April 21, 2013 ยท (Permalink)
No, I think you misunderstood what I am saying in my comment. I didn't say they were in separate states, nor did I say you directly measure the second to find out the first, either. Of course that is not how quantum computation works. I just said it provides a mechanism. I am trying to simplify the explanation because I think it is appropriate for this subreddit, if you would like to have a proper discussion about QIP perhaps we should continue it somewhere else at the risk of overcomplicating what is supposed to be a simple to understand discussion.
Simplified is fine, just sounded like you we're mixing together several concepts incorrectly. You'll always destroy the state when you measure, no amount of entanglement can circumvent that.
The way you described it, it sounded like you could always get an actual 2N speedup by circumventing the wave function collapse using entanglement. Which is all kinds of wrong.
[deleted] ยท 0 points ยท Posted at 15:03:17 on April 21, 2013 ยท (Permalink)
Pretty sure 5 year old me didn't understand a word of that
Wilcows ยท -1 points ยท Posted at 10:09:37 on April 21, 2013 ยท (Permalink)
This wasnt an easy explanation at all. There's no way to understand this without knowing other background info that most of us dont know.
maccyjj ยท 1 points ยท Posted at 11:25:52 on April 21, 2013 ยท (Permalink)
Sorry, I tried my best. There are a few concepts in there that are quite difficult to grasp so it is necessary to go in to some detail.
Wilcows ยท 1 points ยท Posted at 12:00:07 on April 21, 2013 ยท (Permalink)
tl;dr Quantum Computer is like a normal computer but uses qubits instead of bits. It can solve certain problems faster than a normal computer, but is extremely difficult to make.
Working in superconducting circuit quantum electrodynamics here (make small circuits to be qubits in very cold temperatures).
So a normal computer operates with bits, which can be 0 or 1, or on and off. A quantum computer operates with qubits, which can be 0, 1 or a mix of 0 and 1 at the same time. With a normal computer you can only have the bit change between those two values. With a quantum computer you can have it shift between the two values (more complex than that but this is just a ELI5, read on the Bloch Sphere for more).
That the qubit is able to be in this mixed state allows us to do certain things faster than a normal computer can. One of the more famous is Shor's Algorithm, which factors large numbers. The speed up is so much so that factoring a 2000 bit number (think ~1060), which even a normal computer the size of the planet would have trouble solving before the human race died off, would take a quantum computer about a day or two. A good source for other algorithms is Quantum Zoo.
This would still be a pretty big quantum computer though, requiring about 200 million qubits, and take a nuclear reactor to power it. That is with current designs we have come up with so far. It is still very difficult to make as it requires generally very cold temperatures, sometimes very strong magnetic fields, or very good lasers and detectors.
I can't think of any of the algorithms that would necessarily improve a video game, though I could see them being used for better AI.
Yes, but not as a consumer product. Any of the likely scalable systems (superconducting and ion trap) require such low temperatures and heavy shielding that they won't ever be in the home. They could possibly be connected to in a cloud manner, but are likely to have more benefit in an industrial scale. Might see some minor implementation of an optical system to support QKD (Quantum Key Distribution) in consumer systems in the far future.
I think this has been asked a couple of times here.
A normal computer calculates functions. It has an input and produces an output. Each time you calculate the function it takes a certain amount of time. In a sense, a quantum computer allows for multiple inputs and, with only one calculation, gives you all the corresponding outputs.
Edit: we actually don't know they're better, we just strongly believe they are.
[deleted] ยท 1 points ยท Posted at 17:45:50 on April 21, 2013 ยท (Permalink)
I think the people behind it think they're building something functional. I have my doubts. They might have some quantum properties, but is it scalable? What exactly is going on? I wouldn't put my money on it.
One of the, in my opinion, smartest people in this field has this to say.
For any interested 5 year olds with a good grasp of maths: Quantum Computing for the Determined, recorded by one of the guys who literally wrote the book on quantum computation, explains how it works from a theoretical point of view.
One part of your question is "Why is it superior to our current computers?"
This is interesting. From what I know, a quantum computer is not superior to a classical computer all of the time. Quantum computers can do certain types of computations much faster than classical computers, but not all types. If you have a problem, and one part of the problem is very difficult to perform on a classical computer, then it is worth investigating whether it may be faster on a quantum computer. Sometimes you can find a way to do that part of the computation much much faster, other times you can get a small but ultimately not very significant speedup, and most of the time you cannot improve on your classical algorithm.
The most useful thing that a quantum computer can do better than a classical one is to simulate quantum physics. This is very difficult to do on a classical computer: every quantum particle can be in one of two states, so to simulate n particles you need to keep track of 2n states in total. This grows very quickly (2 particles: 4 states, 8 particles: 256 states, 100 particles: 1.2676506e30 states or approx. 1,000,000,000,000,000,000,000,000,000,000 states) so it is not practical to try and simulate even small quantum systems on a classical computer. This is a pity because simulation can teach you a lot about a system. Quantum computers solve this problem by taking advantage of the superposition of quantum states. Each qubit can keep track of the state of one particles state, so you only need n qubits to keep track of n particles in your simulation - an enormous improvement!
The other very famous algorithm use of quantum computers is Shors algorithm for factoring large integers. This algorithm (which I cannot explain because I do not understand it) really got people interested in quantum computing because it takes a very difficult problem (factoring an integer of n digits takes ~ en steps, thus growing mind-numbingly hard for large n) and finds a way to perform the most difficult part in a much shorter time (~ n3, a polynomial number of steps). Most hard problems probably cannot be reformulated in this way, which puts limits on how useful a quantum computer can be.
An example of a problem that can be made faster, but only moderately so, using a quantum computer, is searching an unsorted database. With a classical computer, the best method is to literally check every item one-by-one, thus searching a database of n items should take no more than n steps. The quantum algorithm allows the problem to be solved in n.5 steps. This is better, but it is nothing like the exponential speed-up obtained for the integer factorization problem.
The ultimate answer to your question is that if you can reformulate part of your problem to take advantage of the abilities of a quantum computer, then the quantum computer is better than the classical computer for your problem. But most of the time you will probably not be able to do this, and quantum computers are much harder to build and operate than classical computers, so the improvement will not be worth the cost in most cases. The exceptions should be enough to occupy the worlds quantum computers, once they are built, until the end of time. But you will probably never play computer games or surf the net on a quantum computer.
[deleted] ยท -1 points ยท Posted at 04:05:42 on April 21, 2013 ยท (Permalink)
Here's what i've been told (it could be wrong): normal computers are just a bunch of tiny pieces of information. Each piece of information is called a bit. Bits can only be either "on" or "off." Since there's only two choices, we call this "binary." In a quantum computer, each bit would have more than one option, so you'd be able to have more information in less space. For example, in binary, two bits of information only have four different outcomes (00, 01, 10, 11). If you had a quantum computer with three choices per bit, you'd have nine possible outcomes (00, 01, 02, 10, 11, 12, 20, 21, 22).
Edit: Please stop down voting me on a topic you don't have the proper background to understand, I gave my answer elsewhere. What OP described is a Ternary computer and has nothing to do with quantum computers
[deleted] ยท 3 points ยท Posted at 05:10:22 on April 21, 2013 ยท (Permalink)
Ok, thanks for correcting me. :)
[deleted] ยท -4 points ยท Posted at 02:27:58 on April 21, 2013 ยท (Permalink)
Makes me sad to see you down voted. Quantum information theory(where computers are one part) rises exactly from the realization that information is physical (famous quote from Landauer). Classical information theory(Claude Shannon in particular) is seen as a part of mathematics.
But why should we let math dictate what information is when information is so obviously part of the physical world(books, DVDs, HDD, etc.)?
maccyjj ยท 2 points ยท Posted at 04:48:43 on April 21, 2013 ยท (Permalink)
also from what i've heard, theyre not better. or even as good. (yet)
*note: no background in computing or quantum physics. i could be extremely wrong.
maccyjj ยท 2 points ยท Posted at 04:47:05 on April 21, 2013 ยท (Permalink)
Well of course they are not very good yet, because the research is still very new. But I promise they are much better in terms of computational power!
Amarkov ยท -1 points ยท Posted at 06:36:21 on April 21, 2013 ยท (Permalink)
Well, if you want to do things that require a lot of computational power. I'd expect a quantum computer to be quite a bit slower at browsing the Internet or something, because the major bottleneck is not algorithmic efficiency.
Saved comment
maccyjj ยท 55 points ยท Posted at 04:44:04 on April 21, 2013 ยท (Permalink)
Quantum physicist here - a classical computer encodes information in bits, which can either take the value 0 or 1. A quantum computer instead uses a qubit, which physically can be something like a photon or an atom. The qubit can be in the state 0 or 1 (like a classical computer), but also in a superposition of these two states. Say we have a sequence of three classical bits, then we can only store 1 out of 8 possible numbers at a given time. However if we have a sequence of three qubits, all 8 numbers can be stored in a quantum superposition at the same time! This gives the quantum computer great power, because it can perform calculations on these superpositions in parallel. A system of N qubits can make 2N calculations at the same time. So our system of three qubits make 8 calculations simultaneously, while the classical computer is only making one. This computational power means that large tasks can be performed 2N times as fast, and there are special algorithms for things like factoring large numbers (Shor's algorithm) and searching databases (Grover's algorithm) that are only possible with a quantum computer.
The main difficulty in making a quantum computer is that whenever a quantum state is measured, it collapses. So we must find a way of making the qubit perform calculations, which we do with quantum gates, and then measuring it without destroying the state. This is done in complicated ways by a process called entanglement, which for now is difficult to do with many qubits. (However this destruction of the state is sometimes useful for cryptography, because it allows the receiving end to know whether someone has looked at the information somewhere along the path. If someone has seen it, the state is destroyed and they know that their information has been breached). The qubit is also easily affected by the environment, called decoherence, and so many accidental errors occur when making computations. This is what most research is about and because of these difficulties, the quantum computer is still quite a few years off.
Tl;dr - Quantum computers are super fast because they use qubits to perform multiple calculations at the same time. It is also useful for carrying secret information, beause it is immediately obvious if someone has seen it. Both of these are impossible with classical computers.
sooneday ยท 10 points ยท Posted at 07:12:12 on April 21, 2013 ยท (Permalink)
My understanding is that quantum computers don't make classical computers obsolete. Quantum Computers are better at specific tasks, but classical computers are simpler to make and good enough for general use. Do you think quantum computers will replace classical computers for personal use?
flare561 ยท 8 points ยท Posted at 07:52:08 on April 21, 2013 ยท (Permalink)
Personally I think it will lean towards a hybrid design with a classical and quantum part. While you're right that quantum computers are much better at some tasks, I believe they're also worse at certain types of tasks. That's why I think we'll end up with hybrid devices, not because classical computers are simpler and good enough. With that mentality we might as well be using MSDOS with a black and white CRT screen. It's easier and good enough for general use.
aerfen ยท 7 points ยท Posted at 09:55:14 on April 21, 2013 ยท (Permalink)
I've always thought that eventually we'll end up with a discrete quantum card in an otherwise classical computer. Much like a graphics card is way better at certain massively parallel tasks, but not general purpose computation.
orbital1337 ยท 2 points ยท Posted at 10:08:32 on April 21, 2013 ยท (Permalink)
Yes, this is exactly what I believe will happen. There are already all kinds of weird PCI cards like quantum mechanical random number generators so a "QCU" (Quantum Computing Unit) doesn't seem to improbable for the future. However, I reckon it would take us at least another 25 years to get there.
owieo ยท 2 points ยท Posted at 14:45:44 on April 21, 2013 ยท (Permalink)
With cloud computing growing like it is I would guess that regular consumers would continue to use computers much like they exists today and datacenters would be the users of quantum computers. The fact that the heavy lifting is being done by a quantum computer wouldn't be apparent to the end user.
SnazzilyDressed ยท 2 points ยท Posted at 08:39:28 on April 21, 2013 ยท (Permalink)
Layman question here: How do physicists say things like "whenever a quantum state is measured, it collapses" and not eventually lose their minds?
bandman614 ยท 5 points ยท Posted at 14:53:38 on April 21, 2013 ยท (Permalink)
I look at it kind of like it's a lightswitch, constantly flicking up and down, impossibly fast. The measurement comes in like a big giant foam finger, and pins it down into one of the positions.
You might think that there were some hidden variables that, earlier, would have let us time the finger, so that we could make it one measurement or the other, but quantum physicists don't believe that's the case (for a bunch of good reasons that I, as a non-physicist, don't understand).
light_slider ยท 2 points ยท Posted at 19:18:56 on April 21, 2013 ยท (Permalink)
Upvote for giant foam finger of science.
The_Serious_Account ยท 5 points ยท Posted at 10:15:47 on April 21, 2013 ยท (Permalink)
Hah. The thing is "whenever a quantum state is measured, it collapses" refers to a piece of math. Your problem only arises when you try to map it to reality. It's not agreed on what it means. Can't even agree upon if the quantum state really can collapse or if it is a real physical thing.
Alpha_Q ยท 2 points ยท Posted at 10:39:00 on April 21, 2013 ยท (Permalink)
By abstracting the processes of QCs into mathematical operations/operations on a Turing machine, could you tell me what 'new' phenomenon is it that adds the extra speed? I read somewhere that QCs basically are probabailstic machines with complex/negative probabilities or something.
Edit: Another question - If a QC can do many operations in parallel, how is it different from a multi-headed Turing machine?
The_Serious_Account ยท 2 points ยท Posted at 11:00:44 on April 21, 2013 ยท (Permalink)
To naively simulate a quantum computer as described by OP you'd need 2N turing machines for a N bit input. As the quantum computer (in a sense) can run all possible inputs at the same time, giving you all possible outputs in one run. Problem is that when you measure the output the state collapses and you only get one of the outputs. And the process is even random, so you can't choose which. However, you can make the different outputs 'interfere' with each other before you measure. So you can get something that's a property of all the outputs.
The DeutschโJozsa algorithm is the simplest example I know. Consider having a function f. f takes a N-bit input and outputs 0 or 1. Now the question is. Is f constant or balanced? That is, does it always output the same or does it output half 0's and half 1's? To be sure of this you'd need to run it 2N-1 times or have that many turing machines. A quantum computer can do that in one single run.
wintermute93 ยท 2 points ยท Posted at 18:41:01 on April 21, 2013 ยท (Permalink)
But a Turing machine, even a single-tape one, CAN simulate an arbitrary finite number of Turing machines. A quantum Turing machine can't compute anything that isn't (classical) Turing machine computable, it can just do so much, much more efficiently in some cases.
The_Serious_Account ยท 0 points ยท Posted at 18:51:25 on April 21, 2013 ยท (Permalink)
Yes, that's important to point out. The strong Church-Turing thesis is not being disproven by quantum computers.
Edit: I sometimes wonder who on earth is down voting these comments. Can't possibly have much understanding of the subject matter.
Xentreos ยท 2 points ยท Posted at 07:17:32 on April 21, 2013 ยท (Permalink)
Quantum computers don't do multiple computations at the same time, and I'm not sure how (as a 'quantum physicist') you could have made that mistake. They can perform rotations over Hilbert spaces but it's unclear exactly how much computation power you gain from that (and getting exponentially as much is definitely not the case, as BQP is most certainly in PSPACE and PSPACE is most certainly in EXPTIME).
The_Serious_Account ยท 6 points ยท Posted at 07:29:06 on April 21, 2013 ยท (Permalink)
I think that's a perfectly fine ELI5-way of putting it. In the MWI you literally have a different parallel universe for each computation. Obviously you need make these realities to interfere before measurement.
He does seem confused about the role of entanglement, which makes me wonder about his credentials.
Also, we do appear to get exponential speedup in some cases (factoring being famous).
maccyjj ยท 4 points ยท Posted at 08:19:15 on April 21, 2013 ยท (Permalink)
Okay, thank you, I am trying to explain this stuff like it was for a 5 year old, so yes I did simplify some things. If you would like to have an attempt at explaining these difficult concepts to the layman then please feel free. I feel like perhaps I didn't do such a great job and you are taking my attempt at a simplified explanation as what I believe as fact, this is ELI5 not AskScience nor a conference. Also, not a dude.
The_Serious_Account ยท 2 points ยท Posted at 10:01:55 on April 21, 2013 ยท (Permalink)
I agree it's hard to explan and simplifying is fine. Problem is that this
is not just simplified but incorrect. Entanglement is required for the first part of your description('parallel' computing). Measurements are actually the easy part.
HrBingR ยท 0 points ยท Posted at 20:22:56 on April 21, 2013 ยท (Permalink)
That was eli5? Holy shit, no offense, but I couldn't understand that.
reposter_ ยท 1 points ยท Posted at 15:52:38 on April 26, 2013 ยท (Permalink)
W-w-where am i?
Xentreos ยท 1 points ยท Posted at 07:36:16 on April 21, 2013 ยท (Permalink)
Of course the exponential speedup is important, otherwise we wouldn't care so much for quantum computers. But yeah, I doubt his credentials somewhat.
As a side note the interpretation is kind of irrelevant, what matters is our manipulations of states. I don't think it's reasonable to say it does multiple computations at the same time, to be honest, it gives a very flawed impression of what quantum computers do. Something like manipulating vectors instead of bits maybe, I'm not sure. The general computation time hierarchy is pretty sacred though.
(I'm a grad student in quantum complexity theory, which is why these things irk me so much)
The_Serious_Account ยท 3 points ยท Posted at 07:55:34 on April 21, 2013 ยท (Permalink)
I just mentioned the MWI to point out that saying 'multiple calculations at the same time' is consistent with the theory. Quite a few people in the area wouldn't mind putting it like that.
As long as BQP is not contained on P we could get exponential speedup, so I don't understand your argument with BQP being contained in EXP.
Talking about unitary rotations of vectors in multidimensional complex vector spaces might be too complicated for ELI5.
Xentreos ยท 1 points ยท Posted at 08:06:03 on April 21, 2013 ยท (Permalink)
The argument implies that you can do exponentially many calculations at once, which isn't true. There are some problems that get exponential speedup (hidden subgroup for finite abelian groups is the most famous example) but that is a pretty far cry from being able to compute exponentially many things at a time.
I just think it's misleading. Quantum computers aren't necessarily exponentially faster than classical ones, for most problems they probably aren't.
GoingtoHecq ยท 1 points ยท Posted at 14:47:56 on April 21, 2013 ยท (Permalink)
how much heat do they produce?
bandman614 ยท 1 points ยท Posted at 14:48:59 on April 21, 2013 ยท (Permalink)
Interesting. This doesn't work for entanglement, does it? It couldn't, right? That would violate....well, a lot.
The_Serious_Account ยท 1 points ยท Posted at 04:54:02 on April 21, 2013 ยท (Permalink)
I'm a little confused here. You seem to claim that entanglement is used to make non-destructive measurements. That doesn't sound right. Entanglement is needed for doing the calculations, not the measurement as such. Maybe I misunderstood you?
maccyjj ยท 6 points ยท Posted at 05:03:57 on April 21, 2013 ยท (Permalink)
Perhaps my wording was a bit off, you are correct that entanglement is not an actual physical measurement, but rather entanglement is when a second qubit mimics the properties of a first qubit, providing a mechanism to indirectly measure the quantum state of the first.
The_Serious_Account ยท 0 points ยท Posted at 05:10:38 on April 21, 2013 ยท (Permalink)
No, I think you misunderstood the point of entanglement. Two entangled qubits are not in two seperate states, but in one joint state. That's literally the definition of entanglement. You can't use one half to figure out the state of the other half, that's non sensical and violates all kinds of principles(eg. No cloning theorem).
maccyjj ยท 3 points ยท Posted at 05:24:24 on April 21, 2013 ยท (Permalink)
No, I think you misunderstood what I am saying in my comment. I didn't say they were in separate states, nor did I say you directly measure the second to find out the first, either. Of course that is not how quantum computation works. I just said it provides a mechanism. I am trying to simplify the explanation because I think it is appropriate for this subreddit, if you would like to have a proper discussion about QIP perhaps we should continue it somewhere else at the risk of overcomplicating what is supposed to be a simple to understand discussion.
The_Serious_Account ยท 2 points ยท Posted at 05:37:27 on April 21, 2013 ยท (Permalink)
Simplified is fine, just sounded like you we're mixing together several concepts incorrectly. You'll always destroy the state when you measure, no amount of entanglement can circumvent that.
The way you described it, it sounded like you could always get an actual 2N speedup by circumventing the wave function collapse using entanglement. Which is all kinds of wrong.
[deleted] ยท 0 points ยท Posted at 15:03:17 on April 21, 2013 ยท (Permalink)
Pretty sure 5 year old me didn't understand a word of that
Wilcows ยท -1 points ยท Posted at 10:09:37 on April 21, 2013 ยท (Permalink)
This wasnt an easy explanation at all. There's no way to understand this without knowing other background info that most of us dont know.
maccyjj ยท 1 points ยท Posted at 11:25:52 on April 21, 2013 ยท (Permalink)
Sorry, I tried my best. There are a few concepts in there that are quite difficult to grasp so it is necessary to go in to some detail.
Wilcows ยท 1 points ยท Posted at 12:00:07 on April 21, 2013 ยท (Permalink)
Well i still appreciate the effort
skillphiliac ยท 1 points ยท Posted at 13:27:37 on April 21, 2013 ยท (Permalink)
Oh Lord, again with the people who don't understand the concept of ELI5.
The_Serious_Account ยท -1 points ยท Posted at 17:04:17 on April 21, 2013 ยท (Permalink)
Eh, no. The complaint is that it's not possible to understand for a lay person. That's exactly what this subreddit is for.
[deleted] ยท -6 points ยท Posted at 06:09:16 on April 21, 2013 ยท (Permalink)
I read this all in Sheldon's voice.
EngSciGuy ยท 6 points ยท Posted at 06:58:13 on April 21, 2013 ยท (Permalink)
tl;dr Quantum Computer is like a normal computer but uses qubits instead of bits. It can solve certain problems faster than a normal computer, but is extremely difficult to make.
Working in superconducting circuit quantum electrodynamics here (make small circuits to be qubits in very cold temperatures).
So a normal computer operates with bits, which can be 0 or 1, or on and off. A quantum computer operates with qubits, which can be 0, 1 or a mix of 0 and 1 at the same time. With a normal computer you can only have the bit change between those two values. With a quantum computer you can have it shift between the two values (more complex than that but this is just a ELI5, read on the Bloch Sphere for more).
That the qubit is able to be in this mixed state allows us to do certain things faster than a normal computer can. One of the more famous is Shor's Algorithm, which factors large numbers. The speed up is so much so that factoring a 2000 bit number (think ~1060), which even a normal computer the size of the planet would have trouble solving before the human race died off, would take a quantum computer about a day or two. A good source for other algorithms is Quantum Zoo.
This would still be a pretty big quantum computer though, requiring about 200 million qubits, and take a nuclear reactor to power it. That is with current designs we have come up with so far. It is still very difficult to make as it requires generally very cold temperatures, sometimes very strong magnetic fields, or very good lasers and detectors.
Edit: Woops, fixed from bot.
JordanTheBrobot ยท 2 points ยท Posted at 07:02:39 on April 21, 2013 ยท (Permalink)
Fixed your link
I hope I didn't jump the gun, but you got your link syntax backward! Don't worry bro, I fixed it, have an upvote!
Bot Comment - [ Stats & Feeds ] - [ Charts ] - [ Information for Moderators ] - [ Live Image Feed ]
Wilcows ยท 1 points ยท Posted at 10:12:18 on April 21, 2013 ยท (Permalink)
So if these end up on the market, we'd have super uber realistic videogames?
Is there a chance of these computers ending up on the market?
EngSciGuy ยท 2 points ยท Posted at 10:22:44 on April 21, 2013 ยท (Permalink)
I can't think of any of the algorithms that would necessarily improve a video game, though I could see them being used for better AI.
Yes, but not as a consumer product. Any of the likely scalable systems (superconducting and ion trap) require such low temperatures and heavy shielding that they won't ever be in the home. They could possibly be connected to in a cloud manner, but are likely to have more benefit in an industrial scale. Might see some minor implementation of an optical system to support QKD (Quantum Key Distribution) in consumer systems in the far future.
The_Serious_Account ยท 7 points ยท Posted at 04:25:29 on April 21, 2013 ยท (Permalink)
I think this has been asked a couple of times here.
A normal computer calculates functions. It has an input and produces an output. Each time you calculate the function it takes a certain amount of time. In a sense, a quantum computer allows for multiple inputs and, with only one calculation, gives you all the corresponding outputs.
Edit: we actually don't know they're better, we just strongly believe they are.
[deleted] ยท 1 points ยท Posted at 17:45:50 on April 21, 2013 ยท (Permalink)
This probably doesn't fit into the thread, but what to think of this apparatus? D-Wave 'Quantum' Computer @Lockheed
In short, is that a mix of both worlds, a PR stunt, a serious improvement? Asking you folks with the Quantum insight in general.
The_Serious_Account ยท 2 points ยท Posted at 19:34:01 on April 21, 2013 ยท (Permalink)
I think the people behind it think they're building something functional. I have my doubts. They might have some quantum properties, but is it scalable? What exactly is going on? I wouldn't put my money on it.
One of the, in my opinion, smartest people in this field has this to say.
I hereby retire my notorious comment from 2007, about the 16-bit machine that D-Wave used for its Sudoku demonstration being no more computationally-useful than a roast-beef sandwich. D-Wave does have something today thatโs more computationally-useful than a roast-beef sandwich; the question is โmerelyโ whether itโs ever more useful than your laptop
[deleted] ยท 1 points ยท Posted at 19:43:44 on April 21, 2013 ยท (Permalink)
What`s wrong with a roast-beef sandwich? Seriously, thanks for the read and link.
elmanchosdiablos ยท 2 points ยท Posted at 10:11:02 on April 21, 2013 ยท (Permalink)
For any interested 5 year olds with a good grasp of maths: Quantum Computing for the Determined, recorded by one of the guys who literally wrote the book on quantum computation, explains how it works from a theoretical point of view.
mickey_kneecaps ยท 1 points ยท Posted at 00:10:37 on April 22, 2013 ยท (Permalink)
One part of your question is "Why is it superior to our current computers?"
This is interesting. From what I know, a quantum computer is not superior to a classical computer all of the time. Quantum computers can do certain types of computations much faster than classical computers, but not all types. If you have a problem, and one part of the problem is very difficult to perform on a classical computer, then it is worth investigating whether it may be faster on a quantum computer. Sometimes you can find a way to do that part of the computation much much faster, other times you can get a small but ultimately not very significant speedup, and most of the time you cannot improve on your classical algorithm.
The most useful thing that a quantum computer can do better than a classical one is to simulate quantum physics. This is very difficult to do on a classical computer: every quantum particle can be in one of two states, so to simulate n particles you need to keep track of 2n states in total. This grows very quickly (2 particles: 4 states, 8 particles: 256 states, 100 particles: 1.2676506e30 states or approx. 1,000,000,000,000,000,000,000,000,000,000 states) so it is not practical to try and simulate even small quantum systems on a classical computer. This is a pity because simulation can teach you a lot about a system. Quantum computers solve this problem by taking advantage of the superposition of quantum states. Each qubit can keep track of the state of one particles state, so you only need n qubits to keep track of n particles in your simulation - an enormous improvement!
The other very famous algorithm use of quantum computers is Shors algorithm for factoring large integers. This algorithm (which I cannot explain because I do not understand it) really got people interested in quantum computing because it takes a very difficult problem (factoring an integer of n digits takes ~ en steps, thus growing mind-numbingly hard for large n) and finds a way to perform the most difficult part in a much shorter time (~ n3, a polynomial number of steps). Most hard problems probably cannot be reformulated in this way, which puts limits on how useful a quantum computer can be.
An example of a problem that can be made faster, but only moderately so, using a quantum computer, is searching an unsorted database. With a classical computer, the best method is to literally check every item one-by-one, thus searching a database of n items should take no more than n steps. The quantum algorithm allows the problem to be solved in n.5 steps. This is better, but it is nothing like the exponential speed-up obtained for the integer factorization problem.
The ultimate answer to your question is that if you can reformulate part of your problem to take advantage of the abilities of a quantum computer, then the quantum computer is better than the classical computer for your problem. But most of the time you will probably not be able to do this, and quantum computers are much harder to build and operate than classical computers, so the improvement will not be worth the cost in most cases. The exceptions should be enough to occupy the worlds quantum computers, once they are built, until the end of time. But you will probably never play computer games or surf the net on a quantum computer.
[deleted] ยท -1 points ยท Posted at 04:05:42 on April 21, 2013 ยท (Permalink)
Here's what i've been told (it could be wrong): normal computers are just a bunch of tiny pieces of information. Each piece of information is called a bit. Bits can only be either "on" or "off." Since there's only two choices, we call this "binary." In a quantum computer, each bit would have more than one option, so you'd be able to have more information in less space. For example, in binary, two bits of information only have four different outcomes (00, 01, 10, 11). If you had a quantum computer with three choices per bit, you'd have nine possible outcomes (00, 01, 02, 10, 11, 12, 20, 21, 22).
The_Serious_Account ยท 3 points ยท Posted at 04:12:12 on April 21, 2013 ยท (Permalink)
It is.
Edit: Please stop down voting me on a topic you don't have the proper background to understand, I gave my answer elsewhere. What OP described is a Ternary computer and has nothing to do with quantum computers
[deleted] ยท 3 points ยท Posted at 05:10:22 on April 21, 2013 ยท (Permalink)
Ok, thanks for correcting me. :)
[deleted] ยท -4 points ยท Posted at 02:27:58 on April 21, 2013 ยท (Permalink)
[deleted]
stephencruz ยท 4 points ยท Posted at 08:57:19 on April 21, 2013 ยท (Permalink)
regular computers flip one card at a time to see an answer, one after the other.
quantum computers get to flip all the cards at once
iGotPride ยท -3 points ยท Posted at 03:23:41 on April 21, 2013 ยท (Permalink)
I can give a basic explanation since I don't know a whole lott besides:
Current computers' ability is based on math. Quantum is based on physics.
Sorry, that's all I got! I'm just as curious as you, OP.
The_Serious_Account ยท 2 points ยท Posted at 04:44:04 on April 21, 2013 ยท (Permalink)
Makes me sad to see you down voted. Quantum information theory(where computers are one part) rises exactly from the realization that information is physical (famous quote from Landauer). Classical information theory(Claude Shannon in particular) is seen as a part of mathematics.
But why should we let math dictate what information is when information is so obviously part of the physical world(books, DVDs, HDD, etc.)?
maccyjj ยท 2 points ยท Posted at 04:48:43 on April 21, 2013 ยท (Permalink)
I think physics still is maths, though.
The_Serious_Account ยท 2 points ยท Posted at 05:01:59 on April 21, 2013 ยท (Permalink)
Right. Of course. I meant where your place it at a university. Near math or near physics.
the_corpse ยท -4 points ยท Posted at 02:33:22 on April 21, 2013 ยท (Permalink)
also from what i've heard, theyre not better. or even as good. (yet) *note: no background in computing or quantum physics. i could be extremely wrong.
maccyjj ยท 2 points ยท Posted at 04:47:05 on April 21, 2013 ยท (Permalink)
Well of course they are not very good yet, because the research is still very new. But I promise they are much better in terms of computational power!
Amarkov ยท -1 points ยท Posted at 06:36:21 on April 21, 2013 ยท (Permalink)
Well, if you want to do things that require a lot of computational power. I'd expect a quantum computer to be quite a bit slower at browsing the Internet or something, because the major bottleneck is not algorithmic efficiency.