The initialization time for setting up the experiment grows exponential with the number of cities. Therefore the overall time required to solve the problem is not quadratic but exponential.
© 2007 Optical Society of America
In  we claimed that the proposed gedankenexperiment will find the global solution of a traveling salesman problem (TSP) in quadratic time. That means the time required to solve the TSP increases quadratic with the number of cities N. Our analysis was based on the number of measurements needed to determine the minimum path.
However we did not consider in this estimation that the first measurement only can start after the light has passed through the network. Since the delays for our chosen labeling scheme (Eq. 1 in ) were chosen to be ∼ 2i for city i we have an exponential increase of the overall path length for the light to travel. Therefore the initialization time required before the measurements really can start also increases exponentially with N. That is we have an increase in the initialization time of O(2N). This is considerably lower than the original cost of O(N!) ∼ O(NN) and from a practical point of view this initialization cost is low (due to the high speed of photons) for small problems. Nevertheless the chosen delay settings won’t lead to an overall reduction to quadratic time. This important fact has to be considered.
Additionally two readers pointed us to related publications that we want to reference here [2, 3, 4]. Most important is the work of M. Oltean who solved another NP-complete problem, the Hamiltonian path problem, by light [2, 3]. The core idea to use optical path lengths for coding/labeling the different problems is the same. Whereas we proposed an interferometric approach his technique is based on short pulses of light and incoherent detection. We appreciate his very interesting conference publication.
References and links
2. M. Oltean, “A light-based device for solving the Hamiltonian path problem,” in Lecture Notes in Computer Science 4135, 217–227, Springer (2006). [CrossRef]
3. M. Oltean, “Solving the Hamiltonian path problem with a light-based computer,” Natural Computing, to appear in Vol. 6, Issue 4, 2007.
4. S. Dolev and H. Fitoussi, “The traveling beams optical solutions for bounded NP-Complete problems,” in Lecture Notes in Computer Science 4475, 120–134 (2007). [CrossRef]