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."
Port Slashcode to this, and we'll have FP comments *before* the articles appear!
"Mod, mod, mod...and another troll bites the dust."
c??
-- Thou hast strayed far from the path of the Avatar.
attempts to write a programming language for quantum computers, if and when they appear
Just don't observe them and they will appear!
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."
http://tph.tuwien.ac.at/~oemer/qcl.html
It does a good job of putting the challenges of qubits versus regular bits into layman's terms.
:-)
Yea right. A sample run past my mom...
(Mom reads the article...)
Mom: Will this make FreeCell any easier?
Me: Well, a quantum computer could actually solve all the possible shuffles of FreeCell in one pass.
Mom: That wouldn't be any fun... Would the Internet be faster?
Me: Not until we get rid of your dialup and get you a cable modem.
and so on
www.christopherlewis.com
Better yet, Q#: the fastest way to negate any speed improvments gained by quantum computers.
. . . before this makes it into the Gnu Compiler Collection?
Al Qaeda has ninjas!
This article is about quantum programming, not Windows programming.
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.
my $cat = new Cat('Felix');
my $occupants = [$cat];
my $room = new Room($occupants);
$room->kill_occupant($cat);
# is he dead?
$room->status_occupant($cat);
# doh!
- James
Yes, not to be patronizing, but you're missing the point.
No matter how non-linear the programming of current software seems to be [i.e. through multithreading and object oriented programming], the software nonetheless relies on the fact that certain things will occur in a certain chronological order.
Quantum computing's power is in the ability to perform truly simultaneous, non-sequential operations. As a result, an entirely new language must be written to implement the new types of processes which are possible.
As an anology, consider the "programming language" of an abacus. When a computer is compared, you dont talk about writing a new "compiler" for abacus code on the computer, you write a new language. Similarly, quantum computing is in many ways something wholy different from normal computers.
"Stumble before you crawl"
even worse - half the time, when you order your quantum computer and you open the box, it will be DOA.
If I didn't know the difference between quantum superposition and tachyons, I'd probably have found that funny too.
Not quite. This is more like Boole working out the basic theories of digital logic in the mid-19th century, long before anyone thought of digital computers.
Jason
ProfQuotes
If we build something with qubits, should we call it an ark?
...paper a couple of years ago. Programming goes quantum, TRN March 28/April 4, 2001
Eric Smalley
Personally, I'm just waiting for someone to complain to me that they found a bug in my quantum code:
"It wasn't like that when I originally coded it! You must have looked at it or something! So it's really your bug now, isn't it?
GMD
watch this
if(1 && 0)
{
DoBothBranches();
}
else
{
DoBothBranchesAnyways();
}
else
{
WhatTheHellIsGoingOn();
goto PrintAnswerToQuestionYouWereThinkingOf();
}
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?
Let's not forget QCL (Quantum Computing Language) developed by Bernhard Oemer (a slashdotter) in 1998.
GOTO will be all the rage. Maybe they'll call it LEAP instead!
... when programs have Shroedinger's bugs.
Imagine debugging those. Are they squashed? Or are they squashed/unsquashed at the same time?
(Apologies to real physicists. I'm just being silly. In case you can't tell)
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.
Here's my take on the new language. (Sorry this is so simple for you seasoned programmers.)
... ,sqrt(N)}
Consider how you might factor a large number:
N = 23489803289
for (i=3;i lessthan N;i=i+2)
{
if (N/i has remainder 0)
FACTORS = i and N/i
}
This algorithm takes up to the square root of N tries to complete. This is really slow for big numbers.
If you look at the algorithm, even a quantum computer would not really be able to improve on it, unless you had an EXTREMELY smart compiler that could recognize that each try is independent and could be separated. But that is wishful thinking. Instead, consider using sets:
S: {3, 5, 7,
(S is the set of odd numbers from 3 to the square root of N)
Now the code might look like this:
Function Divide(S(x), N)
{
if (N/S(x) has remainder 0)
FACTORS = S(x) and N/S(x)
}
Now the Divide function would be called with the entire set. Compilers would still need to be smart, but the intent here is utilize the parallel processing of the New hardware. So I'm guessing a language similar to LISP might be a good starting point.
Thoughts?
No... quantum computing will not allow you to factor in constant time or anything, or by "assuming the answer", get back the factors. Your idea seems to be "let's take the result and then calculate backwards" so to speak. But that won't work. Now if we could create two superpositions of "all numbers between 0 and sqrt(c)" (to put it in an easy way), calculate the product and then find a way to filter out all results equal to c (which seems to be what you're looking for), then we'd of course be able to simply measure the factors. But the problem is that you can't "filter out" only the results you want to look at. You might be able to slightly increase the likelihood of measuring the 'correct c' and therefore getting correct factors. That's (very simply put) what Shor's algorithm is doing - it only manages to increase the likelihood to measure the right result and therefore retrieve correct factors.
Note that I'm grossly oversimplifying...
Another example is trying to solve 3CNF-SAT - figure out whether a formula in 3CNF can be satisfied - in O(1). Classically, it's an NP-complete problem with exponential complexity. Now the naïve attempt would be to create a superposition of all possible inputs, filter out only those that yield "true" as a result, and then measure the "filtered" superposition to get a solution. Same problem; you can't really filter out the "true" results, you can only make it slightly more likely to measure a "1" as a result and therefore retrieve a solution for the input. You'd still need to repeat that for a couple of times, only less often as in the classical case - but still not in O(1), or even O(n).
So no, quantum computing is not that much of a magic solve-everything-instantly machine... e.g. Grover's algorithm to find an element in an unsorted list will not bring you from classical O(n) to O(1), but rather O(sqrt(n)).
But then again, maybe you're just trolling :)
Anyway, I found this paper here very interesting: it's called "Quantum Computing for Non-Physicists".
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 can either tell you what milestone we're on, or how fast the project is progressing, but not both.
Error: Missing ';' near identifier 'qubit0'
(Could be you left out a semicolon, could be background cosmic radiation messing with your qubits)
hehe... Microsoft'll love this...
-------
"In times of universal deceit, telling the truth becomes a revolutionary act."
-- George Orwell
Gradual development....
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.
No you've gotten it quite wrong:
*All* the time, when you order your quantum computer and you open the box, it will be *both* DOA *and* fully functional. You simply won't know until you open the box.
It will, however, *always* contain a dead cat in the box.
With apologies to Bill Cosby
God: I want you to build an ark.
Noah: Right! What's an ark?
God: Get some wood. Build it 300 cubits by 80 cubits by 40 cubits.
Noah:Right! What's a cubit?
"My fingers Emit sparks of fire in Expectation of my future labours." William Blake
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.
An infinite number of ways to get from here to there?
A programming language already exists. It's called QCL by Bernhard Oemer.
It also includes an emulator with 64 qubits. Pretty neat.
He also wrote some very useful papers on understanding quantum computing.
------
wildmage
Memoirs of a Mad Scientist
Phase 1: Steal Underwear Phase 1: ??? Phase 1: Profit!
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)
"Seriously?! Now I have to change my PGP key..."
And to the poster who suggested a LISP-type language: no way. Too procedural. A parallel PROLOG is probably closer; you set up some initial conditions (both in terms of data and quantum 'procedures': i.e. the quantum objects), but since the solution is all simultaneous, you don't have to worry about back-tracking.
DNA is a Turing machine. You, however, being dynamic and emergent, are not.
I found this article to be a very useful. A nice starting block.