Ultrafilter, how exactly do the branch and collapse functions work? How many branches can you get? When you collapse, what exactly do you collapse to? Can you recommend any books on nondeterministic programming (which I imagine wouldn’t require understanding of quantum physics)?
I’d guess that one would not need a deep understanding of quantum physics to program a quantum computer–all one would need is some appreciation of a few basic quantum ideas like superposition and entanglement (sorry for the jargon–you can find a lot of info on these topics on the net, though).
To take full advantage of a quantum computer, though, one must appreciate the fundamental differences between quantum information and classical information. Right now, no one can really do this, because no one knows exactly what quantum information is.
But before you start worrying about programming your quantum computer, remember that in 1994 Peter Shor found a factoring algorithm that was superpolynomially faster than any known classical method (the only part that is quantum actually involves finding the periodicity of a function), and this started all this current fascination with quantum computing. In 1996 Lov Grover found a quantum search algorithm that is faster than any classical one (and is in fact optimal). Since 1996, exactly how many algorithms have been discovered that are faster on a quantum computer than any classical one? Zero. That’s right: for all the research going on for the past eight years, we know how to solve exactly two problems.
Don, one of those two problems would blow the lid right off all modern cryptography. If we can factor large numbers in trivial time, we can make obsolete pretty much all foundations the science of secrecy has been built on for the past few decades.
But I do get your point: We have no working models. We’re barely touching the surface of transporting information at the quantum level with our teleportation experiments. Barring the miraculous, it will be decades before any of this is remotely relevant to the day-to-day hacker.
Not only that, but quantum encryption, as I understand it from the links here, is 100% unbreakable without being detected. Might not be legal to make without severe regulations until there is a safety net in place already, perhaps making most crackers obsolete.
Not true. Some (but not all) public-key encryption algorithms are cracked by factoring. No symmetric algorithm that I can recall is attacked this way. Granted, a breakthrough in factoring seriously affects a lot of encryption protocols which rely on algorithms like RSA for key exchange, but it does not eliminate all modern crypto.
In Bruce Schneier’s book “Secrets and Lies”, one of his later chapters discusses technologies to watch and touches briefly on factoring breakthroughs. He says “If this happens, we could be in a world where public-key cryptography does not work and parts of this book are a quaint historical oddity. This won’t be terrible; authentication infrastructure schemes based on symmetric cryptography can do much of the same job.” We’d have to change a lot of protocols, but it’s not the end of privacy.
Quantum encryption is based on particle entanglement properties and has nothing to do with quantum computers, aside from the fact that they both use quantum effects. Quantum encryption is somewhat of a misnomer. It’s really a secure transmission channel which detects eavesdropping. It does not actually encode or obfuscate the message, and simply allows two endpoints to guarantee there’s no man in the middle. Security of storage at the endpoints is another matter. You don’t use a quantum computer to perform quantum cryptography.
I can’t even formulate a response to your second sentence. Do you really anticipate legal restrictions on future crypto (quantum or otherwise)? By whom? With what precedent?
What I’m referring to is an entirely theoretical construct called a non-deterministic Turing machine. Any good text on theoretical computer science would have a lot to say on this–I recommend Sipser’s text, which is pretty clear, and as straightforward as these things get. Be forewarned that it’s pretty mathematically sophisticated.
It will be entirely useless to the world of computer users until someone writes a compiler compiler. That should be the third or fourth thing done, in the world of machine language quantum computer programming. After that, it becomes a matter of taste.
Of course there will be Internet User Groups screaming in all caps about the obvious idiocy of anyone who chooses to use a language they don’t like, because quantum computing made that language obsolete decades ago. That shouldn’t change much until someone invents some new technology for people to froth at the mouth about.
Hardware will become even more invisible to users. Programmers above the level of systems programming will pretty much have to write self adjusting programs to use quantum computer elements when they are available, (Remember math co-processors?) and do it the old fashioned way when they are not. No one is going to throw away a trillion dollars in existing infrastructure to gain the benefits of the new stuff. OK, some will, but most will not.
Programming a current state of the art computer doesn’t require that you know Ohm’s law, or understand the workings of a transistor. My computer uses programs written in the same languages to store information on my hard disk, and on my CD read/write. The level of abstraction we call programming languages exists precisely because it is useful not to consider the hardware that is being used, but rather to consider only the logic of our task. Writing changes into the languages is going to require some understanding of how quantum computing differs in results from electronic computing, but even that won’t require understanding quantum physics. It’s all just ones and zeros, to a programmer. To most programmers it’s all just storage, functions, and addresses. Who cares what is happening on a molecular level?
Tris
Uh, there are compiler-compilers. yacc and bison are two flavours of such tools, and I’ve used them in a compiler construction class where we wrote about 60% of an actual compiler for a functionally complete ‘fictitious’ language within a single school semester. Big deal.
I’m failing to see the magic here.
Either a way will be found to translate existing languages (C, C++, Pascal, FORTRAN, whatever) into such a form as to benefit from Quantum Computing, or some additional libraries or language constructs will be needed to allow such benefits. Following that, languages better suited to quantum computing will emerge. During all of this, typical conventional programming techniques will almost certainly be used for 99% of the code involved. The other 1%, which would normally take 99% of the time, like prime factorization, will make use of the really ugly bits. We can write some pretty optimal things in hand-tooled processor/environment specific assembler that blows away traditional compilers hands down – but nobody in their right mind would do this for more than the absolutely necessary 1% of the code.
Admittedly, this is just my opinion, but I’m not really seeing the issue.
The specific language you choose to use for such things will be dictated purely on how simple it is within it to make use of the special and unique properties of Quantum Computing in those instances where traditional techniques are inadequate.
Languages adapt. Big deal.
I’m sorry my post wasn’t more clear. I mean that that form of security will probably need to be more generally available in some way before quantum computing will be allowed to the public.
No, legal availability of quantum computing devices until security is able to counter its abilities.
Just to sum up:
If someone built a quantum computer today, it could be basically a regular computer with a quantum unit that could be called for factoring (Shor algorithm) or search (Grover algorithm). It would be programmed exactly as a regular computer, in C++, say, with these two functions added.
Or, you could build a computer that is totally quantum. To program it you would need to understand quantum superposition/entanglement. (I would argue that if you understand that, then you have a deep understanding of QM.) It would be easy to make a compiler that doesn’t take advantage of the QM properties, but to take advantage of them would be extremely difficult. Viz, no new algorithms in the last 8 years in spite of huge interest in the problem.