A progamming language for quantum computers?
John Eastmond
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
Daryl McCullough
east...@yahoo.com says...
>
>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
da...@atc-nycorp.com
Ithaca, NY
Kevin A. Scaldeferri
In article <fbf30ca8.03032...@posting.google.com>,
John Eastmond <east...@yahoo.com> wrote:
>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.
Lawrence Foard
>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
Robert Tucci
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)
Ken S. Tucker
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___________|
(o/p)= 1, unless A AND B shut off (1).
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.
Either way, I think the NAND must be made to function
if a processor can be developed.
Thanks and regards
Ken S. Tucker
Squark
> > I was wondering what computer language one would use to
> >program quantum computers.
>
> 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. 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_N...@excite.exe
(just spell the particle name correctly and change the
extension in the obvious way)
Peter Shor
> 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."
Kevin A. Scaldeferri
Squark <fii...@yahoo.com> wrote:
>ke...@sue.its.caltech.edu (Kevin A. Scaldeferri) wrote in message
>news:<b5qv0i$lc9$1...@sue.its.caltech.edu>...
>> > 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).
Hendrik Weimer
east...@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
Michael Weiss
Kevin A. Scaldeferri wrote:
: 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).
David Madore
scripsit:
> 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 <e1>
... <en>) which nondeterimistically returns one of the values <e1>
through <en>. The interpreter, of course, not only runs slowly but
also consumes vast amounts of memory, as all possible threads of
computation must be simulated sequentially.
[*] 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....@ens.fr,
http://www.eleves.ens.fr:8080/home/madore/ )
Robert Tucci
> ent...@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
pete
> 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
Robert Tucci
NAND:
(a,b)-> a + b + (not a)*(not b)
or equivalently
(a, b) -> not(a*b)
Squark
> 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.
Ralph Hartley
Peter Shor wrote:
> 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 was thinking, last time this topic came around, that it might be amusing
to make a wager on that. Of course, it's no good betting that something
will *never* happen, because you can never collect, and the prospect of QC
is to distant to know what would be a good deadline.
So here's my proposition:
I will bet John Baez, and/or all takers, $1 that a quantum computer will be
built *before* any quantum gravitational effect is experimentally observed.
As long as neither event happens (which we will all agree is a distinct
possibiliy), nobody collects.
To count, the quantum computer must be usable to factor a number that
cannot otherwise be factored at that time, or do some task that is mutually
agreed to be something you need a quantum computer to do.
A quantum gravitational effect is any prediction of quantum gravity that is
more or less unique to quantum gravity (i.e. not found in GR or reasonable
non-gravitational quantum theories). There is no way to define it exactly,
but I think people know what I mean.
Though string theories prefer SUSY, and seem to include gravity, I wouldn't
count SUSY as a gravitational effect, at least not by itself. But I could
be convinced to change my mind if the theory made specific enough predictions.
Detecting Hawking radiation *would* be a quantum gravitational effect, even
though it isn't the result of a full quantum gravity theory.
The experiment discussed on this list recently "Re: Planck scale
fluctuations" would have counted, if it had found any (and it was
confirmed, to a reasonable degree, that that's what it found).
Of course, I would be *almost* as happy to lose as to win.
Ralph Hartley
[Moderator's note: Any parties interested in taking part in this bet
should work out the details in private email. -- KS]
David Wnsemius
news:939044f.03032...@posting.google.com:
> (http://www.tph.tuwien.ac.at/~oemer/qcl.html). Not there/
no www.
http://tph.tuwien.ac.at/~oemer/qcl.html
--
David Winsemius
Nicolaas Vroom
Squark wrote:
>
> Hendrik Weimer <hen...@enyo.de> wrote in message news:<867kaje...@gienah.enyo.de>...
> > 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.
Robert Tucci
> (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.
Robert Tucci
> 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
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
Squark
news:<b6052o$6ep$1...@inky.its.caltech.edu>...
> 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 :-)
Kevin A. Scaldeferri
Robert Tucci <tu...@ar-tiste.com> wrote:
>peter...@aol.com (Peter Shor) wrote in message
news:<9b2e17b4.03032...@posting.google.com>...
>> ent...@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 A. Scaldeferri
pete <pfi...@mindspring.com> wrote:
>Kevin A. Scaldeferri wrote:
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.
Ralph Hartley
> 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
Ken S. Tucker
[Large wads of quoted text deleted by overworked moderator]
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 1
And 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
Hendrik Weimer
> Hendrik Weimer <hen...@enyo.de> wrote in message
> news:<867kaje...@gienah.enyo.de>...
> > 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.
Stephen Riley
<har...@aic.nrl.navy.mil> writes
>To count, the quantum computer must be usable to factor a number that
>cannot otherwise be factored at that time, or do some task that is
>mutually agreed to be something you need a quantum computer to do.
I'm wondering what kind of limits exist for classical devices in solving
computationally hard problems, such as factoring? For instance would my
following (hypothetical) machine factor numbers? :
[Brief and speculative factoring device description follows...]
Imagining a 2-D box containing N 'atoms', where N is the number to be
factored. The box is initially setup to hold these atoms in a 1xN
configuration, (i.e. all in a row). So the length of the sides of the
box are the factors of N, and the area (N) is the number to be factored.
This area remains constant for valid solutions. The computation begins
when box squeezes the contents from all sides, pushing it from an
initial 1xN configuration to a final Nx1 configuration (or stopping
earlier at sqrt(N), a square ). Any integer area registered between the
start and end states, are the sought factors of N.
I'd imagined something a bit more complicated than the above description
to get it to work, but that's the general idea. I'm assuming small N
works (e.g. squashing 100 billiard balls would form a 10x10 square and
the other factors), but I haven't tried it, and guessing that it would
be increasingly difficult to build for larger N. The best I can do is
test with four coins I have to hand :)
--
Stephen Riley
Ralph Hartley
> I'm wondering what kind of limits exist for classical devices in solving
> computationally hard problems, such as factoring?
The actual limit is unknown.
> For instance would my
> following (hypothetical) machine factor numbers? :
>
> [Brief and speculative factoring device description follows...]
>
> Imagining a 2-D box containing N 'atoms', where N is the number to be
> factored.
Two problems:
(1) Where are you going to find a 100+ digit number of atoms? Last I
checked, there *aren't* that many. Classical algorithms aren't *that* bad,
the numbers where they start taking too long are still fairly big.
(2) You would have to shake the box around for a *long* time to get them to
settle into a rectangular array. Just "squashing" them won't do it. The
balls would get stuck in some other pattern. There is a class of algorithms
that simulates something like this (simulated annealing). They aren't
always particularly fast, but they are used sometimes (not for factoring).
Ralph Hartley
Kevin A. Scaldeferri
>news:<b6052o$6ep$1...@inky.its.caltech.edu>...
>
>> 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.
Gralp
> 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.
>
> 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
Stephen Riley
<har...@aic.nrl.navy.mil> writes
>Stephen Riley wrote:
>> For instance would my following (hypothetical) machine factor
>>numbers? :
>Two problems:
>
>(1) Where are you going to find a 100+ digit number of atoms? Last I
>checked, there *aren't* that many. Classical algorithms aren't *that*
>bad, the numbers where they start taking too long are still fairly big.
Good point, though I was wondering if a physical analogue of this type
of computation would be more of hypothetical interest. For example its
limitations, a comparison with a Turing machine, whether it runs in
polynomial/exponential time, etc. I thought it might be a good model for
this type of comparison.
>
>(2) You would have to shake the box around for a *long* time to get
>them to settle into a rectangular array. Just "squashing" them won't do
>it. The balls would get stuck in some other pattern. There is a class
>of algorithms that simulates something like this (simulated annealing).
>They aren't always particularly fast, but they are used sometimes (not
>for factoring).
I didn't fully describe the machine, but I'd imagined it would be easy
to keep the balls centres lined up (and I have no problem accepting I
could be wrong). I don't want to develop this into something
crackpottish though, so if you don't see that (crucial) element as
easily obtainable I won't persue it.
--
Stephen Riley
Squark
> 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.
Ralph Hartley
Robert Tucci wrote:
> 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
Robert Tucci
> 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".
Dirk Bruere at Neopax
"Lawrence Foard" <ent...@farviolet.com> wrote in message
news:b5qtco$a1i$1...@farviolet.com...
>
> 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
Nicolaas Vroom
"Kevin A. Scaldeferri" wrote:
>
> In article <939044f.03032...@posting.google.com>,
> Squark <fii...@yahoo.com> wrote:
> >ke...@inky.its.caltech.edu (Kevin A. Scaldeferri) wrote in message
> >news:<b6052o$6ep$1...@inky.its.caltech.edu>...
> >
> >> 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:
x = (a + b) Mod 10
b = x
With a = 7 and b = 1 you get the following pseudo random sequence:
8, 5, 2, 9, 6, 3, 0, 7, 4, 1, 8, 5, 2, etc
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:
Remove the clock pulses of a deterministic machine.
However such a machine is not very practical.
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
Hendrik Weimer
> 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.
Ralph Hartley
> 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
Kevin A. Scaldeferri
Robert Tucci <tu...@ar-tiste.com> wrote:
>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 A. Scaldeferri
In article <b6l03v$ctq$1...@lfa222122.richmond.edu>,
Nicolaas Vroom <nicolaa...@pandora.be> wrote:
>"Kevin A. Scaldeferri" wrote:
>> In article <939044f.03032...@posting.google.com>,
>> Squark <fii...@yahoo.com> wrote:
>> >ke...@inky.its.caltech.edu (Kevin A. Scaldeferri) wrote in message
>> >news:<b6052o$6ep$1...@inky.its.caltech.edu>...
>> >> 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 A. Scaldeferri
In article <d719cdf7.03040...@posting.google.com>,
Gralp <gr...@poczta.onet.pl> wrote:
>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.
Alfred Einstead
> 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.
Kevin A. Scaldeferri
Alfred Einstead <whop...@csd.uwm.edu> wrote:
>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.
Nicolaas Vroom
Robert Tucci wrote:
> 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?
Robert Tucci
> 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.
Nicolaas Vroom
Robert Tucci wrote:
> Nicolaas Vroom <nicolaa...@pandora.be>
> wrote in message news:<3EA19EC3...@pandora.be>...
> > 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
Kevin A. Scaldeferri
Nicolaas Vroom <nicolaa...@pandora.be> wrote:
>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.
Robert Tucci
> 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.
These diagrams should not be understood
as classical hardware circuit diagrams.
They are more akin to classical flow charts.
Nicolaas Vroom
Robert Tucci 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 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
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 001003
The program can also described as in one line as follows:
D = A + B + C
A compiler "translates" this line in the 6 instructions
as described above.
> 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 QB7
Ofcourse 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.
Okay
But still you have to use those flowcharts to BUILT a QC.
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
Robert Tucci
> 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.
Kevin A. Scaldeferri
Nicolaas Vroom <nicolaa...@pandora.be> wrote:
>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.
Nicolaas Vroom
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/
Kevin A. Scaldeferri
Nicolaas Vroom <nicolaa...@pandora.be> wrote:
>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.
Nicolaas Vroom
"Kevin A. Scaldeferri" wrote:
>
> In article <3EB12AFE...@pandora.be>,
> Nicolaas Vroom <nicolaa...@pandora.be> 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
>
> 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
Kevin A. Scaldeferri
Nicolaas Vroom <nicolaa...@pandora.be> wrote:
>
>
>"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.
Nicolaas Vroom
>
> In article <ba677d$2mf$1...@lfa222122.richmond.edu>,
> Nicolaas Vroom <nicolaa...@pandora.be> wrote:
> >
> >
> >"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.
Kevin A. Scaldeferri
Nicolaas Vroom <nicolaa...@pandora.be> wrote:
>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.)
Hendrik Weimer
ke...@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.
Dirk Bruere at Neopax
"Nicolaas Vroom" <nicolaa...@pandora.be> wrote in message
news:3ECE36A7...@pandora.be...
>
>
> 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.
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
Dirk Bruere at Neopax
"Hendrik Weimer" <hen...@enyo.de> wrote in message
news:86y90vt...@gienah.enyo.de...
>
> ke...@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
Hendrik Weimer
"Dirk Bruere at Neopax" <di...@neopax.com> writes:
> "Hendrik Weimer" <hen...@enyo.de> wrote in message
> news:86y90vt...@gienah.enyo.de...
> >
> > 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.
Kevin A. Scaldeferri
Hendrik Weimer <hen...@enyo.de> wrote:
>
>ke...@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:
The IBM scientists controlled a vial of a billion-billion (10^18)
of these molecules so they executed Shor's algorithm and correctly
identified 3 and 5 as the factors of 15.
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 A. Scaldeferri
Hendrik Weimer <hen...@enyo.de> wrote:
>
>"Dirk Bruere at Neopax" <di...@neopax.com> writes:
>
>> "Hendrik Weimer" <hen...@enyo.de> wrote in message
>> news:86y90vt...@gienah.enyo.de...
>> >
>> > 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.
Nicolaas Vroom
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 ?
Nicolaas Vroom
>
> "Nicolaas Vroom" <nicolaa...@pandora.be> wrote in message
> news:3ECE36A7...@pandora.be...
> >
> >
> > 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"
> > 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.
Dirk Bruere at Neopax
"Nicolaas Vroom" <nicolaa...@pandora.be> wrote in message
news:3ED9CB41...@pandora.be...
> 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.
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
Hendrik Weimer
ke...@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
Ralph Hartley
> 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
Kevin A. Scaldeferri
Hendrik Weimer <hen...@enyo.de> wrote:
>
>ke...@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?