Here's an explination of the running time of Shor's facorization algorithm (which requires a quantum computer). On a flawless quantum computer, it runs in O(N^3) time, where N is the number of digits in the number you're factoring. In reality, with quantum error correction, the running time would probably be O(N^3 * polylog(N)), where polylog(N) is polynomial in log N.
The following 3 things are equivalent A qubit The spin of an electron The polarization of a photon
They are equivalent that they can each be representated by a 2 dimensional complex vector, where you don't care about the overall phase (and 0 isn't allowed).
Every played around with polarized lens filters? You have a horizontally polarized lens followed by a vertically polarized lengs, and no light goes through.
You add one that is polarized at 45 degrees, and suddenly 1/8th of your orginal light is going
You can think of your lenses as measuring your qubits (polarization of each of the photons), in different basises, and only letting the ones that were measured as a |0> through.
Nope, there's a theorem called the no-cloning theorem that says that you can not copy an arbitrary quantum state. There's no way to start with a state |v> and get |v> |v>, which would mean I could perform destructive measurements on one |v> and be left with |v>.
This follows from 2 facts 1. Quantum measurements can be replaced by quantum gates 2. Quantum gates preserve the inner product of two states.
Quantum codes are more complicated than a simple majority function. The problem is that simple measurement causes the wave function to collapse, which is no good if you're in the middle of a very long computation.
Some of us are working on getting a better result than 1 in 1000.;) Actually, the important thing is, it depends on what sort of noise you get from your gates.
Quantum teleportation sends a quantum state far away with no physical quantum connection. It can not be used for FTL, because you have to send the other person classical information to tell them what gates to apply to get back the quantum state you started with.
The advantage of a quantum computer, is that we know how to run certain algorithms with a better big-O running time than on any classical computer. It doesn't matter if a quantum computer gets fewer operations per seconds than a classical computer, it'll still win for factoring large numbers.
Now, there's a different field of study called "Rapid Single Flux", where one tries to built very small classical computing devices that take advantage of quantum mechanics, but don't have the big-O advantages of quantum computing.
Quantum computers aren't quite as powerful as you make them out to be. At the end of your algorithm, you have to perform a measurement, and each qubit when measured only gives you 1 classical bit.
It's been proven that quantum computers are no better than classical computers at sorting (both O(n log n), although they are better at finding something in an unsorted database (Grover's algorithm does O(sqrt(N)), instead of O(N) classically).
No one has proven that quantum computers are faster than classical computers for factoring. We just know of a fast algorithm for a quantum computer and not a classical computer. It's likely that quantum computers are much faster there, though.
A typical quantum algorithm puts most of the wavefunction into the state(s) that you want. By applying various quantum unitary gates repeatedly one can do this. It's kind of hard to explain exactly "why". One then measures the state, and with with probability p gets a correct answer. If p> 50%, one can repeat the algorithm a bunch of times to make sure one has the right answer.
NMR quantum computing techniques have been done a few years ago, but most people think that they don't scale very well. The biggest experiment involved using 7 qubits to find the answer to the age old question: what are the factors of 15?
The problem with quantum information is that you can't clone (copy) an arbitrary quantum state, and you can't measure an arbitrary state without destroying the quantum information.
However, there still exist quantum error correcting codes that can correct an arbitrary error. Classically, one only gets bit flip errors. In quantum computation, you have to worry about phase flip errors, for instance instead of a|0>+b|1> you have a|0>-b|1>.
The smallest quantum code that can correct an arbitrary non located (located errors are easier) error on 1 qubit requires 5 qubits. There's a 7 qubit "CSS" code that is important for fault tolerance.
For fault tolerance, you concatenate a code with itself many times, and if your errors are independent of each other, then by doing all sorts of complicated fault tolerant techniques, you can get fault tolerance. What happens is you get a fault tolerance threshold. If your rate of errors are less than that, you can do arbitrary quantum computation with O(M) qubits in O(N polylog N) time, where O(M) is the qubits required on an error free quantum computer, and O(N) is the time required on an error free quantum computer.
With n classical bits, they can be of 2^n possible states. With n quantum qubits, they can be any normalized (overall phase doesn't matter) complex vector in 2^n dimensions. However, when you measure them, the wave-function will collapse (unless you believe in the many world's multiverse), and you'll get n classical bits.
Classical information is simply a subset of quantum information.
Why January 19th, 17000? And another thing. If we still have time zones then, there's the problem where it's never the same day in every time zone. Some country that should be to the east of the date line, declared themselves to be west of the dateline so that they could ring in the millenium first. I think they differ by 25 hours from some other (nearby) timezone. Will it be Greenwich Mean Time? Will Greenwich still exist?
There are 52 Sundays in the year 17000, starting with January 5th, 17000. I demand to know which Sunday, and why it won't be some other day of the week.
I'm just counting the Berkeley part of the tax. It's a flat 7.5% on all utilities. Berkeley is not a liberal city when it has such a regressive tax like that.
You forgot to mention that Peter Shor found the first quantum error correcting code. Would anyone be working on Quantum computing if Feynman hadn't written a few papers circa 1982 on it?
The thing is, you can think of these filters as a measurement in some basis of the 2 dimensional polarization vector. Measurements changing the results of your previous measurements are definitely a quantum mechanical result.
Slashdot Mirror
You want the Stern-Gerlach experiment You send the particle through a magnetic field, and then detect it on a photographic plate.
Here's an explination of the running time of Shor's facorization algorithm (which requires a quantum computer). On a flawless quantum computer, it runs in O(N^3) time, where N is the number of digits in the number you're factoring. In reality, with quantum error correction, the running time would probably be O(N^3 * polylog(N)), where polylog(N) is polynomial in log N.
The following 3 things are equivalent
A qubit
The spin of an electron
The polarization of a photon
They are equivalent that they can each be representated by a 2 dimensional complex vector, where you don't care about the overall phase (and 0 isn't allowed).
Every played around with polarized lens filters? You have a horizontally polarized lens followed by a vertically polarized lengs, and no light goes through.
You add one that is polarized at 45 degrees, and suddenly 1/8th of your orginal light is going
You can think of your lenses as measuring your qubits (polarization of each of the photons), in different basises, and only letting the ones that were measured as a |0> through.
Nope, there's a theorem called the no-cloning theorem that says that you can not copy an arbitrary quantum state. There's no way to start with a state |v> and get |v> |v>, which would mean I could perform destructive measurements on one |v> and be left with |v>.
This follows from 2 facts
1. Quantum measurements can be replaced by quantum gates
2. Quantum gates preserve the inner product of two states.
Quantum codes are more complicated than a simple majority function. The problem is that simple measurement causes the wave function to collapse, which is no good if you're in the middle of a very long computation.
Some of us are working on getting a better result than 1 in 1000. ;) Actually, the important thing is, it depends on what sort of noise you get from your gates.
A quantum gate is a unitary matrix (think complex change of basis).
Some gates only require 1 qubit.
For example, the Pauli gates:
X=[0 1]
[1 0]
Y=[0 -i]
[i 0]
Z=[1 0]
[0 -1]
Quantum teleportation sends a quantum state far away with no physical quantum connection. It can not be used for FTL, because you have to send the other person classical information to tell them what gates to apply to get back the quantum state you started with.
The advantage of a quantum computer, is that we know how to run certain algorithms with a better big-O running time than on any classical computer. It doesn't matter if a quantum computer gets fewer operations per seconds than a classical computer, it'll still win for factoring large numbers.
Now, there's a different field of study called "Rapid Single Flux", where one tries to built very small classical computing devices that take advantage of quantum mechanics, but don't have the big-O advantages of quantum computing.
Here's a link.
"We see a worldwide demand for maybe a couple of computers" - IBM
"640k of memory is enough for anyone" - Gates
Quantum computers aren't quite as powerful as you make them out to be. At the end of your algorithm, you have to perform a measurement, and each qubit when measured only gives you 1 classical bit.
It's been proven that quantum computers are no better than classical computers at sorting (both O(n log n), although they are better at finding something in an unsorted database (Grover's algorithm does O(sqrt(N)), instead of O(N) classically).
No one has proven that quantum computers are faster than classical computers for factoring. We just know of a fast algorithm for a quantum computer and not a classical computer. It's likely that quantum computers are much faster there, though.
A typical quantum algorithm puts most of the wavefunction into the state(s) that you want. By applying various quantum unitary gates repeatedly one can do this. It's kind of hard to explain exactly "why". One then measures the state, and with with probability p gets a correct answer. If p> 50%, one can repeat the algorithm a bunch of times to make sure one has the right answer.
NMR quantum computing techniques have been done a few years ago, but most people think that they don't scale very well. The biggest experiment involved using 7 qubits to find the answer to the age old question: what are the factors of 15?
Stupid 2 minute rule.
The problem with quantum information is that you can't clone (copy) an arbitrary quantum state, and you can't measure an arbitrary state without destroying the quantum information.
However, there still exist quantum error correcting codes that can correct an arbitrary error. Classically, one only gets bit flip errors. In quantum computation, you have to worry about phase flip errors, for instance instead of a|0>+b|1> you have a|0>-b|1>.
The smallest quantum code that can correct an arbitrary non located (located errors are easier) error on 1 qubit requires 5 qubits. There's a 7 qubit "CSS" code that is important for fault tolerance.
For fault tolerance, you concatenate a code with itself many times, and if your errors are independent of each other, then by doing all sorts of complicated fault tolerant techniques, you can get fault tolerance. What happens is you get a fault tolerance threshold. If your rate of errors are less than that, you can do arbitrary quantum computation with O(M) qubits in O(N polylog N) time, where O(M) is the qubits required on an error free quantum computer, and O(N) is the time required on an error free quantum computer.
With n classical bits, they can be of 2^n possible states.
With n quantum qubits, they can be any normalized (overall phase doesn't matter) complex vector in 2^n dimensions.
However, when you measure them, the wave-function will collapse (unless you believe in the many world's multiverse), and you'll get n classical bits.
Classical information is simply a subset of quantum information.
Wow, the bid is already up to 1.20.
Why January 19th, 17000?
And another thing. If we still have time zones then, there's the problem where it's never the same day in every time zone. Some country that should be to the east of the date line, declared themselves to be west of the dateline so that they could ring in the millenium first. I think they differ by 25 hours from some other (nearby) timezone. Will it be Greenwich Mean Time? Will Greenwich still exist?
There are 52 Sundays in the year 17000, starting with January 5th, 17000. I demand to know which Sunday, and why it won't be some other day of the week.
That's one way to have an Internet connection.
Airplane full of CDs.
High bandwidth.
High latency.
Rice and beans.
It has all the necessary amino acids.
I'm just counting the Berkeley part of the tax. It's a flat 7.5% on all utilities. Berkeley is not a liberal city when it has such a regressive tax like that.
I thought the taxes on my T-mobile bill were 18.9%, now I find out that they're only 16.4%.
You forgot to mention that Peter Shor found the first quantum error correcting code. Would anyone be working on Quantum computing if Feynman hadn't written a few papers circa 1982 on it?
The thing is, you can think of these filters as a measurement in some basis of the 2 dimensional polarization vector. Measurements changing the results of your previous measurements are definitely a quantum mechanical result.
What about Richard Feynman or Peter Shor? It seems like they have more of a claim to be the "father of quantum computing" to me.