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."
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"
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
I have to say that while it's an excellent Perl module it's utterly useless for the purpose of describing/studying quantum computers.
Two criticisms I have from 20 seconds reading the CPAN page are
1. It only seems to handle equal superpositions
2. He seems to be unaware that even though you can perform computations in parallel on a superposition , you can only access the result of a SINGLE computation. So the primality testing example he includes isn't going to be running on a quantum computer.
The language Betteli et al describe isn't breaking any new ground in physics, but it's aim is probably to enable computer scientists to start trying to apply formal methods in analyzing quantum computer programs. Maybe they'll have more luck coming up with new algorithms.
:wq
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".
Gradual development....
Did you read the paper? If you had, you'd realize that the people who wrote the paper in fact do understand how quantum computers work, and they in fact do mainly think in terms of gates (well, primitive operations) as well.
The main point that they make is that a final quantum computer will be a hybrid of a classical computer and a quantum "add-on". The classical computer handles all portions of the algorithm that are deterministic, and sets up the quantum portions and controls the measurements.
There are many, many algorithms out there (okay, not 'many, many', but at least 'many') for quantum computers, and they even give code snippets for those portions. The code snippets contain many abstractions (like QFourier, QHadamard, etc.) which right now require a lot of tweaking and careful setting-up by the experimenters, but will hopefully in the future be automatable (I'm probably wrong - it's probably automatable now).
We know certain things about quantum computers - after all, we can build simulators for them trivially - it's just that the computations will take much much longer than they would on corresponding hardware (with sufficiently large N, where N is the number of elements to deal with, assuming a proper quantum computer with a sufficiently large number of qubits).
The paper's not bogus, and this kind of stuff is needed - it'll let people write algorithms in a standard defined way, and eventually when a quantum computer is built, they can construct a "compiler" for it fairly trivially. In this case, a compiler is not what we normally think of as a compiler - it's more like a processor - something that takes instructions and performs the operations on the setup.
This paper is the equivalent of saying "Well, if we're going to build a computer, we need to know what instructions we want to process. What do we need? AND, OR, XOR, LOAD, STORE, ADD, SHIFT." Here it's more complicated, but it's the same idea - just with a quantum computing paradigm.
The current state of quantum computing really doesn't have a 'processor' - the experimenters set things up, and let things run. Eventually that'll change, and this is anticipating it. I think you're being a bit naive to think that a general-purpose quantum computer setup could never be built. Anything that experimenters can do, engineers can automate.
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.