December 2003 - cypherpunks-legacy

comp.html
by Jim Choate 17 Dec '03

17 Dec '03

_________________________________________________________________ next up previous Next: Computing at the atomic scale _________________________________________________________________ QUANTUM COMPUTATION: A TUTORIAL COOL CENTRAL SITE OF THE HOUR Samuel L. Braunstein Abstract: Imagine a computer whose memory is exponentially larger than its apparent physical size; a computer that can manipulate an exponential set of inputs simultaneously; a computer that computes in the twilight zone of Hilbert space. You would be thinking of a quantum computer. Relatively few and simple concepts from quantum mechanics are needed to make quantum computers a possibility. The subtlety has been in learning to manipulate these concepts. Is such a computer an inevitability or will it be too difficult to build? In this paper we give a tutorial on how quantum mechanics can be used to improve computation. Our challenge: solving an exponentially difficult problem for a conventional computer---that of factoring a large number. As a prelude, we review the standard tools of computation, universal gates and machines. These ideas are then applied first to classical, dissipationless computers and then to quantum computers. A schematic model of a quantum computer is described as well as some of the subtleties in its programming. The Shor algorithm [1,2] for efficiently factoring numbers on a quantum computer is presented in two parts: the quantum procedure within the algorithm and the classical algorithm that calls the quantum procedure. The mathematical structure in factoring which makes the Shor algorithm possible is discussed. We conclude with an outlook to the feasibility and prospects for quantum computation in the coming years. Let us start by describing the problem at hand: factoring a number N into its prime factors (e.g., the number 51688 may be decomposed as ). A convenient way to quantify how quickly a particular algorithm may solve a problem is to ask how the number of steps to complete the algorithm scales with the size of the ``input'' the algorithm is fed. For the factoring problem, this input is just the number N we wish to factor; hence the length of the input is . (The base of the logarithm is determined by our numbering system. Thus a base of 2 gives the length in binary; a base of 10 in decimal.) `Reasonable' algorithms are ones which scale as some small-degree polynomial in the input size (with a degree of perhaps 2 or 3). On conventional computers the best known factoring algorithm runs in steps [3]. This algorithm, therefore, scales exponentially with the input size . For instance, in 1994 a 129 digit number (known as RSA129 [3']) was successfully factored using this algorithm on approximately 1600 workstations scattered around the world; the entire factorization took eight months [4]. Using this to estimate the prefactor of the above exponential scaling, we find that it would take roughly 800,000 years to factor a 250 digit number with the same computer power; similarly, a 1000 digit number would require years (significantly lon ger than the age of the universe). The difficulty of factoring large numbers is crucial for public-key cryptosystems, such as ones used by banks. There, such codes rely on the difficulty of factoring numbers with around 250 digits. Recently, an algorithm was developed for factoring numbers on a quantum computer which runs in steps where is small [1]. This is roughly quadratic in the input size, so factoring a 1000 digit number with such an algorithm would require only a few million steps. The implication is that public key cryptosystems based on factoring may be breakable. To give you an idea of how this exponential improvement might be possible, we review an elementary quantum mechanical experiment that demonstrates where such power may lie hidden [5]. The two-slit experiment is prototypic for observing quantum mechanical behavior: A source emits photons, electrons or other particles that arrive at a pair of slits. These particles undergo unitary evolution and finally measurement. We see an interference pattern, with both slits open, which wholely vanishes if either slit is covered. In some sense, the particles pass through both slits in parallel. If such unitary evolution were to represent a calculation (or an operation within a calculation) then the quantum system would be performing computations in parallel. Quantum parallelism comes for free. The output of this system would be given by the constructive interference among the parallel computations. _________________________________________________________________ * Computing at the atomic scale: * Reversible computation: * Classical universal machines and logic gates: * FANOUT and ERASE: * Computation without ERASE: * Elementary quantum notation: * Logic gates for quantum bits: * Model quantum computer and quantum code: * Quantum parallelism: Period of a sequence: * Factoring numbers: * Prospects: * Appendix: * Acknowledgements: * References * About this document ... _________________________________________________________________ next up previous Next: Computing at the _________________________________________________________________ _________________________________________________________________ Samuel L. Braunstein Wed Aug 23 11:54:31 IDT 1995

1 0

Re: hackers and minick
by SteffenHo＠aol.com 17 Dec '03

17 Dec '03

In a message dated 98-01-29 15:44:07 EST, kes21(a)chat.ru writes: << Hello there!!! I send this letter because i want to know anything about hackers Kevin Mitnick please send more information about these topics my E-mail kes21(a)chat.ru >> www.mitnick.com or www.kevinmitnick.com

1 0

EPR, Bell, and FTL Bandwidth (fwd)
by Jim Choate 17 Dec '03

17 Dec '03

Forwarded message: > From: Eric Cordian <emc(a)wire.insync.net> > Subject: EPR, Bell, and FTL Bandwidth > Date: Wed, 28 Jan 1998 14:17:49 -0600 (CST) > Think of the classical case. I bake two fortune cookies, one with > "FOO" written on the slip of paper inside, and the other reading > "BAR." I then put them in a box and shake it for quite a while, until > the final state has chaotic dependence upon initial conditions, and > cannot be predicted. I then keep one fortune cookie, and mail the > other one to Lucky Green in Tonga. > > Someday in the future, I open my cookie, and instantly know what Lucky > will see when he opens his. True, but your opening your cookie does not *force* Lucky to open his at the same time. This is one fault with this model. The 'state' of the cookies are not inter-dependant as the polarization of the photon pairs are. > In doing so, I have created a > "instantaneous" correlation between two things separated by a vast It isn't instantanous, the correlation existed when they were printed and doesn't change. If I destroy one of the cookies it doesn't destroy the other spontaneously as would happen in a correlated photon-pair. The state of the individual cookies exists because of the observer and not a fundamental requirement of the cookies existing. > I am sure we will agree that there was no genuine faster-then-light > communication of information in this case. On this we can agree. > In quantum mechanics, pairs of observables may have the property that > both of them may not be known precisely for a physical system. The > Heisenberg Uncertainty principle states this for position and > momentum. Incorrect. The Heisenberg Uncertainty Principle states that in order to measure one parameter the other must *necessarily* change because they are in actuality different aspects of the *same* characteristic. They are *not* indipendant aspects of the system being observed. Momentum and position are different sides of the same coin. A conservation effect is what we are dealing with. This same conservation issue arises, and in fact allows FTL state transitions, with bound photon-pairs. > Similar relationships exist for energy and time, > polarization or angular momentum measured with respect to different > axes, and various other things. In addition, measuring a physical > system for one such variable always changes its wavefunction into one > for which the value of that variable is precisely specified, and the > value of the other "non-commuting" variable is not. Not quite. In the act of measuring one parameter we necessarily change the other. That change is what we can't measure *at the same time* not the absolute value at a given time tau. > You can see this easily with three polarizing filters. If you shine a > light through two of them at right angles to each other, it will be > completely blocked. Only if the light has a single polarization. If you shine a circularly polarized light through you will in fact see light on the other side. [more stuff deleted] ____________________________________________________________________ | | | The most powerful passion in life is not love or hate, | | but the desire to edit somebody elses words. | | | | Sign in Ed Barsis' office | | | | _____ The Armadillo Group | | ,::////;::-. Austin, Tx. USA | | /:'///// ``::>/|/ http://www.ssz.com/ | | .', |||| `/( e\ | | -====~~mm-'`-```-mm --'- Jim Choate | | ravage(a)ssz.com | | 512-451-7087 | |____________________________________________________________________|

3 2

Quantum teleportation and communication
by Anonymous 17 Dec '03

17 Dec '03

Tim May writes: > Imagine a pair of photons sent in opposite directions. With different > polarizations, but "tangled." Observer A measures a polarization of "1." > > He then knows that Observer B will measure "0." > > All that is revealed is a _correlation_, a kind of structure built into the > Universe. Interesting, but not so weird as it seems. (And this is not any > kind of "action at one site instantaneously changing the state far away." > No more so than sending two envelopes out, one with a "1" inside and the > other with a "0" inside changes things instantaneously.....) > > No signal sending is possible because neither observer can "change" the > polarization of a photon. Tim May knows no more about quantum mechanics than he does about cryptography. He is wrong about the nature of the correlation between the two photons. Bell's theorem shows that if local realism (a technical concept which is hard to deny) holds, then when Observer A changes the way he performs his measurements, what Observer B sees does change. It is completely mistaken to think of the "two envelope" analogy as applying to quantum correlations. There is something much stranger going on here. Don't trust what Tim May writes. He is not only a hypocrite (complaining about chemistry discussions while adding to an equally off-topic physics thread), but a fool as well.

2 1

Microsoft Internet Explorer: Request for Comments
by Fisher Mark 17 Dec '03

17 Dec '03

(taking a deep breath, and donning a flame-resistant Kevlar suit...) We are meeting with Microsoft tomorrow (1/29, 10am EST) to discuss the problems in and needed enhancements for Internet Explorer 4.x. If anyone would care to pass along their comments, I would welcome them. Note that I would prefer serious comments, although any that are both sufficiently humorous and not too defamatory towards Microsoft might also be passed along. (We currently have lists of 73 bugs and 27 enhancement requests...) ========================================================== Mark Leighton Fisher Thomson Consumer Electronics fisherm(a)indy.tce.com Indianapolis, IN "Browser Torture Specialist, First Class"

2 1

More down-to-earth apps for quantum teleportation...
by Jim Choate 17 Dec '03

17 Dec '03

Hi, On a slightly different tack, consider the application of quantum teleportation to computer construction issues related to propagation delays and multiplexing of data and control lines in limited volumes. ____________________________________________________________________ | | | The most powerful passion in life is not love or hate, | | but the desire to edit somebody elses words. | | | | Sign in Ed Barsis' office | | | | _____ The Armadillo Group | | ,::////;::-. Austin, Tx. USA | | /:'///// ``::>/|/ http://www.ssz.com/ | | .', |||| `/( e\ | | -====~~mm-'`-```-mm --'- Jim Choate | | ravage(a)ssz.com | | 512-451-7087 | |____________________________________________________________________|

1 0

Re: Can someone look this up? (fwd)
by John Young 17 Dec '03

17 Dec '03

>Can someone on the list look this up? > >*************************************************************** >If the government has no knowledge of aliens, then why does >Title 14, Section 1211 of the Code of Federal Regulations, >implemented on July 16, 1969, make it illegal for U.S. >citizens to have any contact with extraterrestrials or their >vehicles? Very SETI/UFO-mysterious. Here's what's listed (three times) at: http://www.access.gpo.gov/nara/cfr/index.html [Code of Federal Regulations] [Title 14, Volume 5, Parts 1200 to end] [Revised as of January 1, 1997] >From the U.S. Government Printing Office via GPO Access [CITE: 14CFR1211] [Page 75] TITLE 14--AERONAUTICS AND SPACE CHAPTER V--NATIONAL AERONAUTICS AND SPACE ADMINISTRATION PART 1211--[Reserved] ---------- That's the entire entry.

1 0

Re: EPR, Bell, and FTL Bandwidth (fwd)
by Jim Choate 17 Dec '03

17 Dec '03

Forwarded message: > From: Eric Cordian <emc(a)wire.insync.net> > Subject: Re: EPR, Bell, and FTL Bandwidth (fwd) > Date: Wed, 28 Jan 1998 15:53:28 -0600 (CST) > >> Someday in the future, I open my cookie, and instantly know what > >> Lucky will see when he opens his. > > > True, but your opening your cookie does not *force* Lucky to open his > > at the same time. This is one fault with this model. The 'state' of > > the cookies are not inter-dependant as the polarization of the photon > > pairs are. > > While it is true that my examining my cookie does not force Lucky to > examine his, the same can be said of a photon experiment, where the > photons can remain in flight for an arbitrary period of time before > being measured. Um, actualy no. Since the photons are coupled we know that the second photon has actualy changed it's polarization, either that or your original assumption they are coupled is not true. The polarization between the two photons *must* be zero. Otherwise you arent' playing with our physics. > The state of the cookies is highly correlated, since they have > opposite values. The polarization of the photon pairs is similarly > correlated, as they have equal values. Correlation is not a function of any quantity conservation operation. The values of the photons are actualy opposite and therefore sum to zero. Foo is not the inverse of Bar, as is the case for horizontal and vertical polarization. > > It isn't instantanous, the correlation existed when they were printed > > and doesn't change. > > And indeed in the photon case, the entanglement exists when two > photons with correlated wavefunctions are created. True, but the swap of polarization was *not*. That occured later and is what changes instantly irrespective of distance. > > If I destroy one of the cookies it doesn't destroy the other > > spontaneously as would happen in a correlated photon-pair. > > Nope. Destroying one of a pair of entangled photons does nothing to > the other. Yes, it causes the correlation to be destroyed. You are not taking into account the correllation or polarization dependency between the two photons. Our base assumption is that when photon A is horizontal then photon B is vertical. This *must* occur to preserve symmetry. [more stuff deleted] ____________________________________________________________________ | | | The most powerful passion in life is not love or hate, | | but the desire to edit somebody elses words. | | | | Sign in Ed Barsis' office | | | | _____ The Armadillo Group | | ,::////;::-. Austin, Tx. USA | | /:'///// ``::>/|/ http://www.ssz.com/ | | .', |||| `/( e\ | | -====~~mm-'`-```-mm --'- Jim Choate | | ravage(a)ssz.com | | 512-451-7087 | |____________________________________________________________________|

2 1

waisgate.cgi?WAISdocID=3424713596+1+0+0&WAISaction=retrieve
by Jim Choate 17 Dec '03

17 Dec '03

[Code of Federal Regulations] [Title 14, Volume 5, Parts 1200 to end] [Revised as of January 1, 1997] >From the U.S. Government Printing Office via GPO Access [CITE: 14CFR1211] [Page 75] TITLE 14--AERONAUTICS AND SPACE CHAPTER V--NATIONAL AERONAUTICS AND SPACE ADMINISTRATION PART 1211--[Reserved]

1 0

Can someone look this up? (fwd)
by Jim Choate 17 Dec '03

17 Dec '03

Forwarded message: > Date: Wed, 28 Jan 1998 19:16:36 -0500 (EST) > From: Ray Arachelian <sunder(a)sundernet.com> > Subject: Can someone look this up? (fwd) > ---------- Forwarded message ---------- > Date: Tue, 27 Jan 1998 21:48:14 -0500 > From: Salvatore Denaro <sal(a)panix.com> > To: 'Ray Arachelian' <sunder(a)brainlink.com> > Subject: Can someone look this up? > > Can someone on the list look this up? > > *************************************************************** > If the government has no knowledge of aliens, then why does > Title 14, Section 1211 of the Code of Federal Regulations, > implemented on July 16, 1969, make it illegal for U.S. > citizens to have any contact with extraterrestrials or their > vehicles? It is of some interest to note that in the movie 'Andromeda Strain' the code that trips Wildfire is a '1211'... ____________________________________________________________________ | | | The most powerful passion in life is not love or hate, | | but the desire to edit somebody elses words. | | | | Sign in Ed Barsis' office | | | | _____ The Armadillo Group | | ,::////;::-. Austin, Tx. USA | | /:'///// ``::>/|/ http://www.ssz.com/ | | .', |||| `/( e\ | | -====~~mm-'`-```-mm --'- Jim Choate | | ravage(a)ssz.com | | 512-451-7087 | |____________________________________________________________________|

1 0