Quantum computer: can it divide w/o collapsing the wavefunction ?

http://groups.google.com/groups?q=sci.physics.research,+%22Quantum+computer:+can+it+divide+w/o+collapsing+the+wavefunction?%22&hl=en&sa=G&scoring=d

1 "Michael" Quantum computer: can it divide w/o collapsing the wavefunction ? zondag 7 september 2003 23:49
2 "Lubos Motl" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? maandag 8 september 2003 20:45
3 "P kinsler" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? vrijdag 12 september 2003 22:53
4 "Arkadiusz Jadczyk" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? vrijdag 12 september 2003 0:22
5 "Nicolaas Vroom" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? zaterdag 20 september 2003 0:18
6 "Nicolaas Vroom" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? zaterdag 27 september 2003 1:02
7 "Kevin A. Scaldeferri" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? zondag 28 september 2003 4:36
8 "Joe Rongen" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? maandag 29 september 2003 7:32
9 "Juergen Appel" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? maandag 29 september 2003 19:14
10 "Nicolaas Vroom" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? dinsdag 30 september 2003 7:48
11 "Tom Knight" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? woensdag 1 oktober 2003 7:48
12 "Kevin A. Scaldeferri" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? vrijdag 3 oktober 2003 1:34
13 "P. Gralewicz" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? vrijdag 3 oktober 2003 1:44
14 "Bill Pringlemeir" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? woensdag 8 oktober 2003 8:16
15 "Aaron Denney" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? zaterdag 11 oktober 2003 0:37
16 "Kevin A. Scaldeferri" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? zaterdag 11 oktober 2003 0:49
17 "Joe Rongen" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? vrijdag 17 oktober 2003 16:14
18 "Nicolaas Vroom" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? woensdag 1 oktober 2003 12:17:28
19 "Nicolaas Vroom" Re: Quantum computer: can it divide w/o collapsing the wavefunction ? woensdag 1 oktober 2003 19:50:58

The last 2 messages were rejected for publication in sci.physics.research


1 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Michael"
Onderwerp: Quantum computer: can it divide w/o collapsing the wavefunction ?
Datum: zondag 7 september 2003 23:49

A distinguishing feature of the Quantum Mechanics is the linear unitary evolution of the wave function. How, then, a division of the two numbers can be accomplished in a quantum computer without incurring a collapse of the wavefunction ?

Answer may be a pointer to the appropriate article. Your help is appreciated. Thanks.

MK

next posting 2
next posting 4


2 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Lubos Motl"
Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction
Datum: maandag 8 september 2003 20:45

On Sun, 7 Sep 2003, Michael wrote:

> A distinguishing feature of the Quantum Mechanics is the linear unitary evolution of the wave function. How, then, a division of the two numbers can be accomplished in a quantum computer without incurring a collapse of the wavefunction ?

Well, quantum computers are still *digital*. A qubit is a generalization of a bit. Whatever is possible with bits - i.e. with classical computers - is also possible with (the hypothetical) quantum computers. Classical computers are able to divide the numbers; they follow similar algorithms like those we were taught at basic school. Quantum computers can therefore do the same thing. They are not literally dividing one amplitude by another: if a computer does this literally, then it is an analogue computer, not a digital one.

You can see that a classical computer is able to divide two numbers, even though it exists in a world governed by the laws of quantum mechanics.

______________________________________________________________________________
E-mail: lumo@matfyz.cz   fax: +1-617/496-0110   Web: http://lumo.matfyz.cz/
	phone:          work: +1-617/496-8199  home: +1-617/868-4487
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      Superstring/M-theory is the language in which God wrote the world.

next posting 3


3 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction Datum: vrijdag 12 september 2003 22:53

Lubos Motl wrote:
> Well, quantum computers are still *digital*. A qubit is a generalization of a bit. Whatever is possible with bits - i.e. with classical computers - is also possible with (the hypothetical) quantum computers. Classical computers are able to divide the numbers; they follow similar algorithms like those we were taught at basic school. Quantum computers can therefore do the same thing. They are not literally dividing one amplitude by another: if a computer does this literally, then it is an analogue computer, not a digital one.

I disagree. Last year I saw a talk given by Barry Sanders and Stephen Bartlett, where they explained a theorem whereby certain classes of quantum computation were analogous to classical analogue computations. See

http://arXiv.org/abs/quant-ph/0110039

Qubits are interesting because they allow a continuous range of different superpositions -- this is clearly (at least to me) more analogous to an analog system than a binary digital one.

[aside: this is a slightly altered version of a post I made in the "Baez's Dream" thread here last year]

--
---------------------------------+---------------------------------
Dr. Paul Kinsler
Blackett Laboratory (QOLS)        (ph) +44-20-759-47520 (fax) 47714
Imperial College London,          Dr.Paul.Kinsler@physics.org
SW7 2BW, United Kingdom.          http://www.qols.ph.ic.ac.uk/~kinsle/

next posting 5


4 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Arkadiusz Jadczyk" Aan: Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction ? Datum: vrijdag 12 september 2003 0:22

On Sun, 7 Sep 2003 21:49:47 +0000 (UTC), qwerty6393@hotmail.com (Michael) wrote:

> A distinguishing feature of the Quantum Mechanics is the linear unitary evolution of the wave function. How, then, a division of the two numbers can be accomplished in a quantum computer without incurring a collapse of the wavefunction ?

Answer may be a pointer to the appropriate article. Your help is appreciated. Thanks.

MK

Nothing can be ever accomplished by a linear, unitary evolution. Normal quantum theory does not have the concept of an "event". But one can easily enhance quantum mechanics so as to accomodate for this.

Most physicists believe that such an enhancement is "inessential". Most believe that we do not nee to care about individual quantum systems that somehow do what they do, and in finite time. Usually phsyicists avoid asking certain questions that quantum mechanics has no answers for.

Here is a quote from Ann. der Phys. 4 (1995) 583-599. see also http://xxx.lanl.gov/abs/hep-th/9409189

"Another potential field of application of EEQT is in the theory and practice of quantum computation. Computing with arrays of coupled quantum rather than classical systems seems to offer advantages for special classes of problems (cf. \citen{lloyd93} and references therein). Quantum computers will have however to use classical interfaces, will have to communicate with, and be controlled by classical computers. Moreover, we will have to understand what happens during individual runs. Only EEQT is able to provide an effective framework to handle these problems. It keeps perfect balance of probabilities without introducing \lq negative probabilities\rq\/, and it needs only standard random number generators for its simulations. For a recent work where similar ideas are considered cf. \citen{korn93}"

A more recent review is here:

http://xxx.lanl.gov/abs/quant-ph/9812081

ark --

Arkadiusz Jadczyk http://www.cassiopaea.org/quantum_future/homepage.htm

--


5 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Nicolaas Vroom" Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction Datum: zaterdag 20 september 2003 0:18

p.kinsler@imperial.ac.uk wrote:

> Lubos Motl wrote:
> > Well, quantum computers are still *digital*. A qubit is a generalization of a bit. Whatever is possible with bits - i.e. with classical computers - is also possible with (the hypothetical) quantum computers. Classical computers are able to divide the numbers; they follow similar algorithms like those we were taught at basic school. Quantum computers can therefore do the same thing.

That is the question - See below.

> > They are not literally dividing one amplitude by another: if a computer does this literally, then it is an analogue computer, not a digital one.
>

I disagree.

SNIP

> Qubits are interesting because they allow a continuous range of different superpositions -- this is clearly (at least to me) more analogous to an analog system than a binary digital one.

IMO quantum computers (QC) are more closely to an analog computer (AC) than to a digital computer. (DC) On the other I doubt if QC can do the same (solve the same problems) as a DC, and if they can, they do it quite differently.

The main reason why QC are different from an DC becomes clear if you study how a DC add two numbers. Generally speaking adding two numbers uses steps and cycles. The problem is what is called the carry bit.

How does an "adder" work in a certain implementation. You need two source registers S1 and S2 and two destination registers D1 and D2 Suppose you want to add 999 + 1. At the beginning of the first step and in cycle 1:

S1 contains 999 and S2 contains 1
The whole operation goes in cycles.

Without giving the details:

At the end of cycle 1 S1 = 990 and S2 = 10
At the end of cycle 2 S1 = 900 and S2 = 100
At the end of cycle 3 S1 = 1000 and S2 = 0
Because S2 = 0 you can stop and S1 contains the final result. S2 = 0 is called the stop or finished condition.

Such an adder is very easy to implement on a DC but difficult on a QC, because you cannot use the step and cycle concept. The step and cycle concept means:
1. that you use the same hardware over and over again until the operation (adding two numbers) is finished.
For an "adder" this means that the result of the first step is stored in D1 and D2 and (in the next step) copied into S1 and S2. Than the next cycle starts, until D2 (S2) = 0.
2. you need a clock pulse in order to start the next cycle. A clock pulse is required in order to start the next cycle before the previous cylcle is finished - for synchronisation reasons. (Most probably you also need clock pulses inbetween steps.)

Both concepts are not available on a QC. A QC must contain all the necessary hardware to add both numbers instantaneous and to allow for superposition. What is worse if your problem requires 100 "adders" you need all the required hardware to perform all those 100 additions instantaneous (within certain constraints).

In general the required hardware on a QC increases lineair with the size of your problem.

For multipliers (integer and floating point) this hardware problems becomes worse. For dividers on a QC the problem becomes unsurmountable.

The same situation exists on an analog computer: The amount of harware (integrators, summers, multipliers, inverters) or modules increases lineair with the size of your problem. The reason is that on an AC the whole AC is involved "realtime" with solving your problem i.e. solving a diffential equation.

Suppose you want to make the following calculation:

X = (A*B) + C
On the DC that is easy. On a QC it is very difficult. Generally speaking you have to divide this equation into two:
D = A * B (1)
and X = D + C (2)
The problem is to implement this such that:
eq(1) is executed before eq(2).
What you can use is the "Stop or finished condition" explained above to test that equation 1 is finished and to start equation 2 (etc.) All of that requires extra hardware if you want a "sequence" of calculations and to maintain the benefits of superpositions.

A more general solution is to use clock pulses (timers) to start the next calculation i.e. equation 2.

The point is if you use clocks pulses the performance of a QC becomes identical as a DC and the benefits of superpositions disappears.

See http://users.pandora.be/nicvroom/shor.htm for more details.

Nick.

next posting 6


6 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Nicolaas Vroom"
Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction
Datum: zaterdag 27 september 2003 1:02

Nicolaas Vroom wrote:

> IMO quantum computers (QC) are more closely to an analog computer (AC) than to a digital computer. (DC)

As I explained:

> A QC must contain all the necessary hardware to add both numbers instantaneous and to allow for superposition. What is worse if your problem requires 100 "adders" you need all the required hardware to perform all those 100 additions instantaneous (within certain constraints).

To be more specific: A QC must contain all (must be built with all) the necessary hardware to solve your complete problem to benefit from superposition. For an AC this is the same. An AC needs to be built with all the necessary hardware (modules) to solve differential equations.

However there is one more reason why QC are more closely to an AC than to a DC.
An analog computer can not be programmed. An AC has to be patched using wires to make the connections between the different modules. Patch panels are used to make this easier. The same for a QC.

On a DC if your problem needs 100 multiplications, you only need one multiplier unit. The software takes care that your problem is, as a matter of speaking, subdivided in 100 instructions, which are executed sequential, each only requiring this one multiplier unit at a time. On a QC you need 100 multiplier units to benefit from superposition concept and no programming is available to ease this task.

On the other hand a QC is much more accurate than an AC. Related to accuracy a QC and a DC are the same, but this does not close the overall cap between a QC and a DC.

> See http://users.pandora.be/nicvroom/shor.htm for more details.

Nick.

next posting 7
next posting 8


7 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Kevin A. Scaldeferri"
Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction
Datum: zondag 28 september 2003 4:36

In article <3F7496F2.1BCAD2B0@pandora.be>, Nicolaas Vroom wrote:

> However there is one more reason why QC are more closely to an AC than to a DC. An analog computer can not be programmed. An AC has to be patched using wires to make the connections between the different modules. Patch panels are used to make this easier. The same for a QC.

This is not true. If you are not going to learn this after so many times that I and others have corrected you, I am not going to try to explain it again. Others who are interested can check the Google archives.

--
======================================================================
Kevin Scaldeferri			Calif. Institute of Technology
                      The INTJ's Prayer:
     Lord keep me open to others' ideas, WRONG though they may be.



8 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Joe Rongen"
Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction
Datum: maandag 29 september 2003 7:32

> In article <3F7496F2.1BCAD2B0@pandora.be>, Nicolaas Vroom wrote:

However there is one more reason why QC are more closely to an AC than to a DC. An analog computer can not be programmed.

Certainly, analog computers can be programmed!

An analog computer is a computing system which uses continuous physical variables such as voltage or pressure or other parameters to represent and manipulate the measurements it handles.

Since such system are mostly self sustained / controlled, that does not change the fact that it is basically an analog computer.

> An AC has to be patched using wires to make the connections between the different modules. Patch panels are used to make this easier. The same for a QC.

That was true for the 18th century and maybe even today in a few research labs. :-)

Regards Joe

-------------------------------------------------------
"We must never attempt to use the UN as a substitute
 for clear and resolute U.S. policy." - Barry Goldwater
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.521 / Virus Database: 319 - Release Date: 9/23/03

next posting 10


9 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Juergen Appel"
Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction
Datum: maandag 29 september 2003 19:14

Nicolaas Vroom wrote:

> IMO quantum computers (QC) are more closely to an analog computer (AC) than to a digital computer. (DC)
[...]
> The main reason why QC are different from an DC becomes clear if you study how a DC add two numbers. Generally speaking adding two numbers uses steps and cycles. The problem is what is called the carry bit.
[...]
> Such an adder is very easy to implement on a DC but difficult on a QC, because you cannot use the step and cycle concept. The step and cycle concept means:
1. that you use the same hardware over and over again until the operation (adding two numbers) is finished.

Why should that be?
Every operation in a quantum cumputer is a unitary transformation of the state. This can be a photon's trip through waveplates and mirrors, radiopulses in NMR, laser pules on trapped ions or whatever.

Nothing forbids using the same mirror, the same laser or the same trapped atom twice.

> A QC must contain all the necessary hardware to add both numbers instantaneous and to allow for superposition.

It is not necesseary to do the whole calculation instantaneous. The only requirement is, that all your operations on the system have to be unitary, to take advantage of the properties a QC offers. This forbids getting intermediate results. Only the final result is obtained by a "classical" measurement which destroys the coherence then.

BTW: Multiplications, especially of very large numbers, would be much faster on a quantum computer (if it only existed), since you can do very fast fourier transforms, IIRC.

Greetings J=FCrgen

--=20
GPG key:=20
http://pgp.mit.edu:11371/pks/lookup?search=3DJ%FCrgen+Appel&op=3Dget

next posting 19


10 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Nicolaas Vroom"
Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction
Datum: dinsdag 30 september 2003 7:48

Joe Rongen wrote:
>
> >

In article <3F7496F2.1BCAD2B0@pandora.be>, Nicolaas Vroom wrote:

However there is one more reason why QC are more closely to an AC than to a DC. An analog computer can not be programmed.

>

Certainly, analog computers can be programmed!

What is "your" definition of programming ?

IMO programming from a hardware point of view requires
1. An instruction counter, which points to the instruction being executed.
2. memory which contains instructions.
3. A CPU or Central Processing Unit which decomposes the instruction being executed into parts and performs certain operations. For example: Add two numbers, shift n places, jump to ...
4. At the end the instruction counter is increased with one or set to "any" other value.

(This is also my definition for Quantum Computers)

An Analog Computer does not have those capabilities. An Hybrid Computer has those capabilities, but only the Digital Computer part.

For more detail read the book: "Hybrid Computation" by George A Bekey and Walter J. Karplus. Specific Chapter 6: Complete Hybrid Computer Systems and Chapter 7: Software for Hybrid Computers.

Hybrid Computers are not the subject of this discussion.

> An analog computer is a computing system which uses continuous physical variables such as voltage or pressure or other parameters to represent and manipulate the measurements it handles.

That is correct.

For an analog computer two things are important:
1. If you want to solve a problem (differential equation) on an AC continuous the "whole" AC is involved.
2. If you want to increase your problem (add more diff. eq's) you have to add more hardware.

IMO for a QC this is the same. (give and take)

> Since such system are mostly self sustained / controlled, that does not change the fact that it is basically an analog computer.

That is correct but, I do not understand what your point is.

> > An AC has to be patched using wires to make the connections between the different modules. Patch panels are used to make this easier. The same for a QC.

Quoted in this way things become unclear. Maybe I'am partly to blame.

What should have been quoted is:
>> An analog computer can not be programmed.
( An AC has to be patched using wires to make the connections between the different modules. Patch panels are used to make this easier.)

The same for a QC.

My point was and stil is that a QC can not be programmed. The main problem is superposition.

Nicolaas Vroom

See http://users.pandora.be/nicvroom/shor.htm for more details.

next posting 11
next posting 12
next posting 13
next posting 17


11 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Tom Knight"
Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction
Datum: woensdag 1 oktober 2003 7:48

Nicolaas Vroom writes:
> What is "your" definition of programming ?

IMO programming from a hardware point of view requires
1. An instruction counter, which points to the instruction being executed.
2. memory which contains instructions.
3. A CPU or Central Processing Unit which decomposes the instruction being executed into parts and performs certain operations. For example: Add two numbers, shift n places, jump to ...
4. At the end the instruction counter is increased with one or set to "any" other value.

> An Analog Computer does not have those capabilities.
An Hybrid Computer has those capabilities, but only the Digital Computer part.
My point was and stil is that a QC can not be programmed.
The main problem is superposition.

This is confused in multiple directions.

(1) There are no real digital computers. All digital computers are (highly complex) analog computers. The individual gates and circuits can easily be modeled by a set of nonlinear differential equations. A good way of seeing that you can't in general solve differential equations is to notice that if you write the ODEs for a Turing machine, then there are proofs that you can't predict the behavior. So, if you admit that you program a "digital" computer, then you are also admitting that you can program a (specific) analog computer. Of course, not all devices are programmable or universal.

(2) You are missing the key ideas of interpretation and computational equivalence. The great idea of digital computation is that one general purpose computer can *behave* as another. Once you have a universal Turing machine, then you have everything. I'd recommend looking at Sussman and Abelson, "Structure and Interpretation of Computer Programs" and Minsky, "Finite and Infinite Machines."

Once you have a universal QC, then you can efficiently simulate every other one (and, as Feynman showed, you can efficiently simulate any quantum system).

next posting 18
next posting 14


12 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Kevin A. Scaldeferri"
Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction
Datum: vrijdag 3 oktober 2003 1:34

In article <3F77FFF4.985F1E32@pandora.be>, Nicolaas Vroom wrote:

> Joe Rongen wrote:

>> Certainly, analog computers can be programmed!

> What is "your" definition of programming ?

The one that computer scientists use, presumably. I.e., is the model of computation universal (equivalent to a Turing machine)?

> IMO programming from a hardware point of view requires
1. An instruction counter, which points to the instruction being executed.
2. memory which contains instructions.
3. A CPU or Central Processing Unit which decomposes the instruction being executed into parts and performs certain operations. For example: Add two numbers, shift n places, jump to ...
4. At the end the instruction counter is increased with one or set to "any" other value.

This is a description of a particular architecture. It is certainly not the only model of computation.

> An Analog Computer does not have those capabilities.

Wrong.

> For an analog computer two things are important:
1. If you want to solve a problem (differential equation) on an AC continuous the "whole" AC is involved.
2. If you want to increase your problem (add more diff. eq's) you have to add more hardware.

Wrong.

> IMO for a QC this is the same. (give and take)

Wrong.

> My point was and stil is that a QC can not be programmed. The main problem is superposition.

Wrong.

--
======================================================================
Kevin Scaldeferri			Calif. Institute of Technology
                      The INTJ's Prayer:
     Lord keep me open to others' ideas, WRONG though they may be.


13 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "P. Gralewicz"
Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction
Datum: vrijdag 3 oktober 2003 1:44

Nicolaas Vroom wrote:

> My point was and stil is that a QC can not be programmed. The main problem is superposition.

Actually, the superposition has nothing to do with the ability of a computer to be programmable. Both classical and quantum computers can be regarded as analog devices. One of the main differences between them is that the former operate by jumping between its stable points (labelled by digits) in the phase space, while the latter have no such equilibria by design. This makes the available number of states extend into continuum and we represent them with superpositions of the discrete basis.

Nevertheless, this is no obstacle for programming. All we need is the capability to perform controlled (conditional) operations. As in classical case the program is the initial state (or its part) fed to the universal machine.

The impression that QC are only hardware-programmable comes form the present-day algorithms which are like the CPU-circuit designs rather than programs we have used to.

pg


14 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Bill Pringlemeir"
Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction
Datum: woensdag 8 oktober 2003 8:16

On Wed, 1 Oct 2003, tk@suspiria.ai.mit.edu wrote:

> This is confused in multiple directions.

(1) There are no real digital computers. All digital computers are (highly complex) analog computers. The individual gates and circuits can easily be modeled by a set of nonlinear differential equations.

[snip]

I would disagree with this. The digital gates are designed to be highly non-linear. The typical gate has transistors function in only two states. Using other states is bad digital design and if it were to happen, the system would crash (search forbidden range, jitter, etc). An analog computer is distinctly different in that it is using a physical phenomena to solve a problem. The digital computer converts input to some finite state/algebra and solves the problem in this context. It must use ODE underneath (via transistor physics), but it has been structured to be finite to the programmer. It is an error in the system design to operate in other ranges. System clocking[1] ensures that the transistors have switch states, so from a programmer model it doesn't matter what is happening underneath (TTL, CMOS, ECL, vacuum tubes, etc).

> (2) You are missing the key ideas of interpretation and computational equivalence. The great idea of digital computation is that one general purpose computer can *behave* as another. Once you have a universal Turing machine, then you have everything. I'd recommend looking at Sussman and Abelson, "Structure and Interpretation of Computer Programs" and Minsky, "Finite and Infinite Machines."

Once you have a universal QC, then you can efficiently simulate every other one (and, as Feynman showed, you can efficiently simulate any quantum system).

I would agree with this section. In fact it tends to disprove your first point. If you are implicating a "universal Turing machine", you have a deterministic state (ala the tape). Solving equations by mathematical isomorphism with physical phenomena is distinctly different. Turing's tape is "only infinite"... It is not a real number, which is more than infinite (denumerable).

I am still not in understanding of how a QC would replicate a "universal Turing machine". However, if it did, it would be as general as any digital computer.

fwiw,
Bill Pringlemeir.

[1] It is possible and desirable to design asynchronous logic, but it is very difficult. All computers have a clock (often more than one), mapping to the movement of a turning machines tape... there are no half steps of the tape.

-- Paradigm is a word too often used by those who would like to have a new idea but cannot think of one. - Mervyn King

next posting 15
next posting 16


15 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Aaron Denney"
Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction
Datum: zaterdag 11 oktober 2003 0:37

In article , Bill Pringlemeir wrote:

> On Wed, 1 Oct 2003, tk@suspiria.ai.mit.edu wrote:

>> This is confused in multiple directions.

(1) There are no real digital computers. All digital computers are (highly complex) analog computers. The individual gates and circuits can easily be modeled by a set of nonlinear differential equations.

> I would disagree with this. The digital gates are designed to be highly non-linear. The typical gate has transistors function in only two states. Using other states is bad digital design and if it were to happen, the system would crash (search forbidden range, jitter, etc).

Yes, so it only uses particular sections of the analog input space. It's still analog at heart, and the digital approximation is just a convenient abstraction.

> error in the system design to operate in other ranges. System clocking[1] ensures that the transistors have switch states, so from a programmer model it doesn't matter what is happening underneath (TTL, CMOS, ECL, vacuum tubes, etc).

A programmer need not care, but the designer must.

> I am still not in understanding of how a QC would replicate a "universal Turing machine". However, if it did, it would be as general as any digital computer.

Well, technically it can't, of course, any more than a standard digital computer can, as neither has infinite tape capacity. It's still a good approximation, of course, because most problems we run fit in the space of RAM + swap. (They must, otherwise we wouldn't run them...)

It isn't that hard to define quantum analogs of Turing machines, in fact, there are a few different definitions, with different restrictions.

> [1] It is possible and desirable to design asynchronous logic, but it is very difficult. All computers have a clock (often more than one), mapping to the movement of a turning machines tape... there are no half steps of the tape.

It's actually not that hard if you base things on CSP (Communicating Sequentaial Processes -- See Tony Hoare's work) and have handshaking on the microarchitecture level replace clocking signals. A bit harder is optimizing things to minimize power usage and area while maximizing performance, and at the same time not overspecializing cells to the point of making layout take forever. But this is drifting off topic.

-- Aaron Denney -><-


16 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Kevin A. Scaldeferri"
Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction
Datum: zaterdag 11 oktober 2003 0:49

In article , Bill Pringlemeir wrote:

> I am still not in understanding of how a QC would replicate a "universal Turing machine".

A good start might be to enter "universal quantum turing machine" or "universal quantum computer" into a search engine.

--
======================================================================
Kevin Scaldeferri			Calif. Institute of Technology
                      The INTJ's Prayer:
     Lord keep me open to others' ideas, WRONG though they may be.

17 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Joe Rongen"
Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction
Datum: vrijdag 17 oktober 2003 16:14

"Nicolaas Vroom" wrote in message news:3F77FFF4.985F1E32@pandora.be...
> Joe Rongen wrote:
> >
> > >

In article <3F7496F2.1BCAD2B0@pandora.be>, Nicolaas Vroom wrote:

However there is one more reason why QC are more closely to an AC than to a DC. An analog computer can not be programmed.

> >

Certainly, analog computers can be programmed!

>

What is "your" definition of programming ?

AC programming is entirely different from DC programming. Here are some reasons why:

Electronic analog computers can be continuously and automatically programmed / controlled by their feedback loop(s). Or as in WWII where automatic electromechanical and later electronic analog computers were used as anti aircraft computers. Dials were used to program for windspeed, direction, etc... and that is how one programs an AC.

Another example: the abacus is a hand-operated digital computer; the slide rule is a hand-operated analog computer.

Here is a link to an "Analog computer museum", enjoy! http://dcoward.best.vwh.net/analog/

Regards Joe

"An eye for an eye only makes the whole world blind." -- Mahatma Gandhi


18 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Nicolaas Vroom"
Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction
Datum: woensdag 1 oktober 2003 12:17:28

Tom Knight wrote:
>

Nicolaas Vroom writes:

> > What is "your" definition of programming ?

IMO programming from a hardware point of view requires
1. An instruction counter, which points to the instruction being executed.
2. memory which contains instructions.
3. A CPU or Central Processing Unit which decomposes the instruction being executed into parts and performs certain operations.
For example: Add two numbers, shift n places, jump to ...
4. At the end the instruction counter is increased with one or set to "any" other value.

>
> >

5) An Analog Computer does not have those capabilities.
6) An Hybrid Computer has those capabilities, but only the Digital Computer part.
7) My point was and stil is that a QC can not be programmed.
8) The main problem is superposition.

>

This is confused in multiple directions.

What is confused ? All or some of the items 1-8 ? A more detailed explanation would be welcome.

> (1) There are no real digital computers. All digital computers are (highly complex) analog computers.
Physical all digital, analog and quantum computers (?) are more or less the same. You can call them electronic devices. At micro level they all are built around resistors, diodes, capacitors and inductors.
At functional level (macro) they are totally different. You can not calculate pi on a AC, you need a DC. It is a misnomer to call a DC an AC.

> The individual gates and circuits can easily be modeled by a set of nonlinear differential equations. A good way of seeing that you can't in general solve differential equations is to notice that if you write the ODEs for
ODEs = Ordinary Differential Equations ? See: http://math.bu.edu/odes/
> a Turing machine, then there are proofs that you can't predict the behavior.
I do not understand.

> So, if you admit that you program a "digital" computer, then you are also admitting that you can program a (specific) analog computer.
If you have an AC consisting of modules (Multipliers, adders, Integrators) and you want that the AC is going to solve your problem you need wires to make the connections between the different modules.
There is no programming involved. Programming belongs strictly to the realm of DC's

> Of course, not all devices are programmable or universal.

(2) You are missing the key ideas of interpretation and computational equivalence.

?

> The great idea of digital computation is that one general purpose computer can *behave* as another.
If you mean that in principle on each DC you can solve the same problem than I agree.

> Once you have a universal Turing machine, then you have everything.
Seems optimistic. But what has this to do with the 8 items mentioned above.

> Once you have a universal QC, then you can efficiently simulate every other one (and, as Feynman showed, you can efficiently simulate any quantum system).
Also optimistic. What is an universal QC ?

Nicolaas Vroom


19 Quantum computer: can it divide w/o collapsing the wavefunction ?

Van: "Nicolaas Vroom"
Onderwerp: Re: Quantum computer: can it divide w/o collapsing the wavefunction
Datum: woensdag 1 oktober 2003 19:50:58

Juergen Appel wrote:
>

Nicolaas Vroom wrote:

> >

IMO quantum computers (QC) are more closely to an analog computer (AC) than to a digital computer. (DC)

> [...]
> > The main reason why QC are different from an DC becomes clear if you study how a DC add two numbers. Generally speaking adding two numbers uses steps and cycles. The problem is what is called the carry bit.
> [...]
> > Such an adder is very easy to implement on a DC but difficult on a QC, because you cannot use the step and cycle concept. The step and cycle concept means: 1. that you use the same hardware over and over again until the operation (adding two numbers) is finished.
>

Why should that be?

It is not a must for a DC, but if you do, than you must follow that rule. Item 1 says that on a DC you can use some form of loop construct. The hardware within the loop is as often executed until some final condition is reached.

In a QC such a concept is not available. You must built an adder with all the necessary hardware to add both numbers instantaneous. For an adder this is a rather simple constraint for a multiplier this becomes much more complex.

SNIP.

> > A QC must contain all the necessary hardware to add both numbers instantaneous and to allow for superposition.
>

It is not necesseary to do the whole calculation instantaneous.

That is correct. You should do the calculation very fast. But how fast.
To study this issue go to: http://users.pandora.be/nicvroom/shor.htm#ref3 which is part of hardware to perform shor's algorithm. The left part shows the Hadamard operation.
The right part shows Register R2 which contains the result.
The middle part shows the hardware to calculate the function x^a mod n

The Hadamard operation is performed on 4 Qubits. But what means an Hadamard operation physical ? Is it a (random number) generator which generates numbers inbetween 0 and 15 a) sequential ?
b) or simulataneous ?
c) or in superposition ?
What is true that when you measure Register a it should have a value inbetween 0 and 15 with all equal probability.
If you select c above than what means in superposition physical ?

IMO if you divide time in small enough increments dt, at the end of each increment dt, Register a has a value inbetween 0 and 15.

If that is true than the hardware in the middle part should be fast enough to calculate in dt (at the end of the next dt) the value of Register R2. If the hardware (including all line delays) is not fast enough than Register R2 contains carbage.

> The only requirement is, that all your operations on the system have to be unitary, to take advantage of the properties a QC offers.
I think that the following documents this describe: http://140.112.19.180/course%5CQC%5CCybenko2001.pdf http://web.nwe.ufl.edu/~fischer/tech/qc/qcpaper/node18.html

IMO the sketch discussed above uses that concept. As far as I understand unitary operations (QC's) should not include loop structures. For a DC such a constraint does not exist.

> This forbids getting intermediate results. Only the final result is obtained by a "classical" measurement which destroys the coherence then.

Nicolaas Vroom


Created: 6 October 2003

Back to my home page Contents of This Document