3. P vs. NP is a problem phrased in the language of classical Turing machines. In that sense, quantum computing has no bearing on it. It is unknown whether NP problems can be solved efficiently on quantum computers.
4. Is a common misunderstanding about entanglement. Unfortunately, while entanglement does allow non-classical long-distance correlations, it does not allow for communication. Think of it this way: suppose we took two random number generators that start with the same seed, and thus produce the same stream of bits. Then you take yours over there while I keep mine over here. This doesn't help us communicate faster, because we don't get to pick the bits that come out of the generator. So too with quantum entanglement.
Isn't one of the main idea of entanglement/superposition the fact that the qubits' values are not pre-determined? I.e. the two random generators don't have the same actual seed, but as soon as the first one is used, it generates a seed, and the second one will also use the same seed from then on?
I still have some difficulty understanding how that doesn't rule out some undetectable determinism, and how/if it's possible to measure if the superposition has already collapsed (i.e. the seed has already been determined), something apparently useful in quantum encryption.
Right, s/he's giving you a sense of "classical entanglement", but quantum entanglement can also do some interesting things which classical entanglement cannot do. However, the scope of that is not as simple as "set those bits over there to an arbitrary state as seen from over here." In fact, if my bits over here are entangled with your bits over there, the entanglement manifests in spooky coincidences between our actions which you won't even notice if you don't bring our actions together and compare them. From our perspectives individually it looks like we're both doing random actions; but then you find out that when you bring the actions lists back together they were both the same; neither of us had the chance to predict or affect what the other one did but we both agreed on what we did.
Here's a game for a three-person team: they are all cooperating, but the game is called "betrayal" because we will secretly force one of them to betray the other two and measure how gracefully they recover from it. We will put the team through many "tests", if they win all of them, they get lots of money; you don't get any money for being a traitor in any given test.
Here's how this goes. We put everybody in relativistically separated rooms; each room has a computer screen and two buttons labeled 0 and 1. Once they're all isolated we give the group a test. Then they can come back together and collaborate before the next test, as they see fit.
Some tests are "control" tests. We flash on the screen, simultaneously to all 3 of them, the command "make the sum of your numbers even." We collect the 1's and 0's together, add them together, and they pass the test if it's even.
Other tests, we randomly choose one as a traitor. We flash on the screen to the traitor the same "make the sum of your numbers even" prompt, but we flash to the other two, "traitor round! make the sum of your numbers odd" -- and they pass the test if, when we add together the three numbers they press, that sum is odd.
There's no classical probability distribution on the six random variables A_even, B_even, C_even, A_odd, B_odd, C_odd which satisfies all of those tests 100% of the time, so that A_even + B_even + C_even is even but A_odd + B_odd + C_even is odd and so forth. Just add all of the equations together; you'll get 2 * (A_e + B_e + C_e + A_o + B_o + C_o) on the left hand side, but (even + 3*odd) on the right hand side and thus even = odd, which is impossible. There is no classical 100%-solution.
There is a quantum 100%-solution. If |+> is the state |0> + |1> and |−> is the state |0> − |1> then the (entangled, GHZ) state
|+++> + |−−−> = |000> + |011> + |101> + |110>
guarantees that any measurement will have an even sum, while the state
|+++> − |−−−> = |001> + |010> + |100> + |111>
guarantees that any measurement will have an odd sum. The two people who know there is a traitor in their midst can do the unitary transform which takes |+> to |+> and |−> to i |−> (which is a "controlled phase rotation" combined with some "Hadamard gates"), and this defining property of complex numbers that i^2 = -1 causes the total state to switch between those two parameters when any two people make those transformations.
So if they're playing with an entangled quantum state, two of them can make a local change to their own state which induces the right sort of change in the global state that, when we bring the data together and correlate, we find out that they can do something which classical observers cannot ever do: win a game with 100% probability. Each of them locally appears to be producing 0 or 1 with a 50/50 probability but globally when we compare their bits we find out that they could choose together whether that sum was odd or even in a crazy new way.
http://en.wikipedia.org/wiki/Bell%27s_theorem tells us that no matter how much classical information you have, you still can't get correlations that are as good as quantum entanglement.
If we have quantum computers, then isn't P vs. NP the wrong question? With quantum computers, the more relevant problem to study should be BQP versus QMA (the quantum analogs of P and NP/MA, i.e., computable versus verifiable in polynomial time on a quantum computer). Are complexity theorists studying the wrong problem?
Comments
3. P vs. NP is a problem phrased in the language of classical Turing machines. In that sense, quantum computing has no bearing on it. It is unknown whether NP problems can be solved efficiently on quantum computers.
4. Is a common misunderstanding about entanglement. Unfortunately, while entanglement does allow non-classical long-distance correlations, it does not allow for communication. Think of it this way: suppose we took two random number generators that start with the same seed, and thus produce the same stream of bits. Then you take yours over there while I keep mine over here. This doesn't help us communicate faster, because we don't get to pick the bits that come out of the generator. So too with quantum entanglement.
Isn't one of the main idea of entanglement/superposition the fact that the qubits' values are not pre-determined? I.e. the two random generators don't have the same actual seed, but as soon as the first one is used, it generates a seed, and the second one will also use the same seed from then on?
I still have some difficulty understanding how that doesn't rule out some undetectable determinism, and how/if it's possible to measure if the superposition has already collapsed (i.e. the seed has already been determined), something apparently useful in quantum encryption.
Right, s/he's giving you a sense of "classical entanglement", but quantum entanglement can also do some interesting things which classical entanglement cannot do. However, the scope of that is not as simple as "set those bits over there to an arbitrary state as seen from over here." In fact, if my bits over here are entangled with your bits over there, the entanglement manifests in spooky coincidences between our actions which you won't even notice if you don't bring our actions together and compare them. From our perspectives individually it looks like we're both doing random actions; but then you find out that when you bring the actions lists back together they were both the same; neither of us had the chance to predict or affect what the other one did but we both agreed on what we did.
Here's a game for a three-person team: they are all cooperating, but the game is called "betrayal" because we will secretly force one of them to betray the other two and measure how gracefully they recover from it. We will put the team through many "tests", if they win all of them, they get lots of money; you don't get any money for being a traitor in any given test.
Here's how this goes. We put everybody in relativistically separated rooms; each room has a computer screen and two buttons labeled 0 and 1. Once they're all isolated we give the group a test. Then they can come back together and collaborate before the next test, as they see fit.
Some tests are "control" tests. We flash on the screen, simultaneously to all 3 of them, the command "make the sum of your numbers even." We collect the 1's and 0's together, add them together, and they pass the test if it's even.
Other tests, we randomly choose one as a traitor. We flash on the screen to the traitor the same "make the sum of your numbers even" prompt, but we flash to the other two, "traitor round! make the sum of your numbers odd" -- and they pass the test if, when we add together the three numbers they press, that sum is odd.
There's no classical probability distribution on the six random variables A_even, B_even, C_even, A_odd, B_odd, C_odd which satisfies all of those tests 100% of the time, so that A_even + B_even + C_even is even but A_odd + B_odd + C_even is odd and so forth. Just add all of the equations together; you'll get 2 * (A_e + B_e + C_e + A_o + B_o + C_o) on the left hand side, but (even + 3*odd) on the right hand side and thus even = odd, which is impossible. There is no classical 100%-solution.
There is a quantum 100%-solution. If |+> is the state |0> + |1> and |−> is the state |0> − |1> then the (entangled, GHZ) state
guarantees that any measurement will have an even sum, while the state guarantees that any measurement will have an odd sum. The two people who know there is a traitor in their midst can do the unitary transform which takes |+> to |+> and |−> to i |−> (which is a "controlled phase rotation" combined with some "Hadamard gates"), and this defining property of complex numbers that i^2 = -1 causes the total state to switch between those two parameters when any two people make those transformations.So if they're playing with an entangled quantum state, two of them can make a local change to their own state which induces the right sort of change in the global state that, when we bring the data together and correlate, we find out that they can do something which classical observers cannot ever do: win a game with 100% probability. Each of them locally appears to be producing 0 or 1 with a 50/50 probability but globally when we compare their bits we find out that they could choose together whether that sum was odd or even in a crazy new way.
http://en.wikipedia.org/wiki/Bell%27s_theorem tells us that no matter how much classical information you have, you still can't get correlations that are as good as quantum entanglement.
If we have quantum computers, then isn't P vs. NP the wrong question? With quantum computers, the more relevant problem to study should be BQP versus QMA (the quantum analogs of P and NP/MA, i.e., computable versus verifiable in polynomial time on a quantum computer). Are complexity theorists studying the wrong problem?