http://mathoverflow.net/questions/100480 Proposes a quantum key exchange protocol and asks for criticism/references. Quantum computing is not my field, so there are some details which aren't clear to me but probably would be to an expert, but it seems like a reasonable question on the boundary of math and CS.
First question: What is quantum about it? Quantum cryptography (using quantum mechanical effects to transmit secret data) is not public key cryptography. Quantum computing is not cryptography per se but it has potential application to cryptography. What he is proposing is neither. There is no quantum. The name is there just to impress the ignorant.
Second question: Which Hilbert space and how is this implemented? Cryptography is all about easy computation versus hard computation. How does one compute in a Hilbert space? Maybe one can approximate but unless things are made explicit it doesn't make sense.
So he is proposing some kind of key exchange, but the whole thing is so devoid of details as to be meaningless. Maybe operator theory has not been used in this way but if that's the information he wants, it's kind of pointless.
Given the OP's history here, I don't have high hopes for this or any other of his questions.
Interjecting, I thought the question might be interesting to someone who knows more about quantum computing, and assumed that it has something to do with hilbert spaces and stuff. Maybe the state of a system or something, and then applying operators is what quantum computing actually is.
* I really don't know anything about quantum computing (though, I am very familiar with classical computing), and the above statement is a guess I had - before the post.
My first reaction to Mark Sapir's comment and the very fast closure (without knowing of the history of the user) was that we in all likelihood do not know enough of quantum computing to know if the question is of research level.
If an active researcher in the area, such as Voloch, says the question doesn't make sense, then I guess that's that, at least for me.
@voloch As I commented on the OP, I don't know what it means to send an operator, only to send a state (or a density matrix). Adjusting appropriately for that, here is the best interpretation I could find of the question, and it is genuinely quantum:
Alice and Bob each prepare a qubit in state |1>. They also select random angles alpha and beta, uniformly distributed in the unit circle, and rotate their qubits by alpha and beta respectively. Each then mails their qubit to the other, and applies his or her rotation to the qubit they now have. So they now both have qubits in state cos(alpha+beta) |1> + sin(alpha+beta) |2>, although they don't know what alpha+beta is. Setting alpha+beta = gamma, their joint state is
cos^2 gamma |1> |1> + cos gamma sin gamma |1> |2> + cos gamma sin gamma |2> |1> + sin^2 gamma |2> |2>.
This is different from the standard quantum cryptography protocol, where Alice and Bob's joint state is
1/sqrt{2} |1> |1> + 1/sqrt{2} |2> |2>.
What's interesting is that, unlike the standard protocol, we never need to prepare any particles in an entangled state. Indeed, Alice could make her qubit, send it off and have Bob act on it, and then they could just store it for a year before Bob starts making his qubit. I could imagine this might have advantages.
Now, is this useful for communication? I say yes. As in the standard quantum cryptography procedure, Alice and Bob then each flip a coin. If the coin comes up heads, measure the qubit in the basis (e_1, e_2). If the coin comes up tails, measure the qubit in basis ( (e_1+e_2)/sqrt{2}, (e_1-e_2)/sqrt{2} ). They then tell each other how their coins came up. If the coins disagree, they discard the qubits and data and start over. If the coin flips agree, however, then Alice and Bob use their measurements as the first bit of a shared secret. In classical quantum cryptography, Alice and Bob will always get the same measurement. In the new scenario, if the angle between gamma and their measurement angle is theta, then the probability that they will agree is cos^4 theta+sin^4 theta and, averaging over theta, the probability of agreeing is 1/(2 pi) \int_0^{2 pi} (cos^4 theta+sin^4 theta) d theta = 3/4. So Alice and Bob have a "shared secret" where 1/4 of the bits have been altered. Using error correcting codes, one should still be able to use this for communication.
Now, can Eve interfere? I don't know. This is where I'd appreciate an expert's perspective. It does seem bizarre that Alice and Bob are getting the advantages of quantum cryptography without using any entanglement.
I think the original question is hard to read because it is asked too generally. If I wanted to describe the above protocol in the level of generality of the original post (but replacing operators by states), I would write "Let H be a Hilbert space and G a commutative group (or semigroup) of operators on H. Alice and Bob each start with a particle in the same state v and choose secret elements a and b of G. They send each other av and bv and thus compute abv=bav. They use this as a shared secret." But this raises tons of questions about which G we are using and which probability distribution on it. The above description gives the simplest answers I could find for all of those questions.
@David: I am impressed that you could read all this into the question that the OP asked. I thought he was just proposing a key exchange using non-commutativity of operators (and that's what his X was for). I can't answer the questions you pose. It raises a bunch of other questions. First one I can think of is, how do you mail a qubit? If you have a secure channel, then you don't need anything. If you don't, then somebody can observe the transmission and, as the physicists tell us, cause the wave function to collapse. So you are back to the quantum cryptography situation, needing entanglement and so on.
I am trying to use the same model as in standard quantum crypto. Alice and Bob have a channel which is good enough to send a qubit through and have it come out in the same state, but which is not proof against evesdropping. (One may question the plausibility of this assumption -- that's why quantum crypto doesn't get much use in the real world -- but I think those are the standard rules.)
The odd thing is that I think you get the advantages of quantum crpyto without having prepared two particles in an entangled state. For example, suppose that Eve tries the following: Choose a random angle delta, measure Alice and Bob's particles at that angle, and send on the measured particles. But Eve won't succeed. Once Alice and Bob rotate the particles Eve has sent on, their angles will be uncorrelated. So, when they run through the secret generating algorithm, their secrets will only agree on 1/2 the bits, not 3/4, and a statistical test will show that they are being evesdropped on. Of course, Eve could do a lot of more complicated things, and it is not clear to me whether some of them might work...
This seems so nice that I feel that I must be making some very basic error.
@David Speyer: earlier quantum protocols like BB84 did not use entanglement (unlike E91) and seems nowadays they are used in most commercial applications due to simpler implementation http://en.wikipedia.org/wiki/Quantum_key_distribution
Ah, thanks! I apparently managed to learn this material from sources that only told me about E91. (Sources here mean a Discover magazine article, complete with colorful cartoons, a graduate student seminar at Berkeley and, I thought, a section of Scott Aaronson's lecture notes, although I can't find that right now. I did SAY that I wasn't an expert.) Now that I read about BB84, I wonder why they made that expository decision; BB84 seems so much simpler to present.
In that case, I'm not seeing any advantage of the Diffie-Helman style approach over BB84.
I myself also is not a specialist, but it is hard to be interested in quantum computing, but did not hear some news about quantum cryptography, e.g., I heard lecture of member of quantum hacking group and some other presentations. I can guess, that obvious disadvantages of quantum cryptography are cost (about $50 000 then I asked about that last time) and novelty (the trust comes only with time).