Slashdot Mirror
Quantum Computing Programming Language
William Walker writes "The Economist has an article in its new issue describing attempts to write a programming language for quantum computers, if and when they appear. It does a good job of putting the challenges of qubits versus regular bits into layman's terms. ... The original paper is here."
So how are they going to handle an infinite number of variables? Oh right, dont worry... Someone else's problem?
Perl's had support for quantum computing for three years, thanks to Damian Conway's Quantum::Superpositions module. I saw him do a presentation in Portland few months back, and it was pretty mind-blowing. It may seem odd to talk about programming a computer that doesn't exists yet, but Q::S actually works.
... in multiple universes :)
The promise of quantum computers is doing computations (as Damian says) "in multiple universes, in constant time" and Q::S obviously can't do this. It can and does, however, act like you're programming a quantum computer by allowing you to give one scalar multiple simultaneous values.
Like Perl wasn't confusing enough, now it's like programming line noise
This isn't as much "normalization" as it is "don't take so many drugs when you're designing tables."
Yes. With an infinite number of universes, there are an infinite number of you typing the code. Most of you will get it right and the computer will average the correct answer for you. So there, an infinite number of monkeys CAN write Shakespere, GUIs or anything else they please.
Microsoft has been working on this for a long time with their robot code from thier IDE. It still looks random and does not work quite right because they have not figured out how to make regular digital logic uncertian. When they figure that out, they will have it.
A gold star for you.
Friends don't help friends install M$ junk.
...paper a couple of years ago. Programming goes quantum, TRN March 28/April 4, 2001
Eric Smalley
I've put a little thought (very little) and it's a very interesting issue. First, for the doubters, they do have some quantum computing successes, the basics are proven. It's worth figuring out what the language is like. A couple things occur to me.
(1) Loops. Don't need them. You just have one line, when you use index "i", it contains all the possible values, so all loops are single statements.
OK, so in general, you won't have issues with flow logic, you write a forumula and theoretically all possible answers are in the output and the input also represents all possible inputs. So this languages is going to have less to do with flow control and more to do with filtering out all the unwanted answers. Not just "wrong" answers that don't fit, but extra answers. To use the looping analogy, if you have a qbyte index and would normally loop through to the total number of elements, the qbyte will loop through all it's values, some of which might be out of range, create numerical problems like divide by zero.
Ok, this should be easy for you to tear apart since it's not well thought through, but what do you expect, a freaking Quantum genius to post this?
In the paper they wrote, they claim that Grover's algorithm provides an exponential speed up over classical search algorithms. If I'm not mistaken, Grover's algorithm takes time O(N^(1/2)) while classical search algorithms take time O(N), which is only a quadratic speedup, not an exponential one... I'm sure the rest of their paper is well done, but this bothers me anyway.
Debugging quantum programs is going to be a real pain. This will allow a whole new type of bug. Before, people blamed bugs on faulty software, non-compliant compilers, and bad hardware. Soon they can blame their bugs on physics itself.
heisenbug: /hi:'zen-buhg/ n. [from Heisenberg's Uncertainty Principle in quantum physics] A bug that disappears or alters its behavior when one attempts to probe or isolate it. (This usage is not even particularly fanciful; the use of a debugger sometimes alters a program's operating environment significantly enough that buggy code, such as that which relies on the values of uninitialized memory, behaves quite differently.) Antonym of Bohr bug; see also mandelbug, schroedinbug. In C, nine out of ten heisenbugs result from uninitialized auto variables, fandango on core phenomena (esp. lossage related to corruption of the malloc arena) or errors that smash the stack.
Hey, at least your mom has the sense to ask how the technology applies to what she wants to do. My mom tries to understand all the details and then gets all confused. I remember when she went to the computer store to buy her first computer. She told me afterwards that a "very nice young (sales)man" helped her understand exactly what she needed in a computer. She told me that she was pretty sure that she wanted to get a computer with a ROM since that was necessary to get the computer to do what she wanted. When I explained to her that she didn't need to understand such details of the computer's inner workings if she just wanted to check her email and surf the web, she would hear none of it. After all, this wonderful salesman told her that she should make sure she knew exactly what she was getting. I wanted to hunt down that slick-talking asshole and strangle him for confusing her like that. When she started worrying aloud if she would have to buy some device drivers to make sure her mouse didn't become obsolete, I damn near screamed.
GMD
watch this
I'm sure there will be a reward for the first compiler that can compile itself for a quantum computer from a quantum computer.
On a side note, I really don't think quantum computers will overrun the market much though. There really is no need for them in your average application. Where they will be popular is in add-on cards. It will do wonders I presume for mathematical applications such as: graphics(will OpenGL work?), encryption, perhaps even some kind of strange storage device or network device will make use of quantum shenanigans someday. Anyone with mork knowledge on the subject care to comment about the possible uses in the non-research world other than breaking encryption? I can't think of many cases where NP problems are even used in day to day tasks. Besides traveling salesmen or theives trying to optimize their theivery, what else is actually a practical use?
Karma Clown
Having a superposition of states is really the exciting thing about quantum computing but as a concept there is really nothing new for any cs-majors.
Abstractions of this concept can be pretty well cooked up by nondeterministic programming and lazy evaluation but should one actually be able to run these on a quantum computer the speed-ups could be enormous.
The point being that with the above two concepts you can create even more general problem solving strategies than quantum computers would allow for, however in the same spirit, and use them with current computers. Having a language does not mean that you can really run it with any quantum computers. That's more of a job for a compiler.
I've seen several posts that imply that the its the job of the compiler to handle the parallelism. Quantum computers can only be exploited with highly specialized algorithms and as such, the compiler has no place. In fact people who study quantum computers today dont even use assembly language, they use gates.
It is clear to me that most people who think they have an idea of how quantum computers work don't. Now I'm not an expert, but I have studied up enough to know that they aren't just a happy parrallel abstraction. Most of the information you get on internet about quantum computers is completely bogus (as someone points out this paper appears to be).
Quantum computers are not universal; they cannot be used to do anything you want in "parallel universes".
I highly suggest people who even ponder quantum computers first get a reputable book on the subject.
I won't bet on it. Quantum computing is a fundamentally different idea. For most of the user experience, you don't need to solve N-P complete problems. There is a difference between doing something 20 times faster, and 2^20 times faster. A vast majority of algorithms that exist currently on the desktop are solvable in polynomial time - quantum computing for these is probably an overkill.
Like the parents' post said, travelling salesman problem was hard many decades ago, and is _still_ hard, irrespective of our computing speed increasing by many times. However, one major impact of Quantum computing that I can think of is, we need to invent new algorithms for encryption, and new paradigm for security. The current ones are based on the notion that they are computationally hard to crack.
And I also assume it is much harder to manufacture a quantum computer than a classical one. The idea of quantum computing is about 2 decades old (?), and we aren't even close to making one.
So I would like to know if we could cope up any similar concepts, just to get us starting.
Until now I see two concepts which might be similar, both or only one of them - you tell me, I'm a real new bee in Quantum Programming:
Backtracking - because this is an exponential fractal like algorithm (you call the function and this will repeat itself until exit conditions are true)
Parallel computing - because you different threads the same local variables might have different states
PS: knowing more about basic principles might help finding the best algorithm (somewhat like knowing about cache and writing algorithms around small buffers)