h a l f b a k e r y
0.5 and holding.

meta:

account: browse anonymously, or get an account and write.

 user: pass:
register,

# Quantum Salesman

Real world instantiation of the Travelling Salesman Problem using quantum superposition to traverse all paths at once
 (+3, -3) [vote for, against]

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.

 — hennessey, Mar 05 2009

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]

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.
 — eight_nine_tortoise, Mar 05 2009

I would much prefer this to have been a Salesman selling you quanta. One Higgs Boson please!
 — eight_nine_tortoise, Mar 05 2009

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?
 — hennessey, Mar 05 2009

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.
 — zen_tom, Mar 05 2009

// the supposition of probability waves//
Does that imply that an FFT of the probability waves would give you an answer even faster?
 — coprocephalous, Mar 05 2009

 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.
 — zen_tom, Mar 05 2009

Since you will need a discrete cable for each discrete combined path, it'd be faster to do it with a ball of string.
 — FlyingToaster, Mar 05 2009

 //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.
 — zeno, Mar 05 2009

 [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.
 — hennessey, Mar 05 2009

We really need some sort of CERN-halfbakery interface. I feel it would benefit us both.
 — wagster, Mar 05 2009

 /// //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.
 — colorclocks, Mar 05 2009

 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, Mar 05 2009

[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.
 — hennessey, Mar 05 2009

 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.
 — zen_tom, Mar 05 2009

[colourclocks] yes... nice set up of the problem.
 — hennessey, Mar 05 2009

[+]
 — sninctown, Mar 06 2009

 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.
 — zeno, Mar 07 2009

 // 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.
 — 8th of 7, May 06 2016

 //will there be anything you can measure that indicates the shortest (or longest) path it traversed//

 Yes.

 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.
 — MaxwellBuchanan, May 06 2016

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.
 — WcW, May 16 2016

But then it won't do that quantum boogie.
 — MaxwellBuchanan, May 16 2016

back: main index