Please create an account to participate in the Slashdot moderation system

 


Forgot your password?
Close
typodupeerror
×
Programming IT Technology

Quantum Computing Programming Language 232

Posted by timothy from the boy-scout-motto dept.
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."
This discussion has been archived. No new comments can be posted.

Quantum Computing Programming Language More

Quantum Computing Programming Language

Comments Filter:

  • Future work... (Score:5, Funny)

    by Cutriss ( 262920 ) on Thursday April 03, 2003 @06:34PM (#5656353) Homepage
    Port Slashcode to this, and we'll have FP comments *before* the articles appear!

  • A name for the new quantum language (Score:5, Funny)

    by dfn5 ( 524972 ) on Thursday April 03, 2003 @06:37PM (#5656385) Journal
    c??

  • Heisenberg says... (Score:5, Funny)

    by pr0nbot ( 313417 ) on Thursday April 03, 2003 @06:39PM (#5656397)

    attempts to write a programming language for quantum computers, if and when they appear

    Just don't observe them and they will appear!

  • I mean, C is portable across endless architectures. It would seem far more sensical to put efforts into a new C compiler. If parallelism is required, surely the compiler can simply find bits of code which can execute in parallel without affecting each other.

    And of course, C++ objects can execute independently of one another.

    Blah, I must just be missing the point. Fuzzy bits, which are read in a non-fuzzy manner? The applications are endless!

    Never mind.

    • Re:Isn't this the job of the compiler? (Score:5, Insightful)

      by The Only Druid ( 587299 ) on Thursday April 03, 2003 @06:52PM (#5656487)
      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.
    • All right then, try implementing Shorr's factorization algorithm in C.

  • Seen Quantum::Superpositions (Score:5, Interesting)

    by legLess ( 127550 ) on Thursday April 03, 2003 @06:44PM (#5656432) Journal
    Perl's had support for quantum computing for three years, thanks to Damian Conway's Quantum::Superpositions [cpan.org] 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.

    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 ... in multiple universes :)

    • Re:Seen Quantum::Superpositions (Score:5, Insightful)

      by nihilogos ( 87025 ) on Thursday April 03, 2003 @06:55PM (#5656519)
      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.

      • It's meant to be more of a novelty than a practical example of quantum computing. There's also a Quantum::Entanglement module, allowing you to put variables in a superposition of states, do some calculations on them, and then "observe" the value of the result. The observation then causes the states of all of the other variables along the way to instantly resolve into states consistent with that observation.

    • Re:Seen Quantum::Superpositions (Score:5, Interesting)

      by .com b4 .storm ( 581701 ) on Thursday April 03, 2003 @09:08PM (#5657549)

      To give people an example of what Quantum::Superpositions does, take the following snippet of code:

      if($foo == 1 && $foo == 2 && $foo == 3) {
      print "hooray";
      }

      With traditional Perl, such a condition could never evaluate to true. After all, if $foo is 1, how can $foo be 2 and 3 as well? Now take a look at the following:

      use Quantum::Superpositions;

      my $foo = any(1, 2, 3);

      if($foo == 1 && $foo == 2 && $foo == 3) {
      print "hooray";
      }

      Thanks to our Quantum-powered Perl (heh), this condition is true. $foo is 1, 2, and 3 all at once. Sort of. In quantum terms, $foo isn't any of those values. But once you test $foo to see if it is 1, it becomes 1. And when you look to see if it's 2, it becomes 2, etc. But if you test $foo to see if it is 4, it is not - that's not one of the possible values.

      • (quote)
        use Quantum::Superpositions;
        my $foo = any(1, 2, 3);
        if($foo == 1 && $foo == 2 && $foo == 3) {
        print "hooray";
        }
        (end quote)

        Can it be encapsulated behind API's like?:

        if(spookyShit($foo,[1,2,3])) {
        print "hooray";
        }

  • for those who cant wait (Score:3, Informative)

    by RidRash ( 660853 ) on Thursday April 03, 2003 @06:45PM (#5656437)
    http://tph.tuwien.ac.at/~oemer/qcl.html

  • layman's terms... yea right (Score:5, Funny)

    by Christopher_G_Lewis ( 260977 ) on Thursday April 03, 2003 @06:46PM (#5656452) Homepage
    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 :-)

    • 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 wante

  • How long . . . (Score:3, Funny)

    by cjpez ( 148000 ) on Thursday April 03, 2003 @06:49PM (#5656465) Homepage Journal
    . . . before this makes it into the Gnu Compiler Collection?

  • Sample line of code (Score:5, Funny)

    by jamesmartinluther ( 267743 ) on Thursday April 03, 2003 @06:49PM (#5656475) Homepage
    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
  • I think a quantum language would half to assume the answer. eg:

    factor ( int c ){
    int a, b;

    a * b = c;
    a > 1;
    b > 1;
    c > a;
    c > b;
    b >= a;
    print a, b;

    }

    if c = 91, then it would print 7, 13 - because that's the only answer, and if there was no answer than it would be null, it there were multiple answers it would print a random working answer.

    • I think a quantum language would half to assume the answer. eg: factor ( int c ){ int a, b; a * b = c; a > 1; b > 1; c > a; c > b; b >= a; print a, b; } if c = 91, then it would print 7, 13 - because that's the only answer, and if there was no answer than it would be null, it there were multiple answers it would print a random working answer.

      Well done you have just written a prolog program

    • Re:languages that assume answers (Score:5, Insightful)

      by mindriot ( 96208 ) on Thursday April 03, 2003 @07:23PM (#5656714)

      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 [uni-augsburg.de] here very interesting: it's called "Quantum Computing for Non-Physicists".

      • You cant even do SAT in polynomial time with a quantum computer.

        In fact, there really is no proof that quantum computers can do anything that (specialized) classical computers cant do.

        I have seen hardware that uses content-addressable memory to data-search, or even sort, in O(1) time, and it doesnt use any quantum mumbo-jumbo.

        Interestingly, even Shor's factoring algorithm may not be special. You see, nobody knows what the actually operating time of factoring on a determistic machine is; it is quite poss
  • ...paper a couple of years ago. Programming goes quantum [trnmag.com], TRN March 28/April 4, 2001

  • Sample code: (Score:5, Funny)

    by Anonymous Coward on Thursday April 03, 2003 @07:00PM (#5656558)
    if(1 && 0)
    {
    DoBothBranches();
    }
    else
    {
    DoBothBranchesAnyways();
    }
    else
    {
    WhatTheHellIsGoingOn();
    goto PrintAnswerToQuestionYouWereThinkingOf();
    }

  • Strangeness (Score:4, Interesting)

    by Anonymous Coward on Thursday April 03, 2003 @07:08PM (#5656609)
    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?

  • Quantum Computing Language exists. (Score:3, Informative)

    by zCyl ( 14362 ) on Thursday April 03, 2003 @07:13PM (#5656650)
    Let's not forget QCL (Quantum Computing Language) [tuwien.ac.at] developed by Bernhard Oemer (a slashdotter) in 1998.

  • Yay (Score:5, Funny)

    by dubbayu_d_40 ( 622643 ) on Thursday April 03, 2003 @07:14PM (#5656653)
    GOTO will be all the rage. Maybe they'll call it LEAP instead!

  • The real problem will be... (Score:4, Funny)

    by FurryFeet ( 562847 ) <joudanxNO@SPAMyahoo.com> on Thursday April 03, 2003 @07:17PM (#5656667)
    ... 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)

  • A nitpick... (Score:2, Interesting)

    by Chinju ( 662523 )
    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 [astrian.net]: /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 pr

  • Perhaps the new language might be Set oriented? (Score:5, Insightful)

    by Mr. Asdf ( 267041 ) on Thursday April 03, 2003 @07:18PM (#5656684) Homepage
    Here's my take on the new language. (Sorry this is so simple for you seasoned programmers.)

    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, ... ,sqrt(N)}
    (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?
    • And after you measure the result of Divide on the entire set you get the answer to ONE of the test divisions. Just one. The whole thing would have been quicker on your pocket calculater.
    • How do you think this relates to quantum computers exactly? The very idea here is way way off base. Quantum computation is statistical. Solutions are built into a superposistion of answers, which must be clevery designed to positively interfere in order to create a signal that has a statistical chance of objectifying.

      Take a good long look at Shor's algorithm to get an idea how this actually works.

  • superpositions are nothing new in cs! (Score:3, Interesting)

    by inburito ( 89603 ) on Thursday April 03, 2003 @07:33PM (#5656776)
    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 [mit.edu] and lazy evaluation [mit.edu] 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.

  • A natural feature for a quantum computer language (Score:3, Funny)

    by Waffle Iron ( 339739 ) on Thursday April 03, 2003 @07:34PM (#5656782)
    I propose this useful builtin library function:

    decrypt(cyphertext)

    returns tuple: (public_key, private_key, plaintext)

  • Quantum Computing Jobs (Score:4, Funny)

    by YetAnotherName ( 168064 ) on Thursday April 03, 2003 @07:40PM (#5656828) Homepage
    I'd wager some lame-brain human resources departments (under direction from pointy-haired bosses) will soon start posting job advertisements for this theoretical language on non-existent hardware:
    WANTED: Software development engineers and software QA engineers. Require three to five years experience with qubit-based systems (Q#, Qava, etc.).
    After all, Java jobs appeared (requiring a minimum four years experience) when Java was just two years old.
    • WANTED: Software development engineers and software QA engineers. Require three to five years experience with qubit-based systems (Q#, Qava, etc.).

      Interviewer: How many years of experience in quantum programming do you have and in which languages?
      Applicant: Last time I checked it was 4 years in Q++ and Turbo Q.
      Interviewer: So you have 4 years of experience in Q++ and Turbo Q?
      Applicant: To be honest I can't be sure of it anymore.
      Interviewer: Gnah!
  • Comment removed based on user account deletion

  • Quantum Project Management... (Score:3, Funny)

    by PinchDuck ( 199974 ) on Thursday April 03, 2003 @07:50PM (#5656943)
    I can either tell you what milestone we're on, or how fast the project is progressing, but not both.

  • Debugging (Score:3, Funny)

    by miketang16 ( 585602 ) on Thursday April 03, 2003 @07:50PM (#5656945) Journal
    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...

  • A little premature? (Score:4, Insightful)

    by sketerpot ( 454020 ) <sketerpot&gmail,com> on Thursday April 03, 2003 @07:55PM (#5656982)
    Doesn't this seem a little early to be making real programming languages for quantum computers? I was thinking that the first languages would be things that quantum computer researchers just sort of hack up quickly, and then when quantum computers are here they'll get decent languages. Suppose that these people spend a whole lot of effort on these first-generation languages---will they want to discover that a different approach is better, and wish they had taken it from the start?

    Gradual development....

  • Not just a simple abstraction (Score:4, Interesting)

    by rufusdufus ( 450462 ) on Thursday April 03, 2003 @07:55PM (#5656985)
    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.
    • My thoughts exactly. We are talking about multi-state machines here. We cannot abstract what we know today into these new machines.

      Think back to the ENIAC. Did the hardware or software come first? Did they write a language before the computer? No they didn't, they toggled the switches manually and the languages and refinements came later.

      Correct me if I'm wrong here, (it may be still too 2 dimensional) but I envision:

      {
      if( bitstate ) !& maybe
      result = maybe(bitstate) & not(bitstate)
    • 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
      • I did read the paper. The problem is that the language they are building is neither necessary nor sufficient to describe quantum algorithms. It allows you to string together a handful of quantum operations with classical code. The problem of course is that those operations are not sufficient to do anything new; the interesting stuff (if there is any) is in that layer below the language, unreachable by the language.

        As far as a general purposes quantum computer setup, I think it is naive to assume it can b
  • Looking at the screen for too long...

    "The trick is to find a way to describe, in a
    manner useful to computer scientists, the
    urinary transformations that underlie a
    program."

    Quantum pee!!!

  • Qubits (Score:2, Funny)

    by talleyrand ( 318969 )
    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?

  • It's called QCL [tuwien.ac.at] and you can get an emulator for it that runs on Linux.

  • Isn't that Perl? (Score:2, Funny)

    by Anonymous Coward
    An infinite number of ways to get from here to there?

  • A programming language already exists. It's called QCL [tuwien.ac.at] by Bernhard Oemer.

    It also includes an emulator with 64 qubits. Pretty neat.

    He also wrote some very useful papers [tuwien.ac.at] on understanding quantum computing.

  • superposed phases (Score:4, Funny)

    by sstory ( 538486 ) on Thursday April 03, 2003 @10:18PM (#5657945) Homepage
    Phase 1: Steal Underwear Phase 1: ??? Phase 1: Profit!
  • Move huge numbers of electrons from one capacitor to another with a single statement. Cause electrons to speed down long wires and recombine with holes.

    Seriously: if you feel you must muck around with quantum states, a simple library like QDD [sourceforge.net] will probably do. Or have a look here [ex.ac.uk].

    If quantum computers ever do anything useful--and that's a big "if"--then most likely you will just be using it through high-level operations and datatypes.

  • According to the article these quantum computers will use registers and operators. The registers will be useful for holding pointers to memory locations. The operators will include boolean operators.

    Also according to the article these low-level constructs will eventually combined into "objects" consisting of both commands and data.

    Wow. It's hard to imagine such a computer. This is some futuristic stuff!

    -Peter
  • Most of us I think are new bees in Quantum Programming, but we have a pretty good background in linear and parallel programming (things before quantum :-)).

    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 unti

  • "Did you hear about that quantum computer that factored 15?"

    "Seriously?! Now I have to change my PGP key..."

  • Like early computing; closer to PROLOG than LISP (Score:3, Insightful)

    by Randym ( 25779 ) on Friday April 04, 2003 @04:19AM (#5659330)
    After reading the Bettelli paper, it appears that, just like on the early computers, you have to first build the computer out of the quantum objects (initialization) before you can use it. (Initialization is analogous to setting up the connections between the plug-boards.) Then you use it to solve your problem (evolution) [in today's terms, imagine a Transmeta box modifying itself as the solution to the problem progresses], then you have to interpret the results (finalization). (like reading off the mercury cylinders in the days of yore -- only here, of course, each cylinder vanishes into oblivion as you 'read' it).

    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.

  • Here's a question to the Slashdot crowd: What resources on quantum computing and quantum mechanics are out there? I'm asking from the perspective of a computer scientist who has heard of quantum computing and know the very basics, but has yet to delve any deeper into it.

    Which websites would be useful? What books would be useful? What else would you do to gain a better understanding of the theory?
  • Does quantum computing mean that the question 'array or list ?" is eliminated ? since quantum searches will become constant time.

    Does this also mean that DB indexing would be a thing of the past ?

Slashdot Top Deals

Software production is assumed to be a line function, but it is run like a staff function. -- Paul Licker

Close