- Friday, 30 May 2008
A report discusses an algorithm for a new kind of dynamics based on a quantum-classical hybrid-quantum-inspired maximizer. The model is represented by a modified Madelung equation in which the quantum potential is replaced by different, specially chosen “computational” potential. As a result, the dynamics attains both quantum and classical properties: it preserves superposition and entanglement of random solutions, while allowing one to measure its state variables, using classical methods. Such optimal combination of characteristics is a perfect match for quantum-inspired computing. As an application, an algorithm for global maximum of an arbitrary integrable function is proposed. The idea of the proposed algorithm is very simple: based upon the Quantum-inspired Maximizer (QIM), introduce a positive function to be maximized as the probability density to which the solution is attracted. Then the larger value of this function will have the higher probability to appear.
Special attention is paid to simulation of integer programming and NP- complete problems. It is demonstrated that the problem of global maximum of an integrable function can be found in polynomial time by using the proposed quantum-classical hybrid. The result is extended to a constrained maximum with applications to integer programming and TSP (Traveling Salesman Problem).
This work was done by Michail Zak of Caltech for NASA’s Jet Propulsion Laboratory.
This Brief includes a Technical Support Package (TSP).
Quantum-Inspired Maximizer (reference NPO-45458) is currently available for download from the TSP library.
Please Login at the top of the page to download.