h a l f b a k e r yRight twice a day.
add, search, annotate, link, view, overview, recent, by name, random
news, help, about, links, report a problem
browse anonymously,
or get an account
and write.
register,
|
|
|
Quantum Salesman
Real world instantiation of the Travelling Salesman Problem using quantum superposition to traverse all paths at once | |
Take a piece of card, punch 2 holes in it. Fire photons
(or
electrons or whatever is handy) at it and lo and behold
they will each go through both holes, forming an
interference pattern on the screen that you've placed
behind your card. Really they will.
OK, so repeat this with a Y-shaped
optic fibre that splits
into 2 (you get me?). The photon will start at the bottom
of the "Y" and go down each path, exiting the top end
and
interfering with itself. It will appear on the screen in a
position which is related to the probabilities set up by
the
interference pattern above. Right, nothing new yet.
Briefly consider the travelling salesman problem (TSP): n
cities, fully connected, different path lengths between
cities. Problem is can you find the shortest route which
takes in all the cities without repeating any? This
problem
grows very quickly in complexity (i.e. number of possible
paths) with respect to the number of cities. Indeed it's
NP
(Complete?) and it's hard to answer for large numbers
(20?
) of cities.
OK back to the fibre optics and finally the actual idea.
Set
up optic fibres with lengths that represent the path
lengths in your problem. To the top ends of your "Y" you
add more optic fibres, each splitting into 2, with again
the
lengths representing the TSP. Repeat 'till you have your
problem represented. This won't get you exactly the TSP
because there are certain restrictions on where the
photons can go (i.e. they can't return down a path
towards
your light source and away from the screen) but in
general
this doesn't matter. It's basically the same problem - i.e
the number of possible paths grows very quickly as you
bolt fibre optic cables together.
Now fire a photon at your spaghetti of cables. It will
necessarily traverse *all possible paths* in your tangle.
When it exits and you measure it... here's where i run
out
of steam due to ignorance: will there be anything you
can
measure that indicates the shortest (or longest) path it
traversed, thereby solving the TSP; not explicitly giving
you
the path, but giving you the shortest path length)? It's
not
a "wouldn't it be nice if", it's more a question. I rather
thought that there might be uncertainty in the arrival
time
which was some function of the difference in path
lengths
(since no measurement you can do will determine which
path the photon "really" travelled down) and one could
use
this uncertainty as a bound on the possible path lengths.
Quantum Computing
http://en.wikipedia...ki/Quantum_computer
[hennessey] I could be wrong, but I'm pretty sure this is what you are talking about. [zen_tom, Mar 05 2009]
Reminds me of this: finding the shortest path with gas discharge
http://www.imajeeny...st_path/index.shtml
[notexactly, May 15 2016]
Please log in.
If you're not logged in,
you can see what this page
looks like, but you will
not be able to add anything.
Annotation:
|
| |
I am fairly sure this would not work. But like you I out of steam due to lack of brain power. Oh the human condition. |
|
| |
I would much prefer this to have been a Salesman selling you quanta. One Higgs Boson please! |
|
| |
Umm... that's a little err... i'm struggling for a word
that doesn't sound churlish... unfair? I mean, i'm
basically with you, the odds are it won't work, but
why Mr Tortoise, why? |
|
| |
This is kind of what quantum computing is supposed to be all about, the supposition of probability waves can be (theoretically) set up so that a single answer can be determined instantaneously - at least I think that's how it's supposed to work. |
|
| |
// the supposition of probability waves//
Does that imply that an FFT of the probability waves would give you an answer even faster? |
|
| |
My maths doesn't know the slightest thing about FFTs (I wish it did) - so no, I've no idea. |
|
| |
How fast is a Fast Fourier Transformation anyway? I bet it's not instantaneous, which is pretty fast, as fast goes. |
|
| |
Since you will need a discrete cable for each discrete combined path, it'd be faster to do it with a ball of string. |
|
| |
//Really they will\\ No they won't, it only looks like they do and you can't prove it. |
|
| |
//Y-shaped optic fibre\\ Unlikely to react the same as holes but could be true |
|
| |
//add more optic fibres\\ I knew you would go there. Send one electron through an optic fibre. Make it y shaped and two electrons come out. (or at least the effect of two electrons) Add more and pretty soon we get millions of electrons (or the effect of millions of electrons) from one at the start. This violates pretty much all natural laws. |
|
| |
[FlyingToaster] I think you make a fair point - this
is borne of my attempting to make things clearer
by using fibre optics. Let's forget them, and just
use slits. Then your (valid) objection is no longer a
problem (though this may raise other objections) |
|
| |
[Zeno] you make a internally inconsistent
statement: "no they don't" and "You can't prove
it". You, of course, can't 'prove' they don't, and
you're up against some incredibly well established
experimental evidence with your belief. I hardly
want to get into a discussion of whether the basic
tenets of QM are true or not, but this is taken to
be what happens by everyone in the field. |
|
| |
OK to some of your more interesting points
[zeno]: Y shaped optic fibres - //unlikely to react
the same// fair point - but why? what's the
difference? It's just a medium through which the
photon is travelling, admittedly with some total
internal reflection caper roughing things up. |
|
| |
Last point: We don't get millions and millions of
electrons. We get one in one out. It's just that
the best way of describing its propagation from
source to screen (indeed the only way which is
consistent with the facts) is that it has travelled
though every path. As i'm sure you know (forgive
me) it's not a ball of matter as we think of it. No
"natural laws" have been violated by the premise
at least. |
|
| |
We really need some sort of CERN-halfbakery interface. I feel it would benefit us both. |
|
| |
/// //Y-shaped optic fibre\\ Unlikely to react the
same \\\
There are fiber optic interferometers, so the
fiber/hole thing is not a problem. But holes are
better than fibers for implementing this
calculation anyway, so I think this question is
moot. |
|
| |
If the cities are restricted to lie on a 2D surface
(lucky for us, they are!), then the calculation can
be implemented very easily: |
|
| |
Take N copies of a map.
Poke holes in all N cities.
Stack the maps on a horizontal surface.
Separate the maps vertically by some fixed
distance.
Shine coherent light from the top.
Measure at the bottom. |
|
| |
The vertical separation distance doesn't matter
because all you need is the *ordering* of city visits
that minimizes the total distance traveled.
Adding fixed separations doesn't change the
ordering of the best route. |
|
| |
I have no idea how to interpret the diffraction
pattern to get a solution. I think it would be very
hard to do. But I think there's no question that
the solution is in the diffraction pattern. |
|
| |
If I'm getting this description right, the idea is to compare two lengths of cable by shooting a photon down them and measure where it comes out first. |
|
| |
That is possible, but has nothing to do with quantum computing, wave/particle duality, or interference patterns, and other ways of comparing the lengths of things have been devised. (E.g., holding them next to each other and looking at them.) |
|
| |
[jutta], the photon will really travel down all
possible paths, so it's not about measuring
individual path lengths (which as you point out, is
rather easy) but about the combination of
possible path lengths to get to the screen, which
is deceptively complex (see TSP in general). The
problem may be the counter-intutive-ness?? of
quantum events, or it may be rather more prosaic:
namely the limits of my description here. But
really, this does live or die on whether you can
"get the solution out of the diffraction pattern" as
[colourclocks] says. Hence I don't think your
description accurately characterises what's going
on. |
|
| |
If the idea is to solve the travelling salesman problem using similar phenomena as found in the twin-slit experiment, then yes, it does fall within the realm of quantum computing - the point of quantum computing being that "tricky" (NP type) problems will become solvable as if they were simple (P) problems through quantum phenomena. |
|
| |
The way this is theorised as being implemented is through simultaneous supposition of quantum states, the same way the twin-slit experiment (or variations thereof) provides instantaneous results. The idea as described sounds like an implementation method for putting together a quantum computer, albeit a naive one - the supposition of all electon/photon path probabilities, given that all probabilities are offered as optional routes, should result in the 'best' or 'shortest' result being produced experimentally. |
|
| |
[colourclocks] yes... nice set up of the problem. |
|
| |
The thing is, I said you can't prove it because when you look at the outcome it certainly seems they went through both holes. But when you actuallt try to measure right at the the hole itself, it doesn't work anymore. That's quantum for you I guess. |
|
| |
/We get one in one out\ No you don't. in your first example you get one in, a wavey pattern out, that suggests these particles sometimes perform as particle, sometimes as wave. |
|
| |
As cought in a system of y shaped fibres you will find they will no longer have the freedom to function as a wave form. So one in one out yes. One in wave form out no. So one in millions out no. |
|
| |
// I suppose you could insert a banana if you like // |
|
| |
We were initially going to ask "Where ?", but on consideration that's a question we almost certainly don't want an answer to. |
|
| |
//will there be anything you can measure that
indicates the shortest (or longest) path it
traversed// |
|
| |
First, make the length of each fibre proportional
to the actual distance between the towns it joins
(obviously). If necessary, add or subtract very
small amounts from some of the lengths, so that
they are all different. |
|
| |
Now your photon will arrive at the output smeared
over a finite period of time, corresponding to the
time delays of all the different paths it took to get
there. The photon detector will of course collapse
this into a single arrival time. If you measure a lot
of arrival times, and find the "commonest" arrival
time, you will know the physical distance of the
shortest path and, if the fibre lengths were
tweaked correctly, this will uniquely identify the
series of fibres travelled along. |
|
| |
There is one problem with this idea, though. The
real travelling salesman problem stipulates that he
should only visit each town once. If there is a
shortest route that visits some towns twice or
more, that's the answer this system will give you. |
|
| |
Precisely. We cannot tell if the photon has visited all of the cities, or if it has visited any of them more than once. We can pretty much assume that the, average photon has met neither condition. |
|
| |
But then it won't do that quantum boogie. |
|
| |