3 ms·
Related: I'm still not satisfied with the answer as to why quantum cryptography's eavesdropper detection -- not possible with a Turing machine -- can't be embed
by amichail 17y ago
Related: I'm still not satisfied with the answer as to why quantum cryptography's eavesdropper detection -- not possible with a Turing machine -- can't be embedded in a model of computation that goes beyond Turing-completeness:
http://news.ycombinator.com/item?id=955079 http://news.ycombinator.com/item?id=955079
- pmjordan 17y agoI've been thinking about this and the best I can come up with is the same as smanek's answer. It's not a form of computation; I'd say it's a physical concept rather than a mathematical one. Retrieving information about a quantum system's state changes that that state. Moreover, it is impossible to have a complete set of information about the system's state.
- mkyc 17y agoBecause it is possible with a Turing machine. http://en.wikipedia.org/wiki/Quantum_Turing_machine http://en.wikipedia.org/wiki/Quantum_Turing_machine http://74.125.155.132/search?q=cache:CgFC04CcivAJ:folk.uio.no/ovrum/articles/deutsch85.pdf http://74.125.155.132/search?q=cache:CgFC04CcivAJ:folk.uio.n... The idea (iirc, and poorly translated into more familiar vocabulary) is that when we're running a quantum Turing machine on a regular machine, the data on the tape can be "quantum encoded". There is a specific series of steps for "decoding" it, but it's a destructive operation: decoding the data screws up the data. Decoding it a second time gives you broken data, and you know that it's broken. (You might wonder, why don't we just write a Turing machine that can decode the data without destroying it? Well, you're free to do so, but then it's no longer a quantum Turing machine running on a Turing machine - it's no longer the same as the physics, can't be implemented directly in quantum physics, and therefore would be both slow and potentially have a tape with more slots than atoms in our universe.)