1 "John Eastmond" |
A progamming language for quantum computers? | woensdag 26 maart 2003 1:18 |
2 "Lawrence Foard" |
Re: A progamming language for quantum computers? | woensdag 26 maart 2003 2:48 |
3 "Kevin A. Scaldeferri" |
Re: A progamming language for quantum computers? | woensdag 26 maart 2003 3:16 |
4 "Daryl McCullough" |
Re: A progamming language for quantum computers? | woensdag 26 maart 2003 6:26 |
5 "Robert Tucci" |
Re: A progamming language for quantum computers? | donderdag 27 maart 2003 8:52 |
6 "Ken S. Tucker" |
Re: A progamming language for quantum computers? | vrijdag 28 maart 2003 1:39 |
7 "Squark" |
Re: A progamming language for quantum computers? | vrijdag 28 maart 2003 1:40 |
8 "Peter Shor" |
Re: A progamming language for quantum computers? | vrijdag 28 maart 2003 5:48 |
9 "Kevin A. Scaldeferri" |
Re: A progamming language for quantum computers? | vrijdag 28 maart 2003 5:48 |
10 "Hendrik Weimer" |
Re: A progamming language for quantum computers? | vrijdag 28 maart 2003 21:23 |
11 "Michael Weiss" |
Re: A progamming language for quantum computers? | vrijdag 28 maart 2003 21:24 |
12 "David Madore" |
Re: A progamming language for quantum computers? | zaterdag 29 maart 2003 18:42 |
13 | Re: A progamming language for quantum computers? | zaterdag 29 maart 2003 18:51 |
14 "Robert Tucci" |
Re: A progamming language for quantum computers? | zaterdag 29 maart 2003 18:53 |
15 "Robert Tucci" |
Re: A progamming language for quantum computers? | zaterdag 29 maart 2003 18:55 |
16 "Squark" |
Re: A progamming language for quantum computers? | zaterdag 29 maart 2003 18:59 |
17 "David Wnsemius" |
Re: A progamming language for quantum computers? | dinsdag 1 april 2003 0:04 |
18 "Nicolaas Vroom" |
Re: A progamming language for quantum computers? | dinsdag 1 april 2003 0:11 |
19 "Robert Tucci" |
Re: A progamming language for quantum computers? | dinsdag 1 april 2003 0:12 |
20 "Squark" |
Re: A progamming language for quantum computers? | dinsdag 1 april 2003 9:03 |
21 "Robert Tucci" |
Re: A progamming language for quantum computers? | dinsdag 1 april 2003 9:03 |
22 "Kevin A. Scaldeferri" |
Re: A progamming language for quantum computers? | dinsdag 1 april 2003 9:24 |
23 "Kevin A. Scaldeferri" |
Re: A progamming language for quantum computers? | dinsdag 1 april 2003 9:24 |
24 "Ralph Hartley" |
Re: A progamming language for quantum computers? | dinsdag 1 april 2003 9:42 |
25 "Ken S. Tucker" |
Re: A progamming language for quantum computers? | dinsdag 1 april 2003 20:40 |
26 "Hendrik Weimer" |
Re: A progamming language for quantum computers? | dinsdag 1 april 2003 20:43 |
27 "Kevin A. Scaldeferri" |
Re: A progamming language for quantum computers? | dinsdag 1 april 2003 23:42 |
28 "Gralp" |
Re: A progamming language for quantum computers? | woensdag 2 april 2003 22:13 |
29 "Squark" |
Re: A progamming language for quantum computers? | woensdag 2 april 2003 22:19 |
30 "Ralph Hartley" |
Re: A progamming language for quantum computers? | donderdag 3 april 2003 0:21 |
31 "Robert Tucci" |
Re: A progamming language for quantum computers? | donderdag 3 april 2003 23:59 |
32 "Kevin A. Scaldeferri" |
Re: A progamming language for quantum computers? | vrijdag 4 april 2003 0:46 |
33 "Dirk Bruere at Neopax" |
Re: A progamming language for quantum computers? | vrijdag 4 april 2003 5:40 |
34 "Hendrik Weimer" |
Re: A progamming language for quantum computers? | zaterdag 5 april 2003 0:12 |
35 "Nicolaas Vroom" |
Re: A progamming language for quantum computers? | zaterdag 5 april 2003 0:14 |
36 "Ralph Hartley" |
Re: A progamming language for quantum computers? | zaterdag 5 april 2003 0:16 |
37 "Kevin A. Scaldeferri" |
Re: A progamming language for quantum computers? | dinsdag 8 april 2003 3:46 |
38 "Kevin A. Scaldeferri" |
Re: Deterministic vs random | dinsdag 8 april 2003 6:42 |
39 "Alfred Einstead" |
Re: Deterministic vs random | woensdag 9 april 2003 23:27 |
40 "Kevin A. Scaldeferri" |
Re: Deterministic vs random | donderdag 10 april 2003 22:59 |
41 "Nicolaas Vroom" |
Re: A progamming language for quantum computers? | maandag 21 april 2003 22:19 |
42 "Robert Tucci" |
Re: A progamming language for quantum computers? | woensdag 23 april 2003 22:34 |
43 "Nicolaas Vroom" |
Re: A progamming language for quantum computers? | woensdag 30 april 2003 8:39 |
44 "Kevin A. Scaldeferri" |
Re: A progamming language for quantum computers? | woensdag 30 april 2003 22:48 |
45 "Robert Tucci" |
Re: A progamming language for quantum computers? | donderdag 1 mei 2003 0:39 |
46 "Nicolaas Vroom" |
Re: A progamming language for quantum computers? | donderdag 8 mei 2003 2:12 |
47 "Robert Tucci" |
Re: A progamming language for quantum computers? | vrijdag 9 mei 2003 4:41 |
48 "Kevin A. Scaldeferri" |
Re: A progamming language for quantum computers? | zaterdag 10 mei 2003 2:39 |
49 "Nicolaas Vroom" |
Re: A progamming language for quantum computers? | donderdag 15 mei 2003 20:04 |
50 "Kevin A. Scaldeferri" |
Re: A progamming language for quantum computers? | zaterdag 17 mei 2003 1:24 |
51 "Nicolaas Vroom" |
Re: A progamming language for quantum computers? | zaterdag 17 mei 2003 22:48 |
52 "Kevin A. Scaldeferri" |
Re: A progamming language for quantum computers? | vrijdag 23 mei 2003 1:32 |
53 "Nicolaas Vroom" |
Re: A progamming language for quantum computers? | maandag 26 mei 2003 21:50 |
54 "Kevin A. Scaldeferri" |
Re: A progamming language for quantum computers? | dinsdag 27 mei 2003 22:55 |
55 "Hendrik Weimer" |
Re: A progamming language for quantum computers? | woensdag 28 mei 2003 6:52 |
56 "Dirk Bruere at Neopax" |
Re: A progamming language for quantum computers? | donderdag 29 mei 2003 9:03 |
57 "Dirk Bruere at Neopax" |
Re: A progamming language for quantum computers? | vrijdag 30 mei 2003 7:01 |
58 "Hendrik Weimer" |
Re: A progamming language for quantum computers? | vrijdag 30 mei 2003 20:15 |
59 "Kevin A. Scaldeferri" |
Re: A progamming language for quantum computers? | maandag 2 juni 2003 2:59 |
60 "Kevin A. Scaldeferri" |
Re: A progamming language for quantum computers? | maandag 2 juni 2003 3:09 |
61 "Nicolaas Vroom" |
Re: A progamming language for quantum computers? | maandag 2 juni 2003 7:29 |
62 "Nicolaas Vroom" |
Re: A progamming language for quantum computers? | maandag 2 juni 2003 7:33 |
63 "Dirk Bruere at Neopax" |
Re: A progamming language for quantum computers? | maandag 2 juni 2003 19:55 |
64 "Hendrik Weimer" |
Re: A progamming language for quantum computers? | dinsdag 3 juni 2003 6:16 |
65 "Ralph Hartley" |
Re: A progamming language for quantum computers? | donderdag 5 juni 2003 0:49 |
66 "Kevin A. Scaldeferri" |
Re: A progamming language for quantum computers? | dinsdag 10 juni 2003 2:15 |
67 "Nicolaas Vroom" |
Re: A progamming language for quantum computers? | Wed, 26 Mar 2003 13:39:56 |
68 "Nicolaas Vroom" |
Re: A progamming language for quantum computers? | Sun, 30 Mar 2003 13:29:01 |
69 "Nicolaas Vroom" |
Re: A progamming language for quantum computers? | Wed, 09 Apr 2003 20:35:28 |
70 "Nicolaas Vroom" |
Re: A progamming language for quantum computers? | Thu, 01 May 2003 16:11:42 |
71 "Nicolaas Vroom" |
Re: A progamming language for quantum computers? | Sat, 17 May 2003 16:08:56 |
The last 5 messages were either rejected or are "still in process" in sci.physics.research
I've seen quantum computers described by networks of quantum gates in a manner analogous to how classical computers are made up of boolean logic gates. However most people who work with classical computers are not concerned with their hardware but rather with the software that runs on it. I was wondering what computer language one would use to program quantum computers.
I guess one could image a simple procedural language in which one has a command to read any qubit (by projecting onto the |0>, |1> basis set) and branch on the result. I guess one would then have quantum parallelism in that if the qubit was in a superposition of |0> and |1> then both code paths would be taken by the quantum computer. I guess a general write command would be different because one would want to be able to write a general superposition into a qubit. I suppose that writing a superposition of |0> and |1> at any point in the code rather than |0> or |1> would cause the code path to split when that superposition is read and cause quantum parallelism to occur in the manner described above. Would these two commands, write and read-branch, be enough to program any quantum calculation?
John Eastmond
In article
> | I've seen quantum computers described by networks of quantum gates in a manner analogous to how classical computers are made up of boolean logic gates. However most people who work with classical computers are not concerned with their hardware but rather with the software that runs on it. I was wondering what computer language one would use to program quantum computers. |
Slight topic divergence here. Am I the only rationalists out there hoping that quantum computing fails? Rather than providing infinite computing power, it may instead provide a deeper understanding of the meaning of quantum mechanics by its failure.
Around me I see a world with very large but finite computing power, my
intuition tells me that we will fail to extract many orders of magnitude
more computing power from the world than the world already demonstrates.
Of course I could be wrong and the world is really as weird as everyone
says, but until a quantum computer is doing amazing and otherwise
impossible feats I'll remain a skeptic.
--
Be a counter terrorist perpetrate random senseless acts of kindness
Rave: Immanentization of the Eschaton in a Temporary Autonomous Zone.
"Anyone who trades liberty for security deserves neither liberty nor security"
-Benjamin Franklin
In article
> | I've seen quantum computers described by networks of quantum gates in a manner analogous to how classical computers are made up of boolean logic gates. However most people who work with classical computers are not concerned with their hardware but rather with the software that runs on it. I was wondering what computer language one would use to program quantum computers. |
This seems to be only very slightly about physics, so I will be brief.
I would hope that one would use any and all of the usual languages. C, Java, Lisp, Perl, Fortran, etc. The whole reason to have high level languages is to free you from having to think about the underlying machine architecture (too much).
I guess from the below, you are wondering more like what the machine language for a quantum computer would be like?
> | I guess one could image a simple procedural language in which one has a command to read any qubit (by projecting onto the |0>, |1> basis set) and branch on the result. I guess one would then have quantum parallelism in that if the qubit was in a superposition of |0> and |1> then both code paths would be taken by the quantum computer. I guess a general write command would be different because one would want to be able to write a general superposition into a qubit. I suppose that writing a superposition of |0> and |1> at any point in the code rather than |0> or |1> would cause the code path to split when that superposition is read and cause quantum parallelism to occur in the manner described above. Would these two commands, write and read-branch, be enough to program any quantum calculation? |
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
> |
I've seen quantum computers described by networks of quantum gates in a manner analogous to how classical computers are made up of boolean logic gates. However most people who work with classical computers are not concerned with their hardware but rather with the software that runs on it. I was wondering what computer language one would use to program quantum computers. |
As a matter of fact, my company (ATC-NY, formerly Odyssey Research Associates) is involved in a small project to develop a programming language for quantum computing. I'm not on the project, so I can't say much about it except what is found on our website:
http://www.oracorp.com/extdR&d.html#quantum
-- Daryl McCullough daryl@atc-nycorp.com Ithaca, NY
Since quantum mechanics is ultimately a theory about probabilities, if I were you, I would look for inspiration at already existing software that handles complicated calculations with classical probabilities.(eg. bayesian nets, fuzzy logic, etc.) In my opinion, trying to design a quantum computer programming language that ignores lessons learned from existing classical probability software is like reinventing the wheel.
Robert R. Tucci www.ar-tiste.com (a quantum computer programming company)
tucci@ar-tiste.com (Robert Tucci) wrote: in message news:
>
Since quantum mechanics is ultimately a theory about probabilities, if
I were you, I would look for inspiration at already existing software
that handles complicated calculations with classical
probabilities.(eg. bayesian nets, fuzzy logic, etc.) In my opinion,
trying to design a quantum computer programming language that ignores
lessons learned from existing classical probability software is like
reinventing the wheel.
Robert R. Tucci
www.ar-tiste.com (a quantum computer programming company)
Ok, but one still needs to get to an assembler/machine code, higher level languages can run on, or be compiled for. For most *upwardly compatible* chips this instruction code is many hundreds. As a matter of history the famous IC TTL 74xx series began with 7400, a quad 2 input NAND (NOT AND) gate. The idea is that with NAND's you can build all other logic functions AND, OR, NOR, XOR, NONXOR (I think I can still prove this if requested). 2 input NAND returns 1 unless both inputs are 1 then it returns 0. Physically, with X being a shut-off and (1) a source, this is produced in a diagram like, (hoping my ascii fig. isn't mutiltated),
A___________ | ___X___ (1)___ | |____(o/p) |___X___| | B___________|What is needed is the specific quantum mechanical process to be used for a logical decision that will create this gate, or perhaps a two step process is required.(o/p)= 1, unless A AND B shut off (1).
kevin@sue.its.caltech.edu (Kevin A. Scaldeferri) wrote
in message news:
I would hope that one would use any and all of the usual languages.
C, Java, Lisp, Perl, Fortran, etc. The whole reason to have high
level languages is to free you from having to think about the
underlying machine architecture (too much).
> >
I was wondering what computer language one would use to
program quantum computers.
>
I doubt that, somehow. You are free from having to think about the architecture up to some limits, and switching from classical to quantum computations appears to cross those limits. It is hard for me to imagine how you would implement a genuine quantum quantum algorithm like Schur's factorization using a standard language like C. At the least you would have to introduce additional arithmetics / boolean operators. However, considering the possibility of applying the quantum operators to the variable controlling program flow (i.e. the pointer to the currently executed command), this probably wouldn't be enough.
Best regards, Squark
------------------------------------------------------------------
Write to me using the following e-mail:
Skvark_Nuclearsto@excite.exe
(just spell the particle name correctly and change the
extension in the obvious way)
entropy@farviolet.com (Lawrence Foard) wrote
> | Slight topic divergence here. Am I the only rationalist out there hoping that quantum computing fails? |
Not at all.
> |
Rather than providing infinite computing power, it may instead
provide a deeper understanding of the meaning of quantum mechanics
by its failure.
Around me I see a world with very large but finite computing power, my intuition tells me that we will fail to extract many orders of magnitude more computing power from the world than the world already demonstrates. Of course I could be wrong and the world is really as weird as everyone says, but until a quantum computer is doing amazing and otherwise impossible feats I'll remain a skeptic. |
The proponents of "Digital Philosophy," including Ed Fredkin, believe that quantum computing can't work. And it also seems to follow from some of the things Wolfram says in his book "New Kind of Science" (not surprising, since the "digital philosophers" claim that Wolfram stole the whole idea from them); however, it's not completely clear to me from his book what Wolfram's opinion is. And even if you discount the "digital philosophers" as being a little bit crazy, there are also quite a number of otherwise sensible computer scientists and mathematicians who expect that quantum computing will fail. The only one I'll mention is Leonid Levin; I expect he won't mind being named since his opinions on his web page, and he is also probably the most notable, being the co-discoverer of NP-completeness (along with Stephen Cook; this is one of many discoveries which happened independently on either side of the Iron Curtain).
I don't know any physicists who share this view, but I wouldn't be surprised if there were some. Note that I'm not counting here the fairly large number of physicists who believe quantum computing won't happen not because it's fundamentally impossible but because it is too difficult an engineering problem.
I do expect that if quantum computing is discovered to fail due to fundamental reasons, somebody will win a Nobel Prize for this discovery.
Peter Shor
And I can't resist adding that quantum computing doesn't actually provide infinite computing power. Anything a quantum computer can do in time n, a classical computer can do in time 2^n. And in my opinion, it doesn't even provide exponential computing power, but rather a different kind of computing power. To float an anology, if somebody built a windmill in a solar-powered world, the correct response should not be "Wow ... you can get this much power from starlight - just think what your machine will be able to do in the daytime." But this type of fallacy is exactly the natural response to media quotes of "A quantum computer could factor in minutes a number which would take a convential computer millions of years."
In article <939044f.0303271009.10f32c38@posting.google.com>,
Squark
> |
kevin@sue.its.caltech.edu (Kevin A. Scaldeferri) wrote in message
news: |
>> > | I was wondering what computer language one would use to program quantum computers. |
>> | I would hope that one would use any and all of the usual languages. C, Java, Lisp, Perl, Fortran, etc. The whole reason to have high level languages is to free you from having to think about the underlying machine architecture (too much). |
> | I doubt that, somehow. You are free from having to think about the architecture up to some limits, and switching from classical to quantum computations appears to cross those limits. It is hard for me to imagine how you would implement a genuine quantum quantum algorithm like Schur's factorization using a standard language like C. |
It is probably best not to think too much about "languages" like C in this regard, since it doesn't have any formal definition.
However, let's think about Lisp instead. In some crude sense, quantum computers are a little like non-deterministic machines. Now, it's not that hard to describe a non-deterministic algorithm in Lisp. Evaluating it might be slow because we have to simulate a non-deterministic machine, but it's possible.
More generally, I didn't think that quantum computers were known to be more powerful than Turing machines / lambda calculus. They may be more efficient at some computations, but not more powerful. Perhaps I'm wrong about that, but if I'm not than you should be able to program a QC in Lisp (or in any other rigorously-defined, Turing-complete language).
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
eastmond@yahoo.com (John Eastmond) writes
> | I've seen quantum computers described by networks of quantum gates in a manner analogous to how classical computers are made up of boolean logic gates. However most people who work with classical computers are not concerned with their hardware but rather with the software that runs on it. |
I think there are several reason why this problem hasn't caught much attention so far. One point is that there are only a few quantum algorithms which outperform their classical counterparts, so a high-level programming language is a bit of overkill. Another point is that most current ideas regard the quantum computer as a device controlled by a classical computer. This means that even if quantum computers are available the programming interface will still be classical.
> | I was wondering what computer language one would use to program quantum computers. |
An example for a language designed for quantum computers is QCL (http://www.tph.tuwien.ac.at/~oemer/qcl.html).
Hendrik Weimer
--
libquantum - Simulation of a Quantum Computer
http://www.enyo.de/libquantum/
: : More generally, I didn't think that quantum computers were known to be : more powerful than Turing machines / lambda calculus. They may be : more efficient at some computations, but not more powerful. Perhaps : I'm wrong about that, but if I'm not than you should be able to : program a QC in Lisp (or in any other rigorously-defined, : Turing-complete language).
Depends what you mean by programming an algorithm. Roughly speaking, for T to be Turing-complete just means that given any algorithm A_m expressed in language M, there is *an equivalent* algorithm A_t expressed in the language T --- where equivalent means, computes the same function. You can't necessarily express the original algorithm A_m in the language T.
The proof that quantum computers can compute only recursive functions uses simulation. A conventional computer can simulate a quantum computer by keeping track of what happens to all the various amplitudes, doing matrix multiplications to represent the effect of the quantum gate operations. By the time this is programmed in a conventional language, you have all sorts of dandruff(loops, loop counters, etc.) that don't belong in the quantum algorithm. You could write a "quantumizing" compiler for your quantum computer that would recognize what your program is really trying to do, and translate it back into the desired quantum operations. Or you could extend the language to express your meaning explicitly.
It's analogous to programming a parallel computer using, say, old-fashioned Fortran-77, making sure to employ only those programming patterns that a smart parallelizing compiler can recognize and convert into parallel operations. This has been done; on the other hand, explicitly parallel extensions have also been added to conventional languages (Fortran-90, C*, *Lisp).
Kevin A. Scaldeferri in litteris
> | However, let's think about Lisp instead. In some crude sense, quantum computers are a little like non-deterministic machines. Now, it's not that hard to describe a non-deterministic algorithm in Lisp. Evaluating it might be slow because we have to simulate a non-deterministic machine, but it's possible. |
Indeed, Abelson and Sussman, in their celebrated book *Structure and
Interpretation of Computer Programs* (the "Wizard Book"; see URL:
http://mitpress.mit.edu/sicp/ > for the full text and extra material)
describe a nondeterministic variant of Scheme[*] and construct (in
section 4.3) an interpreter thereof in conventional Scheme. The
essential extension to the language is the primitive (amb
[*] For those who do not know the language, Scheme is a variant of Lisp invented by Steele and Sussman, and whose main difference with more conventional (e.g. Common) Lisp is that functions share the same namespace and first-class citizenship manipulation as other variables.
> | More generally, I didn't think that quantum computers were known to be more powerful than Turing machines / lambda calculus. They may be more efficient at some computations, but not more powerful. Perhaps I'm wrong about that, but if I'm not than you should be able to program a QC in Lisp (or in any other rigorously-defined, Turing-complete language). |
Indeed, the Church-Turing Thesis, in its "physical" form (viz., "any physically realizable means of computation can have no more computational power than the (untyped) Lambda calculus / a Turing machine") supposedly applies also to quantum computers.
(Well, strictly speaking, this may not be true. Even classically, a computer which has access to a "true" random number generator has more computational power than a Turing machine, since the random number stream has unbounded Kolmogoroff complexity. So perhaps the Church-Turing thesis should be stated relative to a random Oracle. But this is mostly beside the point, here.)
In the complexity zoo, the class of problems "feasible" for quantum computers is BQP (Bounded-Error Quantum Polynomial-Time, see URL: http://www.cs.berkeley.edu/~aaronson/zoo.html#bqp >). This is a complexity class, not a computability class: given enough resources, it is thought that classical and quantum computers can compute exactly the same functions - the recursive functions, those that a Turing machine computes.
This does not, however, address the problem of whether we can write an effective and efficient "compiler" from some conventional programming language such as (nondeterministic) Scheme to the hardware / machine code of a quantum computer.
-- David A. Madore (david.madore@ens.fr, http://www.eleves.ens.fr:8080/home/madore/ )
> | It is probably best not to think too much about "languages" like C in this regard, since it doesn't have any formal definition. |
What doesn't have any formal definition ?
-- pete
peterwshor@aol.com (Peter Shor) wrote in message news:<9b2e17b4.0303270821.37e3ab04@posting.google.com>...
> | entropy@farviolet.com (Lawrence Foard) wrote |
> | The proponents of "Digital Philosophy," including Ed Fredkin, believe that quantum computing can't work. And it also seems to follow from some of the things Wolfram says in his book "New Kind of Science" (not surprising, since the "digital philosophers" claim that Wolfram stole the whole idea from them); however, it's not completely clear to me from his book what Wolfram's opinion is. And even if you discount the "digital philosophers" as being a little bit crazy, there are also quite a number of otherwise sensible computer scientists and mathematicians who expect that quantum computing will fail. The only one I'll mention is Leonid Levin; I expect he won't mind being named since his opinions on his web page, and he is also probably the most notable, being the co-discoverer of NP-completeness (along with Stephen Cook; this is one of many discoveries which happened independently on either side of the Iron Curtain). |
Unless one defines quantum computing = Shor factorization, I believe that what these people think is unfeasible is Shor Factorization for >300 digit numbers, not all of quantum computing. They think Shor's proof is mathematically correct but it does not take into account decoherence noise introduced by contact with the environment. Furthermore, they think that the state of the art error correction schemes are not sufficient to overcome this noise. (Maybe if the dream of topological quantum computers becomes a reality, they will change their tune?) Lest I be accused of putting words in other people's mouth, here is Levin's web page on the subject http://www.cs.bu.edu/fac/lnd/misc/qc.html
Correction:
NAND:
(a,b)-> a + b + (not a)*(not b)
or equivalently
(a, b) -> not(a*b)
Hendrik Weimer
> | An example for a language designed for quantum computers is QCL (http://www.tph.tuwien.ac.at/~oemer/qcl.html). |
That link went "the page cannot be displayed" on me.
Best regards, Squark
------------------------------------------------------------------
Write to me using the following e-mail:
Skvark_Nuclearsto@excite.exe
(just spell the particle name correctly and change the
extension in the obvious way)
fiis5d@yahoo.com (Squark) wrote in news:939044f.0303290808.26530e47@posting.google.com:
> | (http://www.tph.tuwien.ac.at/~oemer/qcl.html). Not there/ |
http://tph.tuwien.ac.at/~oemer/qcl.html
-- David Winsemius
> |
Hendrik Weimer |
> > | An example for a language designed for quantum computers is QCL (http://www.tph.tuwien.ac.at/~oemer/qcl.html). |
> |
That link went "the page cannot be displayed" on me. |
Try: http://tph.tuwien.ac.at/~oemer/qcl.html
There is a hugh difference between simulating a quantum computer specific simulating shor's algorithm and programming a quantum computer.
Nick http://users.pandora.be/nicvroom/ See question 23.
Hendrik Weimer
> | An example for a language designed for quantum computers is QCL (http://www.tph.tuwien.ac.at/~oemer/qcl.html). |
http://tph.tuwien.ac.at/~oemer/qcl.html
Unfortunately, this lacks a quantum compiler, (the most important part, in my opinion) By a quantum compiler I mean some software that runs on a classical computer. Given any unitary matrix U and an error tolerance, the ideal quantum compiler would give you the shortest sequence of elementary operations that approximates U to within the specified tolerance. For example, given a discrete Fourier transform matrix, a quantum compiler would output Coppersmith's decomposition.
kevin@inky.its.caltech.edu (Kevin A. Scaldeferri) wrote in message
news:
> |
It is probably best not to think too much about "languages" like C in
this regard, since it doesn't have any formal definition.
However, let's think about Lisp instead. |
I don't know much about Lisp, but okay.
> | In some crude sense, quantum computers are a little like non-deterministic machines. Now, it's not that hard to describe a non-deterministic algorithm in Lisp. |
But you still need an additional component in the language, like a "random" function (which would be "genuine random" in this case, rather than a pseudorandom number generator).
> | Evaluating it might be slow because we have to simulate a non-deterministic machine, but it's possible. |
Now it sounds as if you suggest "going over all possible outcomes" of the "random". This indeed allows to build a slower emulation of the non-deterministic machine, but that's not what was intended. You need to be able to write a program, which would use the "true random" on the low level when compiled. You can't do _that_ in Lisp, can you? You can program a usual, classical, computer to run an emulation of that sort, but that's no use.
Or are you suggesting the compiler should be smart enough to plug in the "true random" itself? That seems to require something close to an Artifical Intelligence. If I had one, I'd let it do the programming itself and be done with it :-)
Best regards,
Squark
------------------------------------------------------------------
Write to me using the following e-mail: Skvark_Nuclearsto@excite.exe (just spell the particle name correctly and change the extension in the obvious way)
> | Ok, but one still needs to get to an assembler/machine code, higher level languages can run on, or be compiled for. |
I too believe quantum computers need something like a high level language and a compiler. My own, personal views about this are explained in http://www.ar-tiste.com/qubiter.html That web page gives some arXiv references
> | Either way, I think the NAND must be made to function if a processor can be developed. |
In quantum computing one uses elementary gates also (eg. CNOTs and
qubit rotations) A CNOT is just a reversible version of a NAND gate:
For a, b \in {0,1}
NAND: (a, b)->(a+b)
CNOT: (a, b)->(a, a+b)
where + is mod 2 addition
In article
> | peterwshor@aol.com (Peter Shor) wrote in message |
>> | entropy@farviolet.com (Lawrence Foard) wrote |
>> | there are also quite a number of otherwise sensible computer scientists and mathematicians who expect that quantum computing will fail. The only one I'll mention is Leonid Levin; I expect he won't mind being named since his opinions on his web page, and he is also probably the most notable, being the co-discoverer of NP-completeness (along with Stephen Cook; this is one of many discoveries which happened independently on either side of the Iron Curtain). |
> |
Unless one defines quantum computing = Shor factorization, I believe that what these people think is unfeasible is Shor Factorization for >300 digit numbers, not all of quantum computing. They think Shor's proof is mathematically correct but it does not take into account decoherence noise introduced by contact with the environment. Furthermore, they think that the state of the art error correction schemes are not sufficient to overcome this noise. |
I don't think I've heard anyone who has this skepticism only in regard to Shor's algorithm. I think that these people think that any and all quantum computations will fail to scale to useful sizes.
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
In article <3E842E30.6192@mindspring.com>,
pete
> | Kevin A. Scaldeferri wrote: |
>> | It is probably best not to think too much about "languages" like C in this regard, since it doesn't have any formal definition. |
> | What doesn't have any formal definition ? |
I knew that was going to cause confusion...
C has a "formal definition" in the sense of their being a standard which defines the language (actually, more than one(*)).
However, it is not based on any mathematical model of computation, and that is the sense that I meant when I said that it does not have a formal definition. This makes it very difficult, if not impossible, to reason rigorously about C programs, and consequently most academics in CS don't! They tend to prefer languages like Lisp (which is really pure mathematics) or the ML family which are rigorously defined.
* ObITJoke - The nice thing about standards is that there's so many to choose from.
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
> | I didn't think that quantum computers were known to be more powerful than Turing machines / lambda calculus. They may be more efficient at some computations, but not more powerful. |
Correct. Quantum computers are known to *not* be more powerful than Turing machines, at least in the sense of what functions they compute.
It is strongly conjectured that there are some computations for which they are much more efficient than deterministic machines. It is considered unlikely that they are always as good as nondeterministic machines (confusion on this point in the popular press notwithstanding).
There are also applications of quantum computation other than computing functions. For example, implementing (or attacking) quantum cryptographic protocols. A quantum computer can do things to Qbits that a classical computer cannot.
> | Perhaps I'm wrong about that, but if I'm not than you should be able to program a QC in Lisp (or in any other rigorously-defined, Turing-complete language). |
Of course you *can* program a QC in any language (rigorously defined or not), because any classical program is also a quantum program. But if you did that, you wouldn't get any of the advantages of quantum computation.
It would be relatively easy to add quantum primitives to any language. That would permit the efficient implementation of any quantum algorithm, but wouldn't necessarily result in a good language for quantum computers.
A *good* quantum programing language would be one that makes quantum algorithms easy(er) to write and to understand, so that a person does not need the equivalent of a PhD in Computer Science *and* Physics to do it.
I don't think we know how to do that now. We don't even know how large or diverse the class of good quantum algorithms is (the known ones are few, and have low diversity), so we don't even know how "general purpose" a good quantum language needs to be.
My guess is that if a quantum computer of any useful size is ever built, this is likely to very quickly become a Big Deal.
Ralph Hartley
tucci@ar-tiste.com (Robert Tucci) wrote in message
news:
[Large wads of quoted text deleted by overworked moderator]
> |
Correction: NAND: (a,b)-> a + b + (not a)*(not b) or equivalently (a, b) -> not(a*b) |
I'm a bit uncertain on your nomenclature on boolean algebra, so I'll do the truth table...
Ok, consider the logic inputs to be A and B and the output to be X, then a boolean matrix, for an AND gate would be,
A B X 0 0 0 1 0 0 0 1 0 1 1 1And NAND should be A B X 0 0 1 1 0 1 0 1 1 1 1 0
You suggested a correction in your post, and that implies I made an error, but how did I make an error? I reiterate, if a A and B are OFF "1" doesn't flow to the output. Regards again and thanks Ken S. Tucker
fiis5d@yahoo.com (Squark) writes:
> |
Hendrik Weimer |
> > | An example for a language designed for quantum computers is QCL (http://www.tph.tuwien.ac.at/~oemer/qcl.html). |
> | That link went "the page cannot be displayed" on me. |
Oops, must be http://tph.tuwien.ac.at/~oemer/qcl.html.
Hendrik Weimer
-- libquantum - Simulation of a Quantum Computer
http://www.enyo.de/libquantum/
In article <939044f.0303280253.1c4feb3d@posting.google.com>,
Squark
> |
kevin@inky.its.caltech.edu (Kevin A. Scaldeferri) wrote in message
news: |
>> |
In some crude sense, quantum computers are a little like non-deterministic machines. Now, it's not that hard to describe a non-deterministic algorithm in Lisp. |
> |
But you still need an additional component in the language, like a "random" function (which would be "genuine random" in this case, rather than a pseudorandom number generator). |
You're confusing randomness with non-determinism. When discussing computability, those are very different things. A non-deterministic machine is not the same as a deterministic machine with randomization.
One obvious difference is that we know how to build a deterministic machine with randomization (more-or-less), but we don't know how to build a non-deterministic machine.
To explain the difference, let me very briefly describe a deterministic finite automata, a non-deterministic finite automata, and a randomized DFA.
A DFA is a machine with a set of states and a set of transistions which tells how to move from state to state for each possible input. There is a single path from each state for each possible input.
A NFA can have multiple paths from a state for a single input symbol. The output of an NFA considers all possibilities that could be taken for the sequence of input symbols provided.
Note that a DFA can simulate an NFA by expanding its state space to be the power set of the state space of the NFA (i.e. the set of all subsets of the NFA state space). This has exponential cost in time and space, though.
A randomized DFA is just like a normal DFA except that when deciding what transistion to take from a state, it considers both the current input symbol and a randomly generated symbol. As a consequence, the output of the randomized DFA cannot be predicted from the input sequence.
Note that it's easy to get confused here, because the output of a non-deterministic machine on a specific input is deterministic. However, the output of a randomized machine is non-deterministic.
>> | Evaluating it might be slow because we have to simulate a non-deterministic machine, but it's possible. |
> |
Now it sounds as if you suggest "going over all possible outcomes" of the "random". This indeed allows to build a slower emulation of the non-deterministic machine, but that's not what was intended. You need to be able to write a program, which would use the "true random" on the low level when compiled. You can't do _that_ in Lisp, can you? You can program a usual, classical, computer to run an emulation of that sort, but that's no use. |
Hopefully from the above comments, you can work out the answers to these questions. I was referring to simulating a non-deterministic machine on a deterministic machine, not simulating a randomized machine, which is impossible.
> | Or are you suggesting the compiler should be smart enough to plug in the "true random" itself? That seems to require something close to an Artifical Intelligence. If I had one, I'd let it do the programming itself and be done with it :-) |
An optimizing compiler for a quantum computer would presumably recognize idioms which can readily take advantage of the special abilities of a quantum computer. It might even perform code rewrites which preserve the semantics of the program but make it more amenable to quantum computation. Presumably, language extensions would allow one to provide hints to the compiler.
All this is pretty analogous to how existing optimizing compilers work. In particular optimizing compilers for parallel computers encounter a lot of the same challenges.
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
> |
You're confusing randomness with non-determinism. When discussing
computability, those are very different things. A non-deterministic
machine is not the same as a deterministic machine with randomization.
One obvious difference is that we know how to build a deterministic machine with randomization (more-or-less), but we don't know how to build a non-deterministic machine. To explain the difference, let me very briefly describe a deterministic finite automata, a non-deterministic finite automata, and a randomized DFA. A DFA is a machine with a set of states and a set of transistions which tells how to move from state to state for each possible input. There is a single path from each state for each possible input. A NFA can have multiple paths from a state for a single input symbol. The output of an NFA considers all possibilities that could be taken for the sequence of input symbols provided. A randomized DFA is just like a normal DFA except that when deciding what transistion to take from a state, it considers both the current input symbol and a randomly generated symbol. As a consequence, the output of the randomized DFA cannot be predicted from the input sequence. |
i'm affraid your definition of "non-deterministic" is somewhat different than just "not deterministic" which is anything that cannot be described by some semi-group law with unity (monoid). what about the deterministic systems with partial information accessible? if we cannot determine the initial conditions exactly, then the evolution will only be predictable to some extent with a probabilitic distribution of possible paths. according to your definition, this is non-deterministic model, but behaves like randomized deterministic one.
is there a way to tell them apart? that is, to decide upon a record of outcomes, to which category the system belongs?
the nicety may lay in the perspective taken - whether we describe the law governing internal states of the original, or the law of a model which reproduce the outcomes.
best regards p. gralewicz
kevin@clyde.its.caltech.edu (Kevin A. Scaldeferri) wrote in message news:
>
You're confusing randomness with non-determinism...
Yes, I see the point.
> | An optimizing compiler for a quantum computer would presumably recognize idioms which can readily take advantage of the special abilities of a quantum computer. It might even perform code rewrites which preserve the semantics of the program but make it more amenable to quantum computation. Presumably, language extensions would allow one to provide hints to the compiler. |
Well, replacing "quantum computer language" by "language extensions" is just playing with the terminology.
> | All this is pretty analogous to how existing optimizing compilers work. In particular optimizing compilers for parallel computers encounter a lot of the same challenges. |
Yes, but
1) You'd hardly expect an optimizing compiler to take the job of "quantizing" algorithms all on itself, the same true for parallelization when it's non-trivial.
2) A priori "quantizations" seems to be even harder than "parallelization" as the later might be done (to some extent) by just considering which operations in the non-parallelized algorithm "don't depend on each other" and separating them into different "threads", while here I don't see even an order 0 approach straight away.
Best regards,
Squark
------------------------------------------------------------------
Write to me using the following e-mail:
Skvark_Nuclearsto@excite.exe
(just spell the particle name correctly and change the
extension in the obvious way)
> | Unfortunately, this lacks a quantum compiler, (the most important part, in my opinion) By a quantum compiler I mean some software that runs on a classical computer. Given any unitary matrix U and an error tolerance, the ideal quantum compiler would give you the shortest sequence of elementary operations that approximates U to within the specified tolerance. |
You don't ask for much do you?
It isn't really reasonable to ask a compiler to produce an *optimal* implementation of a program. You should only demand a "reasonable" implementation.
I am skeptical that a "quantum compiler" in your sense is practical, or even possible (depending on some definitions/assumptions).
By your definition, a *classical* compiler is impossible. The problematical requirement is that it produce the *shortest* sequence of operations.
To do that you would need an algorithm to find the shortest program (or fastest etc.) equivalent to a given program, but that is *known* to be uncomputable.
I'm not sure how these uncomputability results extend to the case of a unitary matrix, which may only correspond to a single *step* of a computation. It may be that you can approximate a given matrix optimally, but that iterating the approximation is not the optimal way to approximate lim_{n->infinity} U^n.
Also, if you mean a *finite* matrix, such a compiler would only cover quantum finite state machines, not all quantum programs. If you mean a potentially infinite matrix (as for a quantum TM), then it may matter how the matrix is described. For instance, if the language for describing matrices includes powers and limits, then a "compiler" (in your sense) is impossible.
Even if possible, a quantum compiler might use *many* more operations finding the optimal sequence of operations than that sequence of operations uses. A compiler that produces code %10 faster isn't much use if it takes the lifetime of the universe to compile any program.
Would not a "quantum compiler" (by your definiton), if given Shor's algorithm as input, have to return the best possible classsical factoring algorithm? (That algorithm is still unknown.)
Ralph Hartley
Ralph Hartley
> | I am skeptical that a "quantum compiler" in your sense is practical, or even possible (depending on some definitions/assumptions). |
I think you are unduly pessimistic. Let SEO = sequence of elementary operations. A quantum compiler would be a practical solution to a practical, well defined problem. In writing a quantum computer program that used 1000 qubits, it would not be necessary to ask the compiler to decompose a 2^1000 dimensional unitary matrix into an "optimal" SEO . That would be tantamount to asking the compiler to write the whole program for you. On the other hand, there might be small subroutines in the program that required you to decompose a 2^5 dimensional unitary matrix into a SEO, and a quantum compiler would do this for you. We already know various algorithms for decomposing a unitary matrix into a SEO in a non-optimal way. Now we just have to find various optimizations that make these algorithms better, and maybe at some point someone will provide a proof that we've improved them "as far as possible".
In article
> | We already know various algorithms for decomposing a unitary matrix into a SEO in a non-optimal way. Now we just have to find various optimizations that make these algorithms better, and maybe at some point someone will provide a proof that we've improved them "as far as possible". |
If the last century of mathematics has taught us anything, it is that it seems much more likely that someone will provide a proof that it is impossible to prove that a quantum algorithm is optimal.
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
"Lawrence Foard"
Around me I see a world with very large but finite computing power, my
intuition tells me that we will fail to extract many orders of magnitude
more computing power from the world than the world already demonstrates.
Of course I could be wrong and the world is really as weird as everyone
says, but until a quantum computer is doing amazing and otherwise
impossible feats I'll remain a skeptic.
>
Depends what you mean by computing power from the world. Classical computers still have (at a guess) at least 6 orders of magnitude improvement ahead of them in the near future. And if we start paralleling them massively in a super WWW you can probably add another 12 orders beyond that.
Certainly within 30 yrs it looks like the dominant computing power on Earth is likely to be machine rather than standard biology as it is now.
Dirk
tucci@ar-tiste.com (Robert Tucci) writes:
> | A quantum compiler would be a practical solution to a practical, well defined problem. In writing a quantum computer program that used 1000 qubits, it would not be necessary to ask the compiler to decompose a 2^1000 dimensional unitary matrix into an "optimal" SEO . That would be tantamount to asking the compiler to write the whole program for you. On the other hand, there might be small subroutines in the program that required you to decompose a 2^5 dimensional unitary matrix into a SEO, and a quantum compiler would do this for you. |
IMO it is not very useful to think in terms of unitary matrices when it comes to systems with many qubits. Sure, there are some cases (e.g. QFT) in which it may be useful, since the classical counterparts of these algorithms can be expressed efficently as a matrix as well. But in other cases such as modular exponentation it is certainly not.
Hendrik Weimer
-- libquantum - Simulation of a Quantum Computer
http://www.enyo.de/libquantum/
> |
In article <939044f.0303280253.1c4feb3d@posting.google.com>,
Squark |
> > |
kevin@inky.its.caltech.edu (Kevin A. Scaldeferri) wrote in message
news: |
> >> |
In some crude sense, quantum computers are a little like non-deterministic machines. Now, it's not that hard to describe a non-deterministic algorithm in Lisp. |
>> | SNIP |
> |
You're confusing randomness with non-determinism. When discussing computability, those are very different things. A non-deterministic machine is not the same as a deterministic machine with randomization. |
I do not understand and or it is not clear to me. IMO if you want to have a worthwhile discussion about determistic and non-deterministic you must first define what those concepts are. I will give you my definition, but anyone is allowed to disagree and come up with a better one.
A digital machine (DM or DA) consists of a set of Input Registers,
Output Registers and logic gates. (digital operators: AND, OR etc)
The Output Registers and Input Registers are connected via logic gates
as such the state of the Output registers is a function of the Input
Registers.
A DM or DA works in cycles. At each cylcle the state of the Output
Registers is calculated as a function of the Input Registers.
A DM is called deterministic when if you repeat the same calculation with the same state of the Input Registers this results in the same state of the Output Registers. A DM is called non-determistic when this is not the case i.e. "each time" you get a different answer.
A deterministic and a non-deterministic DM can both be called Random
For a deterministic DM to be called Random you have to consider
at least more cycles and in one cycle part of the information
in the Output Registers has to be feedback to the Input Registers.
For example the following two instructions do just that:
For both a deterministic DM and a non-deterministic DM each to trully to be called random you have to include certain tests on the data.
> |
One obvious difference is that we know how to build a deterministic machine with randomization (more-or-less), but we don't know how to build a non-deterministic machine. |
To build a non-deterministic machine is very easy:
To have any use you have to consider your non-determistic DM and your deterministic DM completely separated. Which such a combination you can (in principle) do Monte Carlo type simulation and calculate pi. (However each time you get a different answer)
> |
To explain the difference, let me very briefly describe a
deterministic finite automata, a non-deterministic finite automata,
and a randomized DFA.
A DFA is a machine with a set of states and a set of transistions which tells how to move from state to state for each possible input. There is a single path from each state for each possible input. |
What is you definition of single path?
> | A NFA can have multiple paths from a state for a single input symbol. The output of an NFA considers all possibilities that could be taken for the sequence of input symbols provided. |
Difficult definition. Not easy to understand. What means considers Can you give an example ? Above you mention that we don't know how to build them so what is the point.
> | Note that a DFA can simulate an NFA by expanding its state space to be the power set of the state space of the NFA (i.e. the set of all subsets of the NFA state space). This has exponential cost in time and space, though. |
> | A randomized DFA is just like a normal DFA except that when deciding what transistion to take from a state, it considers both the current input symbol and a randomly generated symbol. As a consequence, the output of the randomized DFA cannot be predicted from the input sequence. |
Again what do you mean with: considers. How is that implemented.
> | Note that it's easy to get confused here, because the output of a non-deterministic machine on a specific input is deterministic. |
Yes I'am confused. I would call the output non-deterministic.
> | However, the output of a randomized machine is non-deterministic. |
It can also de deterministic if your randomized machine is deterministic. With a randomized deterministic machine when you calculate pi "each time" you get the same answer.
Nick.
http://users.pandora.be/nicvroom/ Select question 23
http://users.pandora.be/nicvroom/shor.htm
> | Ralph Hartley wrote: |
>> | I am skeptical that a "quantum compiler" in your sense is practical, or even possible (depending on some definitions/assumptions). |
> |
I think you are unduly pessimistic. |
> | A quantum compiler would be a practical solution to a practical, well defined problem. |
A good program that did the job on a "best effort" basis would be a practical solution to a practical, well defined problem, but that's not what you asked for. You said "shortest".
> | there might be small subroutines in the program that required you to decompose a 2^5 dimensional unitary matrix into a SEO, and a quantum compiler would do this for you. We already know various algorithms for decomposing a unitary matrix into a SEO in a non-optimal way. Now we just have to find various optimizations that make these algorithms better, |
All possible.
> | maybe at some point someone will provide a proof that we've improved them "as far as possible". |
Not possible.
Give me the program, and I will construct a problem for which it can be improved more (assuming the program works on a large enough class of problems (i.e. unbounded memory etc.). If not, I will point out a class of problems it doesn't work on).
This is not specific to quantum computation. For any programming language, a compiler produces *a* SEO. "Optimizing" compilers try to produce a *better* SEO. None can always produce the *best*. All can be improved further (in principle, eventually it gets too hard). This is a theorem, so it isn't open to opinion (and is getting off topic for this list).
Ralph Hartley
In article
> | "Kevin A. Scaldeferri" wrote |
>> |
In article <939044f.0303280253.1c4feb3d@posting.google.com>,
Squark |
>> > |
kevin@inky.its.caltech.edu (Kevin A. Scaldeferri) wrote in message
news: |
>> >> | In some crude sense, quantum computers are a little like non-deterministic machines. Now, it's not that hard to describe a non-deterministic algorithm in Lisp. |
>> | You're confusing randomness with non-determinism. When discussing computability, those are very different things. A non-deterministic machine is not the same as a deterministic machine with randomization. |
> | I do not understand and or it is not clear to me. IMO if you want to have a worthwhile discussion about determistic and non-deterministic you must first define what those concepts are. I will give you my definition, but anyone is allowed to disagree and come up with a better one. |
No, no, no...
What I gave was not _my_ definition, nor am I interested in yours. The theory of computation has its definitions and it would be wise to conform to them. The definition of "non-deterministic" in this context does not imply randomness.
(Note that if non-deterministic was the opposite of deterministic, than the question of whether P=NP would be trivially false. It is only because non-deterministic machines are a superset of deterministic machines that the question makes any sense at all.)
> | A DM is called deterministic when if you repeat the same calculation with the same state of the Input Registers this results in the same state of the Output Registers. A DM is called non-determistic when this is not the case i.e. "each time" you get a different answer. |
No, you should break yourself of this terminology if you want to communicate with other people interested in computability. In the standard terminology, both deterministic and non-deterministic machine produce the same output every time for a given input. Only a randomized machine can produce different output on repeated runs.
>> |
To explain the difference, let me very briefly describe a
deterministic finite automata, a non-deterministic finite automata,
and a randomized DFA.
A DFA is a machine with a set of states and a set of transistions which tells how to move from state to state for each possible input. There is a single path from each state for each possible input. |
> | What is you definition of single path? |
I mean that there is a transition function G : S x A -> S, where S is the state space and A is the symbol alphabet for the input.
>> | A NFA can have multiple paths from a state for a single input symbol. The output of an NFA considers all possibilities that could be taken for the sequence of input symbols provided. |
> | Difficult definition. Not easy to understand. What means considers Can you give an example ? |
The transition function of an NFA is G : S x A -> 2^S. An execution of an NFA succeeds if the intersection of the set of success sets with the output of the closure of G applied to the input string is non-empty.
Not sure if that was clearer. Honestly, you'd be best off to find a textbook or to do a web search to see the exact definitions.
> | Above you mention that we don't know how to build them so what is the point. |
To understand the theory of computability.
>> | A randomized DFA is just like a normal DFA except that when deciding what transition to take from a state, it considers both the current input symbol and a randomly generated symbol. As a consequence, the output of the randomized DFA cannot be predicted from the input sequence. |
> | Again what do you mean with: considers. How is that implemented. |
I mean that the transition function is G : S x A x B -> S, where B is an alphabet of symbols which our source of randomness chooses from on each step.
>> | Note that it's easy to get confused here, because the output of a non-deterministic machine on a specific input is deterministic. |
> | Yes I'am confused. I would call the output non-deterministic. |
No, because it is always the same.
>> | However, the output of a randomized machine is non-deterministic. |
> | It can also be deterministic if your randomized machine is deterministic. |
One could consider degenerate cases where the randomness does not affect the output, but that's not very interesting, nor any more powerful than a normal deterministic machine.
> | With a randomized deterministic machine when you calculate pi "each time" you get the same answer. |
No, generically a randomized algorithm would give different results each time, which are hopefully close enough or right often enough to be useful.
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
> | Kevin A. Scaldeferri wrote |
>> | You're confusing randomness with non-determinism. When discussing computability, those are very different things. A non-deterministic machine is not the same as a deterministic machine with randomization. |
>> |
A DFA is a machine with a set of states and a set of transistions
which tells how to move from state to state for each possible input.
There is a single path from each state for each possible input.
A NFA can have multiple paths from a state for a single input symbol. The output of an NFA considers all possibilities that could be taken for the sequence of input symbols provided. |
> | i'm affraid your definition of "non-deterministic" is somewhat different than just "not deterministic" which is anything that cannot be described by some semi-group law with unity (monoid). |
Well, it's not _my_ definition, but you're correct that non-deterministic machines are not the complement of deterministic machines. That's what I was trying to explain. When we talk of "non-deterministic" in the context of computability, there is a very precise and limited sort of non-determinism that is allowed.
> | what about the deterministic systems with partial information accessible? if we cannot determine the initial conditions exactly, then the evolution will only be predictable to some extent with a probabilitic distribution of possible paths. according to your definition, this is non-deterministic model, but behaves like randomized deterministic one. |
No, this is a completely different sort of problem. In the sorts of machines I'm talking about, the initial state is always uniquely defined, and the input is fully defined in advance of the execution of the machine.
To a limited degree, one could consider a NFA where the initial state is not fully determined, but is instead a set of states. If the initial set is fixed, then this is really no different that a normal NFA. If the initial state is variable, then you are really describing a family of machines, not a single machine.
> | is there a way to tell them apart? that is, to decide upon a record of outcomes, to which category the system belongs? |
Well, as I said in my previous message, the output of both DFAs and NFAs are consistent for a fixed input. So, if you feed the same input into a machine multiple times (resetting the machine each time) and get different outputs, then you know that you are not dealing with one of these machines.
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
> | You're confusing randomness with non-determinism. When discussing computability, those are very different things. A non-deterministic machine is not the same as a deterministic machine with randomization. |
Actually, they're not very different. Every stochastic automaton has a non-deterministic automaton as its base:
a -- x -> b iff the probability of a transition from a to b on x > 0. a is an initial state iff the probability of a being an initial state > 0. b is a final state iff the probability of b being a final state > 0.
Some definitions of stochastic automata don't have any concept of final state. This can be treated as the limiting case of the more general definition (in which final states are allowed for) where all the final state probabilities go to 0.
So, there is a many-to-one correspondence between stochastic automata and non-deterministic automata.
In the setting of orthodox quantum physics (meaning, specifically: Schroedinger's Equation + Lueder's Rule), it's actually specifically a stochastic automaton that you have, not merely a non-deterministic; with the state transition probabilities given in the Lueder's Rule.
In article
> | Kevin A. Scaldeferri wrote |
>> |
You're confusing randomness with non-determinism. When discussing computability, those are very different things. A non-deterministic machine is not the same as a deterministic machine with randomization. |
> |
Actually, they're not very different. Every stochastic automaton has a non-deterministic automaton as its base: a -- x -> b iff the probability of a transition from a to b on x > 0. a is an initial state iff the probability of a being an initial state > 0. b is a final state iff the probability of b being a final state > 0. |
I'm pretty sure we're on the same side of this discussion, so let me try to clarify lest others become confused.
The definitions of a deterministic automaton, a non-deterministic automaton, and a stochastic automaton are quite similar. There is just a subtle difference in the transistion function(*) for each. Also, there are multiple equivalent definitions of each of the three.
_However_, stochastic automata are significantly different in what they do from deterministic or non-deterministic. Importantly, DFAs and NFAs are equivalent models of computation, while randomized automata are inequivalent to either.
(*) depending on the type of automata and the specific form of the definition, the "transition function" might not actually be a function. I'm not going to elaborate on that, though.
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
> | I too believe quantum computers need something like a high level language and a compiler. My own, personal views about this are explained in http://www.ar-tiste.com/qubiter.html |
At that URL you write: "Qubiter is a tool that translates this high level language to qubit level instructions which can then be fed to a QC."
Please can you give some imformation how you envision this last step ?
My first guess is that this is not simple, but ofcourse I can be wrong.
Can you use this methodology on any QC or are there special restrictions?
Suppose your QC consists of a set of Qbit registers. Does this last step means that you will initialize those Qbit registers with the correct values?
Suppose a problem requires a sequence of different quantum logical operations. Does Qubiter takes care that those operations are performed in the correct order on your QC?
When you use Qubiter does that mean that you can easily use the same QC to solve different problems?
Nick http://users.pandora.be/nicvroom/shor.htm
Nicolaas Vroom
> | Please can you give some information how you envision this last step ? |
To go from a quantum Bayesian Net to a SEO, one would follow a process like the one described in http://www.arxiv.org/abs/quant-ph/9805016 The process described in that paper is not yet implemented in Qubiter. At this point, all Qubiter does is to decompose a unitary matrix into a SEO, and this it can only do in an inefficient way.
> | Can you use this methodology on any QC or are there special restrictions? |
You can use quantum Bayesian nets and quantum compilers to program any QC consisting of a finite number of qubits that are fairly free from interaction with the external environment so that their state can be modelled as a pure state instead of a mixed state. (Shor and Grover algorithms assume a pure state) Generalization of this programming method to systems in mixed states is probably possible but the theory for this hasn't been completely developed yet.
> | Suppose your QC consists of a set of Qbit registers. Does this last step means that you will initialize those Qbit registers with the correct values? |
The output of a full, complete quantum compiler would be the SEO that you should apply to the QC PLUS also a description of the initial states that you should place the qubits in. Quantum Bayesian Nets contain (in their root nodes) information about initial conditions. This information must be translated into information about the initial conditions of the qubits.
> | Suppose a problem requires a sequence of different quantum logical operations. Does Qubiter takes care that those operations are performed in the correct order on your QC? |
A bit unclear to me what you mean.
> | When you use Qubiter does that mean that you can easily use the same QC to solve different problems? |
A bit unclear to me what you mean. I think a quantum compiler would allow us to program a QC to solve many problems that heretofore nobody knew how to program on a QC.
> | Nick http://users.pandora.be/nicvroom/shor.htm |
> |
Nicolaas Vroom |
> > | Please can you give some information how you envision this last step ? |
SNIP
> | At this point, all Qubiter does is to decompose a unitary matrix into a SEO, and this it can only do in an inefficient way. |
I understand
My question again to you is: "Qubiter is a tool that translates this high level language to qubit level instructions which can then be fed to a QC." Do you expect that this last step "fed to a QC" will ever be possible.
A classical computer consists of a CPU memory with data (registers) and memory (registers/bits) with instructions What a compiler does it initializes those instruction registers in a human friendly way.
A QC (My understanding) does not consists of instructions. It consists of a CPU (sort of) which contains a "matrix" Elementary Operations and data registers (Qubits)
In Nature vol 422 27 march 2003 at page 408 Rainer Blatt e.a. writes: " A QC can be BUILT using single qubit operations ('rotations') and two-qubit CNOT gates because any computation can be decomposed into a sequence of these basic gate operations." See articles 8 and 9 for detail.
I have written built in capital letters because that is how I understand how you have to use a QC in the future.
I expect that there is no direct programming involved.
You can use programming to decompose a computation, the output are like diagrams which can serve as blueprints to built a QC.
For examples of those diagrams see the pages 22-37 of: http://www.ccmr.cornell.edu/~mermin/qcomp/chap2.pdf
Nick http://users.pandora.be/nicvroom/shor.htm
In article <3EAA7B80.5DFF701E@pandora.be>,
Nicolaas Vroom
> |
My question again to you is:
"Qubiter is a tool that translates this high level language
to qubit level instructions which can then be fed to a QC."
Do you expect that this last step "fed to a QC"
will ever be possible.
A classical computer consists of a CPU memory with data (registers) and memory (registers/bits) with instructions |
I think that you are missing a crucial element, which is that "instructions" and "data" are not two seperate entities. This is of critical importance both theoretically, where it is central to concepts like universal machines and undecidibility, and practically, where it form the basis of powerful languages like Lisp and also enables a broad class of security breaches.
...
> |
I have written built in capital letters because that is
how I understand how you have to use a QC in the future.
I expect that there is no direct programming involved. You can use programming to decompose a computation, the output are like diagrams which can serve as blueprints to built a QC. |
No, it is possible (theoretically, at least) to build a universal quantum computer. One would be able to program such a beast in an analogous method to a universal classical computer.
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
> | What a compiler does it initializes those instruction registers in a human friendly way. |
A compiler translates "high" level code to "low" level code. It generates a sequence of elementary operations, taken from a small basic set, for the hardware to follow. The output of what I call a quantum compiler is a sequence of CNOTs and qubit rotation instructions. QCs as currently envisioned will be able to perform these operations.
> | You can use programming to decompose a computation, the output are like diagrams which can serve as blueprints to built a QC. |
> | Nicolaas Vroom wrote: |
> > | What a compiler does it initializes those instruction registers in a human friendly way. |
> |
A compiler translates "high" level code to "low" level code. It generates a sequence of elementary operations, taken from a small basic set, for the hardware to follow. |
First I explain in a simple way what instructions and what a compiler does. Consider the following program in pseudo code:
ML1 Load Reg1 with Memory Location 1000 Reg1 = "A" ML2 Load Reg2 with Memory Location 1001 Reg2 = "B" ML3 Load Reg3 with Memory Location 1002 Reg3 = "C" ML4 ADD Reg1 with Reg2 Result in Reg4 Reg4 = A+B ML5 ADD Reg4 with Reg3 Result in Reg4 Reg4 = A+B+C ML6 Store Reg4 in Memory Location 1003ML stands for Memory Location. The 6 instructions are stored in Memory Locations 1-6 The program contains three instuction types: 1 Load, 2 Add and 3 Store
Each instruction internally is stored as a string of bits. In Decimal Notation the program looks as something like:
ML1 001 001 001000 ML2 001 002 001001 ML3 001 003 001002 ML4 002 001 002 004 ML5 002 004 003 004 ML6 003 004 001003The program can also described as in one line as follows:
> | The output of what I call a quantum compiler is a sequence of CNOTs and qubit rotation instructions. |
Let me describe how I see such a program:
ML1 CNOT QB1 QB2 QB3 ML2 CNOT QB4 QB5 QB6 ML3 Rot QB3 180 ML4 Rot QB6 212 ML5 CNOT QB3 QB6 QB7Ofcourse a Quantum Compiler can generate those instructions.
> | QCs as currently envisioned will be able to perform these operations. |
I doubt that.
In Decimal Notation the program looks like ML1 0 1 2 3 ML2 0 4 5 6 ML3 1 3 180 ML4 1 6 212 ML5 0 3 6 7 The first column is instruction type: 0=CNOT 1=Rotation
Is this what you have in mind ? Where are those instructions stored ? in Qubits Registers ? Do you agree that you need some sort of CPU to execute each instruction ? Does a QC has something what you call a Program Counter (PrC)? I doubt that
IMO if your QC wants to make use of concepts like: Superposition, Entanglement and or Parallel Processing than you cannot make use of instructions which are executed sequential under control of a PrC
> > | You can use programming to decompose a computation, the output are like diagrams which can serve as blueprints to built a QC. |
> | These diagrams should not be understood as classical hardware circuit diagrams. They are more akin to classical flow charts. |
Nick http://users.pandora.be/nicvroom/
Some poor soul not cited by Robert Tucci wrote:
> |
Is this what you have in mind ?
Where are those instructions stored ?
in Qubits Registers ?
Do you agree that you need some sort of CPU to execute each
instruction ? Does a QC has something what you call a Program Counter (PrC)? I doubt that IMO if your QC wants to make use of concepts like: Superposition, Entanglement and or Parallel Processing than you cannot make use of instructions which are executed sequential under control of a PrC |
Contrary to the von Neumann paradign, a QC would not store data and instructions in the same type of registers. A quantum computer CPU, as I understand it, would NOT store the program counter and instructions in quantum registers, but rather in classical registers.
The quantum registers (qubit arrays) would be loaded only with the initial data. These would be operated upon repeatedly until their quantum state, when measured, answered our question, within some degree of uncertainty.
> | The flowcharts only include CNOT's and Rotations. They don't include concepts like CPU, instructions and a PrC. At least that is my current understanding. Correct me if I'am wrong |
yep. The qubit circuit diagrams do not tell you where instructions and program counters are stored, or how they evolve.
In article <3EB12AFE.DE009A42@pandora.be>,
Nicolaas Vroom
> |
First I explain in a simple way what instructions
and what a compiler does.
Consider the following program in pseudo code:
ML1 Load Reg1 with Memory Location 1000 Reg1 = "A" ML2 Load Reg2 with Memory Location 1001 Reg2 = "B" ML3 Load Reg3 with Memory Location 1002 Reg3 = "C" ML4 ADD Reg1 with Reg2 Result in Reg4 Reg4 = A+B ML5 ADD Reg4 with Reg3 Result in Reg4 Reg4 = A+B+C ML6 Store Reg4 in Memory Location 1003 ML stands for Memory Location. The 6 instructions are stored in Memory Locations 1-6 The program contains three instuction types: 1 Load, 2 Add and 3 Store |
> | Is this what you have in mind ? Where are those instructions stored ? in Qubits Registers ? Do you agree that you need some sort of CPU to execute each instruction ? Does a QC has something what you call a Program Counter (PrC)? I doubt that |
I think you are fixating on a particular model of computation. However, it may or may not be useful to model quantum computation as a simple variation of this architecture.
As a somewhat wacky example for you to consider, a particular quantum compiler might produce "machine code" which consists of a sequence of bases (amino acids) and a sequence of NMR pulses to be applied to the protein.
Even in the classical realm, the van Neumann architecture is not mandated. People have built machines which implement the lambda calculus (Lisp) in hardware.
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
Robert Tucci wrote:
> |
Contrary to the von Neumann paradign, a QC would not store data and instructions in the same type of registers. A quantum computer CPU, as I understand it, would NOT store the program counter and instructions in quantum registers, but rather in classical registers. |
It seems to me what you have in mind is like an hybrid computer system i.e. a computer system which contains a classical part (PC like) and the quantum mechanical part. The interface between the two allows for communication between the classical output reg's and quantum input reg's and between quantum output reg's and the classical input reg's
Such an hybrid computer system is the ideal platform to solve shor's algorithm which is partly implemented on a QC and partly on a PC.
> | The quantum registers (qubit arrays) would be loaded only with the initial data. These would be operated upon repeatedly until their quantum state, when measured, answered our question, within some degree of uncertainty. |
That is in agreement with my description of a hybrid computer system above. Your description is correct for the QC part. The PC part or classical part ofcourse can be programmed.
But that is not the issue.
The QC part consists of input reg's (qubit in array)
and output reg's (qubit out array)
The connection between the two is by means of a matrix
of quantum logical gates.
Each different problem requires its own matrix or
matrix of quantum logical gates.
The question is: how do you take care that problem 1 will
execute matrix 1 and problem 2 matrix 2.
IMO you have to (re)built that matrix for each problem.
Programming is no issue.
It is a mechanical (engineering?) hardware oriented problem.
Nick http://users.pandora.be/nicvroom/
In article
> |
Each different problem requires its own matrix or
matrix of quantum logical gates.
The question is: how do you take care that problem 1 will
execute matrix 1 and problem 2 matrix 2. IMO you have to (re)built that matrix for each problem. Programming is no issue. It is a mechanical (engineering?) hardware oriented problem. |
No, this is not true. It is known, in theory, how to construct a universal quantum turing machine. In other words, you can build a general-purpose quantum computer. You do not have to have a custom machine for each problem you want to solve.
There are several caveats and unknowns when it comes to building a QC in practice, but what you keep saying (that you can't build a general purpose QC) is false.
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
> |
In article <3EB12AFE.DE009A42@pandora.be>,
Nicolaas Vroom |
> > |
Is this what you have in mind ?
Where are those instructions stored ?
in Qubits Registers ? |
> |
I think you are fixating on a particular model of computation. |
You should start with something in as much detail as possible and see what the consequences are.
> | As a somewhat wacky example for you to consider, a particular quantum compiler might produce "machine code" which consists of a sequence of bases (amino acids) and a sequence of NMR pulses to be applied to the protein. |
Please let us start with the hardware platform (sort of) as described in Nature Vol 421 20 Feb 2003 page 823-825.
> | Even in the classical realm, the van Neumann architecture is not mandated. People have built machines which implement the lambda calculus (Lisp) in hardware. |
Please let us first discuss "machine code" and what it means. IF machine code PrC and a CPU can be implemented on a QC than the next step to use a higher level is relative easy. However I have major doubts about the feasibility of the first part of that sentence making any discussion about the second part inappropiate.
Nick http://users.pandora.be/nicvroom/ can not be solved
In article
> |
"Kevin A. Scaldeferri" wrote: |
>> |
I think you are fixating on a particular model of computation. |
> |
You should start with something in as much detail as possible and see what the consequences are. |
I think this is liable to cause you trouble. Classical and quantum computation are substantially different. You seem to want to start from a very detailed, specific architecture for classical computing and jump sideways to quantum computing. However, this architecture may be completely inappropriate for quantum computing.
> |
>> |
As a somewhat wacky example for you to consider, a particular quantum compiler might produce "machine code" which consists of a sequence of bases (amino acids) and a sequence of NMR pulses to be applied to the protein. |
> |
Please let us start with the hardware platform (sort of) as described in Nature Vol 421 20 Feb 2003 page 823-825. |
I don't see why we should choose that platform over what I suggested. Both are proposed as ways to do quantum computation. No one knows whether either will scale to useful sizes.
People have actually successfully factored small numbers with Shor's algorithm using an NMR quantum computer. I don't believe any other approaches have actually done this.
>> | Even in the classical realm, the van Neumann architecture is not mandated. People have built machines which implement the lambda calculus (Lisp) in hardware. |
> |
Please let us first discuss "machine code" and what it means. |
Machine code is whatever the machine executes. Different architectures can have machine codes that look completely different. That was my point. You can build a machine where the machine code is Lisp! It doesn't have to look at all like machine code for a van Neumann machine.
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
> |
In article |
> > |
"Kevin A. Scaldeferri" wrote: |
> >> |
I think you are fixating on a particular model of computation. |
> > |
You should start with something in as much detail as possible and see what the consequences are. |
> |
I think this is liable to cause you trouble. Classical and quantum computation are substantially different. |
That is correct. Programming belongs to the realm of classical computation and that is why if someone believes that programming is also relevant for quantum computations he or she has to convince in as much detail as possible why and how it can be used. (and what the benefits are)
SNIP
> | People have actually successfully factored small numbers with Shor's algorithm using an NMR quantum computer. I don't believe any other approaches have actually done this. |
That is correct. The following article in Nature discusses this subject. http://www.nature.com/nature/links/011220/011220-2.html Figure 1 shows a "Quantum circuit for Shor's algorithm" My interpretation of that figure is if you want to factorize larger numbers you have to increase the size of the circuit and you have to use more Qubits. The complexity more or less stays the same. My interpretation of the article is also that no programming is involved and programming is no issue.
> > | Please let us first discuss "machine code" and what it means. |
> |
Machine code is whatever the machine executes. |
A classical machine
> | Different architectures can have machine codes that look completely different. That was my point. You can build a machine where the machine code is Lisp! |
I fully agree for a classical machine. However the issue is quantum computers.
For a nice url about "NMR Quantum Information Processing" see: http://www.c3.lanl.gov/~knill/qip/nmrprhtml/nmrprhtml.html They do not mention programming.
The following url: "Three Lectures on Quantum Computing" http://beige.ucs.indiana.edu/M743-talk-2/M743-talk-2.html when you select "Introduction" there is a discussion in which the words: "High level language and LISP" are mentioned. However I do not think that it is any issue if you want to understand Quantum Computing and or if you want to built a Quantum Computer.
Nick http://users.pandora.be/nicvroom/shor.htm
In article <3ECE36A7.6FCF3D79@pandora.be>,
Nicolaas Vroom
> | Programming belongs to the realm of classical computation and that is why if someone believes that programming is also relevant for quantum computations he or she has to convince in as much detail as possible why and how it can be used. (and what the benefits are) |
This is getting rather tiresome, and this is going to be the last post I make on this thread.
Quantum computers can be "programmed" in principle. That is to say, it is known that you can construct a universal quantum computer. (For anyone not familiar with the lingo, crudely speaking, a universal computer is one that accepts a description of another computer (i.e. a program) and then simulates the behavior of that machine on the remainder of the input.) Anyone who is interested can do a web or literature search to find the details.
In practice, there may be many obstacles to this.
First, it's not clear that even special purpose quantum computers can scale to useful size.
Second, a universal machine is inevitable slower at any given task that a special purpose machine for that task. It may be that the loss of efficiency is such that in practice only special purpose quantum computers will be constructed and used.
Third, writing compilers for general high-level languages which target universal quantum computers in a way that actually takes advantage of the particular efficiencies of quantum machines may be too difficult a task.
Finally, there appears to be only a limited class of problems where quantum computers are algorithmically faster than classical computers. For the majority of computations, they do not give any algorithmic speedup and are expected to be significantly slower than classical computers. Therefore, many people suspect that only hybrid machines will be build, with a quantum computer as a subsystem of an otherwise classical computer. (This is, in spirit, somewhat akin to special purpose FPU, vector, or graphic chips in modern chip/board architectures.)
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
kevin@clyde.its.caltech.edu (Kevin A. Scaldeferri) writes:
> | People have actually successfully factored small numbers with Shor's algorithm using an NMR quantum computer. |
Am I the only one who thinks that this is a bit exaggerated? Implementing about a dozen quantum gates for a seven qubit system is truly quite impressive, but real quantum factoring requires more than that, even for small numbers such as 15.
Hendrik Weimer
-- libquantum - Simulation of a Quantum Computer
http://www.enyo.de/libquantum/
"Nicolaas Vroom"
> |
That is correct.
The following article in Nature discusses this subject.
http://www.nature.com/nature/links/011220/011220-2.html
Figure 1 shows a "Quantum circuit for Shor's algorithm"
My interpretation of that figure is if you want to factorize larger
numbers you have to increase the size of the circuit and you have
to use more Qubits. |
My interpretation would be exactly the opposite. Namely, that the programming is more of a Hardware Description Language. This in itself is not necessarily a big step beyond standard software programming languages.
Dirk
"Hendrik Weimer"
> |
kevin@clyde.its.caltech.edu (Kevin A. Scaldeferri) writes: |
> > |
People have actually successfully factored small numbers with Shor's algorithm using an NMR quantum computer. |
> |
Am I the only one who thinks that this is a bit exaggerated? Implementing about a dozen quantum gates for a seven qubit system is truly quite impressive, but real quantum factoring requires more than that, even for small numbers such as 15. |
Would 8 qubits be better, and less exaggerated? 10, 12... how many, in fact, before such a machine would be treated 'seriously'? It is proof of principle - no more. By the time we get to 100 qubit registers people will be claiming those 7 qubits were of major historical significance (assuming we get there). A matter of perspective, much like Babbage's machine that I could quite equally claim both didn't work and, had it worked, would be no match for a P4 running at 3GHz.
Anyway, the focus now seems to have shifted away from bulk NMR towards more normal semiconductor techniques using embedded atoms. Last I heard was that two atoms in a matrix had been entangled, which on the face of it is even less impressive.
However, it might just turn out to be a problem that can be 'cracked' in one breakthrough if we are very lucky. That entangling N (with N being a useful number) in such a system is a linear scaling in difficulty unlike the NMR method.
Dirk
"Dirk Bruere at Neopax"
> |
"Hendrik Weimer" |
> > |
Implementing about a dozen quantum gates for a seven qubit system is truly quite impressive, but real quantum factoring requires more than that, even for small numbers such as 15. |
> |
Would 8 qubits be better, and less exaggerated? 10, 12... how many, in fact, before such a machine would be treated 'seriously'? |
It is not a question of seriousness. But people tend to say that today's quantum computers are able to factorize small numbers, using a method that beats classical algorithms. And this is just not true.
> | It is proof of principle - no more. |
Exactly. But the principle is controlling several qubits and applying gates on them. And this has been done before, although with less qubits and gates.
> | Anyway, the focus now seems to have shifted away from bulk NMR towards more normal semiconductor techniques using embedded atoms. Last I heard was that two atoms in a matrix had been entangled, which on the face of it is even less impressive. |
The main problem is that we cannot easily say which technology is the best for building a scalable quantum computers. NMR devices do not seem to be very scalable, but it may be enough to actually do something useful with them.
As you said, other technologies such as ion traps seem to be much more promising. So I think that improvements in these areas are far more interesting even if they have already been realized in NMR devices several years ago.
Hendrik Weimer
-- libquantum - Simulation of a Quantum Computer
http://www.enyo.de/libquantum/
In article <86y90vtk32.fsf@gienah.enyo.de>,
Hendrik Weimer
> |
kevin@clyde.its.caltech.edu (Kevin A. Scaldeferri) writes: |
>> |
People have actually successfully factored small numbers with Shor's algorithm using an NMR quantum computer. |
> |
Am I the only one who thinks that this is a bit exaggerated? Implementing about a dozen quantum gates for a seven qubit system is truly quite impressive, but real quantum factoring requires more than that, even for small numbers such as 15. |
Maybe you can elaborate? This article,
http://www.research.ibm.com/resources/news/20011219_quantum.shtml
(which is little more than a press release, I grant) states:
I.e., they designed and fabricated an appropriate molecule, then applied a specified series of NMR pulses to perform the factorization, then read out the results.
So, what do you consider the shortcoming here?
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
In article <86fzmwyjzu.fsf@gienah.enyo.de>,
Hendrik Weimer
> |
"Dirk Bruere at Neopax" |
>> |
"Hendrik Weimer" |
>> > |
Implementing about a dozen quantum gates for a seven qubit system is truly quite impressive, but real quantum factoring requires more than that, even for small numbers such as 15. |
>> |
Would 8 qubits be better, and less exaggerated? 10, 12... how many, in fact, before such a machine would be treated 'seriously'? |
> |
It is not a question of seriousness. But people tend to say that today's quantum computers are able to factorize small numbers, using a method that beats classical algorithms. And this is just not true. |
Other than qualifications which should be added to the final clause (i.e. that this refers to the asymptotic complexity, not this particular case) I don't understand what isn't true.
Please clarify _exactly_ what you feel makes this example not qualify as an implementation of Shor's algorithm.
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
"Kevin A. Scaldeferri" wrote:
SNIP
> | Quantum computers can be "programmed" in principle. |
Can you give me a clue how that is done ? Does such a quantum computer exploit the principle of superposition ?
> | That is to say, it is known that you can construct a universal quantum computer. (For anyone not familiar with the lingo, crudely speaking, a universal computer is one that accepts a description of another computer (i.e. a program) and then simulates the behavior of that machine on the remainder of the input.) Anyone who is interested can do a web or literature search to find the details. |
Why do you write simulate the behavior etc ? This is not clear. Please give more advice with the web search
> | In practice, there may be many obstacles to this. |
I expect the same....
> | First, it's not clear that even special purpose quantum computers can scale to useful size. |
What is your definition of a special purpose QC? Does it include programming ? (I expect not) Does it exploit the principle of superposition ? (I expect Yes)
> | Second, a universal machine is inevitable slower at any given task that a special purpose machine for that task. It may be that the loss of efficiency is such that in practice only special purpose quantum computers will be constructed and used. |
I agree (in principle) with you but still it is important to understand what the major difference(s) is between a special purpose QC and a general purpose QC.
> | Third, writing compilers for general high-level languages which target universal quantum computers in a way that actually takes advantage of the particular efficiencies of quantum machines may be too difficult a task. |
I agree with you.
> | Finally, there appears to be only a limited class of problems where quantum computers are algorithmically faster than classical computers. For the majority of computations, they do not give any algorithmic speedup and are expected to be significantly slower than classical computers. |
This is an interesting remark. The true issue is for what type of calculations a (special purpose) QC is faster.
> | Therefore, many people suspect that only hybrid machines will be build, with a quantum computer as a subsystem of an otherwise classical computer. |
I expect the same. But that does not answer the question: Does a quantum computer supports any form of programming? Does a quantum computer incorporates instructions and at the same time exploit the principle of superposition ?
Nick http://users.pandora.be/nicvroom/
Dirk Bruere at Neopax wrote:
> |
"Nicolaas Vroom" |
> > |
That is correct. The following article in Nature discusses this subject. http://www.nature.com/nature/links/011220/011220-2.html Figure 1 shows a "Quantum circuit for Shor's algorithm" My interpretation of the article is also that no programming is involved and programming is no issue. |
> |
My interpretation would be exactly the opposite. |
The whole article is about quantum hardware (i.e. Qubits and quantum logic) related issues.
> | Namely, that the programming is more of a Hardware Description Language. This in itself is not necessarily a big step beyond standard software programming languages. |
IMO the standard interpretation of programming (software) is not about hardware. Of course you can write software which specifies hardware. For example CAD, CAM software does just that.
The topic of this tread if Quantum Computers require (incorporate) some form of programming. IMO that also implies that they use some form of instructions. The benefit of such an architecture makes them general purpose. However, and that is important, they still should exploit the concept of superposition.
IMO all of that is very difficult.
Nick http://users.pandora.be/nicvroom/
"Nicolaas Vroom"
Namely, that the programming is more of a Hardware Description Language.
This in itself is not necessarily a big step beyond standard software
programming languages.
IMO the standard interpretation of programming (software) is not about
hardware.
Of course you can write software which specifies hardware.
For example CAD, CAM software does just that.
>
The whole article is about quantum hardware (i.e. Qubits and quantum
logic)
related issues.
> >
>
> | The topic of this tread if Quantum Computers require (incorporate) some form of programming. IMO that also implies that they use some form of instructions. The benefit of such an architecture makes them general purpose. |
If every problem needs a specific hardware solution then all we require is s/w configurable h/w. Something along the lines of a programmable quantum gate array. That is why if we cannot create the analog of a von Neumann machine we could still potentially create a programming language for QCs.
> |
However, and that is important, they still should exploit
the concept of superposition.
IMO all of that is very difficult. |
The h/w is undoubtedly the hardest part of the whole venture.
Dirk
kevin@its.caltech.edu (Kevin A. Scaldeferri) writes:
> |
I.e., they designed and fabricated an appropriate molecule, then
applied a specified series of NMR pulses to perform the factorization,
then read out the results.
So, what do you consider the shortcoming here? |
Shor's algorithm consists of three parts: a quantum version of modular exponentiation, the Quantum Fourier Transform and some classical postprocessing. While the last two were realized as Shor proposed, the modular exponentiation was not calculated with a quantum algorithm.
Instead, they used some knowledge about the number to be factorized which cannot be extracted in polynomial time. For example, they write about the evaluation of the function a^x mod 15, "If we happen to pick a = 2, 7, 8 or 13, we find that a^4 mod 15 = 1". Once I know that, I do not have to use Shor's algorithm anymore, since I already know the order of the function.
While this may seem as nit-picking to you (which is certainly true to some extent), the simplifications have an enormous impact. Without any prior knowledge about the number 15, a quantum computer would require at least about 4,000 gates to perform the factorization using an implementation of Shor's algorithm.
Hendrik Weimer
-- libquantum - Simulation of a Quantum Computer
http://www.enyo.de/libquantum/
Nicolaas Vroom wrote:
> | the question: Does a quantum computer supports any form of programming? Does a quantum computer incorporates instructions and at the same time exploit the principle of superposition ? |
It depends!
A "quantum" computer is not the same as a "Pentium" computer! "Quantum" does not refer to any particular architecture, but to any computer that exploits superposition.
Given that we can build quantum computers at all, we can build them that support any and all forms of programming, or we can build them with one algorithm wired into the hardware. We can build them that "incorporates instructions", or not. The instruction sequence can be classical, or superpositions of instructions can be used.
Those are architectural design decisions. Given quantum circuit elements, we know how implement *all* the possibilities above. That's what people mean when they say a set of elements is "complete". It remains to be seen what is the *best* architecture.
If classical instructions are much faster that quantum ones, and/or the list of useful quantum algorithms stays as short as it is now, a specialized "quantum coprocessor" will be the way to go.
If quantum circuits end up being nearly as fast as classical ones, and there turn out to be lots of diverse quantum algorithms, then a general purpose, fully programmable quantum computer will be preferred.
It may be that both (or many) kinds of "quantum computer" will be used.
But since the big problem *now* is how to build quantum circuits to begin with, and finding what algorithms they are good for, you must excuse people for not prematurely committing to an architecture.
It is too soon to answer your questions!
Ralph Hartley
In article <86fzmsbh19.fsf@gienah.enyo.de>,
Hendrik Weimer
kevin@its.caltech.edu (Kevin A. Scaldeferri) writes:
So, what do you consider the shortcoming here?
Shor's algorithm consists of three parts: a quantum version of modular
exponentiation, the Quantum Fourier Transform and some classical
postprocessing. While the last two were realized as Shor proposed, the
modular exponentiation was not calculated with a quantum algorithm.
Instead, they used some knowledge about the number to be factorized
which cannot be extracted in polynomial time. For example, they write
about the evaluation of the function a^x mod 15, "If we happen to pick
a = 2, 7, 8 or 13, we find that a^4 mod 15 = 1". Once I know that, I
do not have to use Shor's algorithm anymore, since I already know the
order of the function.
While this may seem as nit-picking to you
>
>>
>
Actually, I don't think it's nitpicking at all. I think it's a totally valid criticism. I wasn't aware that they had cut that corner based on the press-release type article I was looking at. That didn't have a reference to the actually paper, or I would have looked there for more details. Do you have the reference handy?
Anyway, I think we do agree that the NMR folks have gotten further along than anyone else at this point, although it's not at all clear that they have the potential to scale as well as other approaches, right?
-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.
> |
I've seen quantum computers described by networks of quantum gates in a manner analogous to how classical computers are made up of boolean logic gates. However most people who work with classical computers are not concerned with their hardware but rather with the software that runs on it. I was wondering what computer language one would use to program quantum computers. |
Based on my understanding of Quantum Computers QC you will "never" be
able to program a quantum computer QC using a software program
written in a computer language.
In order to use a QC in order to solve EACH particular problem you
have to build your QC (the hardware) with the aid of building blocks
(QuBits, and logic gates) completely.
A QC is very much like an Analog Computer AC.
With an Analog Computer you run in the same problem:
1. You have to build (hardware configure using wires) you AC each time.
(there are ways to ease this, by using special patch boards)
2. The more differential (difference) equations you have and the higher
the order of each the more hardware in the form of integrators you
need.
(See also http://users.pandora.be/nicvroom/shor.htm )
In general with a Quantum Computer you have to be very much concerned with the hardware and not with the software.
What we need is a standard way to describe our problem, some form of CAD drawing, which we can give to the QC manufacturer in order for them to build our QC.
Nick.
I don't know any physicists who share this view, but I wouldn't be
surprised if there were some. Note that I'm not counting here the
fairly large number of physicists who believe quantum computing won't
happen not because it's fundamentally impossible but because it is
too difficult an engineering problem.
>
My main concern is that QC maybe is impossible. To "solve" that issue I have the following overall question: Is quantum entanglement a necessary feature for a QC to work?
To answer that question lets us study the two articles in Nature
identified as 7 and 8 in the following document:
http://users.pandora.be/nicvroom/shor.htm
In document 8
1. "Superposition is a one particle property."
2. "Entanglement is a characteristic of two or more particles."
IMO you can have a register of 13 Qubits with or without entanglement.
The difference, if I interpret the documents correct, lies in the
coupling i.e. without coupling no entanglement.
My more detailed question is entanglement of the 13 qubits required for Step 3 (Observe Register 2 for n=55 - See Document 1) Does Step 3 (Result of x^a Mod n) work when the qubits are in superposition ?
IMO Step 2 and Step 3 will also work when the 13 Qubits are in
superposition. In document 7 this means each qubit is oscillating
at his own frequency - with no interference between each qubit.
IMO when you measure Register 2 with or without entanglement
you have the SAME chance of measuring any of the values:
The same question I have for the combination Step 4 and Step 5: Is entanglement of the 13 qubits required for the FFT to function properly? If the answer is Yes then what is the observed difference? Does it mean that only with entanglement you have a 4.4% chance of measuring 4915 and not with superposition ?
> | I do expect that if quantum computing is discovered to fail due to fundamental reasons, somebody will win a Nobel Prize for this discovery. |
hum...
> | Peter Shor |
Nick
> |
In article |
> > |
"Kevin A. Scaldeferri" wrote: |
> |
> > |
I do not understand and or it is not clear to me. IMO if you want to have a worthwhile discussion about determistic and non-deterministic you must first define what those concepts are. I will give you my definition, but anyone is allowed to disagree and come up with a better one. |
> |
No, no, no... What I gave was not _my_ definition, nor am I interested in yours. The theory of computation has its definitions and it would be wise to conform to them. The definition of "non-deterministic" in this context does not imply randomness. |
For a definition of Deterministic see:
http://www.swif.uniba.it/lei/foldop/foldoc.cgi?deterministic
For a definition of Non-Determinism see:
http://www.swif.uniba.it/lei/foldop/foldoc.cgi?non-determinism
IMO if your algorithm or methode tries all possible solutions than your methode should be called deterministic. And "ofcourse" every time you will get the same answer.
For a definition of "non-deterministic polynomial time" See:
http://www.swif.uniba.it/lei/foldop/foldoc.cgi?non-deterministic+polynomial+time
Here they use the wording "trial and error"
What does "trial and error" mean ?
If it means: try all possible solutions than again I would call this
deterministic.
If it means: to use a random mumber generator than in order to get
every time the same answer your random number generator should
also every time generate the same number sequence.
The following shows "Non-deterministic Ada Programs"
http://www.csc.liv.ac.uk/~ped/teachadmin/algor/cooks_thm.html
This is Cook's Theorem via:
http://www.csc.liv.ac.uk/~ped/teachadmin/algor/comput.html
In that program they use a subroutine CHOOSE.
The question is how does "choose" select between 0 and 1.
Randomly ?
or by "Trail and Error" ?
> | (Note that if non-deterministic was the opposite of deterministic, than the question of whether P=NP would be trivially false. It is only because non-deterministic machines are a superset of deterministic machines that the question makes any sense at all.) |
> | No, you should break yourself of this terminology if you want to communicate with other people interested in computability. In the standard terminology, both deterministic and non-deterministic machine produce the same output every time for a given input. Only a randomized machine can produce different output on repeated runs. |
> > | Above you mention that we don't know how to build them so what is the point. |
> |
To understand the theory of computability. |
However that is not the subject of this thread. The subject of this thread is: "I was wondering what computer language one would use to program quantum computers."
A digital computer you can program in machine language but that is very cumbersome and not very user friendly. A much more friendly way is to use a higher level language for example ADA or Visual Basic (And many others)
The Question is: can you use any of those higher level languages to program a quantum computer.
IMO you can try to use those programming languages to SIMULATE a quantum computer on a digital computer. For example I have used EXCELL to simulate shor's algorithm on a PC. A free copy is availble via my url. However IMO you can not use any of those computer language on a quantum computer.
A Quantum computer is very much identical as an Analog Computer: You can not program an Analog Computer. In order for an Analog Computer to solve a problem you more or less have to build your own Analog Computer out of a set of available hardware modules: Integrators, Summers, Multipliers, limiters, wiring cords etc.
For a quantum computer based on what I read the same situation exists: In order to solve a problem on a quantum computer you must have all the hardware (Qubits and all the Quantum gates, which perform the quantum operations) hardwired together.
An interesting question to answer is if it possible to simulate a Quantum Computer on an Analog Computer including superposition and entanglement. If the answer is confirmative than the chance of simulating a Quantum Computer on a Digital Computer is almost answered.
Nick http://users.pandora.be/nicvroom/ See question 23
Please Read my reply to Robert Tucci first.
> |
In article <3EAA7B80.5DFF701E@pandora.be>,
Nicolaas Vroom |
> > |
A classical computer consists of a CPU memory with data (registers) and memory (registers/bits) with instructions |
> |
I think that you are missing a crucial element, which is that "instructions" and "data" are not two seperate entities. |
In my reply today to Robert Tucci I wrote in detail how a program line like:
An example in which one instruction is modified:
ML1 Load Reg1 with Memory Location 5 Reg1 = instruction ML2 Load Reg2 with Memory Location 1000 Reg2 = "A" ML3 ADD Reg1 with Reg2 Result in Reg4 Reg4 = instr + "A" ML4 Store Reg4 in Memory Location 5 ML5 Store Reg2 in Memory Location 1000ML = Memory Location.
Add the end of program execution:
When "A" = 0 nothing happens because ML5 is not modified When "A" = 1 ML5 is modified into: ML5 Store Reg2 in Memory Location 1001 That means ML 1001 contains a 1 When "A" = 2 ML 1002 contains a 2 etcModifying instructions is "dangerous". The above can easier be implemented by using index registers.
A more practical example in which instructions are modified is used by subroutine handling (return address) but that is not crucial and outside the scope of this thread.
> | This is of critical importance both theoretically, where it is central to concepts like universal machines and undecidibility, and practically, where it form the basis of powerful languages like Lisp and also enables a broad class of security breaches. |
IMO this has "nothing" to do with QC's and with the subject of this thread in particular.
> > |
I have written built in capital letters because that is
how I understand how you have to use a QC in the future.
I expect that there is no direct programming involved. You can use programming to decompose a computation, the output are like diagrams which can serve as blueprints to built a QC. |
> |
No, it is possible (theoretically, at least) to build a universal quantum computer. One would be able to program such a beast in an analogous method to a universal classical computer. |
In my reply to Robert Tucci I have shown how I envision such a program. It looks something like:
ML1 CNOT QB1 QB2 QB3 ML3 Rot QB3 180 ML5 CNOT QB3 QB6 QB7IMO with a Quantum Compiler you can generate such a program. However I have great problems of understanding how you build such a Quantum Computer which uses a CPU, instructions and a Program Counter. Above and most important which includes concepts like:
In short I have great doubts that you can program a QC. That does not mean that you can not solve all types of problems on a QC.
Nick. http://users.pandora.be/nicvroom/
> |
In article |
> > | Each different problem requires its own matrix or matrix of quantum logical gates. It is a mechanical (engineering?) hardware oriented problem. |
> |
No, this is not true. It is known, in theory, how to construct a universal quantum turing machine. In other words, you can build a general-purpose quantum computer. You do not have to have a custom machine for each problem you want to solve. |
Please go to the following document and study the pages 23-25
http://www.ccmr.cornell.edu/~mermin/qcomp/chap3.pdf
Page 23 shows figure 1, Page 24 shows figure 2 and Page 25 shows figure
3
Each of those figures shows a different circuit diagram to implement
the same problem or functionality.
i.e. for input qubits x0-x3 on the right side
i.e. for output qubits y0-y3 on the left side
i.e. and a matrix in between
That means figure 1 shows matrix 1, figure 2 matrix 2 and figure 3
matrix 3.
The question is how do you physical implement those three circuits in a general purpose QC.
IMO each matrix has to be built separately that means you need 3 QC's to solve those three implementations (in order to demonstrate all three problems in quick succession )
In principle you can also implement those three circuits in one QC in order to multi use the same input registers x0-x3 and y0-y3 however the matrix of that QC is larger than the sum of matrix 1 plus matrix 2 plus matrix 3, because you need additional selection logic.
If there is a fourth circuit than you must "rebuilt" your matrix and make it larger with matrix 4
> | There are several caveats and unknowns when it comes to building a QC in practice, but what you keep saying (that you can't build a general purpose QC) is false. |
Part of this discussion depents on definitions.
A special purpose QC is a QC which only can solve one particular problem
A general purpose QC is a QC which allows you to solve different
problems.
The question of course is what is the physical difference between
a spQC and a gpQC
i.e. what is it that a gpQC has more, as what a spQC does not have.
If you can give me some hints what those physical differences are than I will be very gratefull.
A PC is a general purpose computer. Each of those figures and circuits requires a separate program (which contains 4 lines of coding) Performing the functionality of figure 1 or circuit 1 means loading program 1 and excuting program 1 etc etc.
Nick http://users.pandora.be/nicvroom/
Created: 26 Maart 2003
Last updated: 29 April 2003
Back to my home page Contents of This Document