[RC5] More on Quantum Computing and Crypto

Greg Hewgill greg at hewgill.com
Fri May 21 00:30:22 EDT 1999

On Wed, May 19, 1999 at 09:22:42AM -0700, Adam Zilinskas wrote:
> If you could pull the web off the wall and label all end points and 
>  each strand, the longest distance between two points is found by holding 
>  each start/end point and carefully pulling them apart, if you
>  break a strand but leave another path intact, you keep pulling. The moment
>  you cannot pull any further without seperating the start and end point,
>  that is the longest path.

I'm not sure this is a perfect analogy. Consider the following small fragment
of your conceptual spider web (please excuse the ascii art):

  A      B       C      D
         |       |

That is, a taut connection between ABCD with a loop of web dangling from B and
C. While there is a wasy for this to break (at the short path between B and C)
to produce the longest connecting path, this will not be the case in general.
All other things being equal, there is a probability 1/3 that the short BC
connection will break first, rather than AB or CD. Of course, if AB or CD
breaks, then this web fragment becomes disconnected and is disqualified.

I think that at best, you could come up with a probability that the last
connected path is really the longest path.

If this were a quantum problem, then the web would not actually break until it
were observed. Unfortunately, I think tugging on the A and D ends of the web
above would count as observation because the elasticity of the remaining
connected web (if any) would exert a reactive force on the tugging, which could
be measured.

Greg Hewgill

To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list