1	The Tunneling Salesman Olly Downs Princeton University & Analytical Insights, Inc http://olly.downs.net http://www.analyticalinsights.com
2	Overview Global Optimization using QM Quantum Dynamics for Optimization Quantum Mathematics 1d and 2d Visual Examples Efficient N-dimensional Optimization Tricks from Quantum Mathematics How to truncate the set of basis functions ‘Hard’ Problems and Polynomial Cost Functions Classical vs. Quantum Factoring bi-primes Conclusions and ongoing work
3	QM for Global Optimization Model–based learning problems typically optimization of cost function on model parameters Motivated by binary combinatorial optimization problems, represented as smooth (polynomial) cost functions State of the art for general global optimization is still simulated annealing Physical analogy to a classical thermally excited particle Novel: Take physical analogy with quantum particle
4	Quantum Dynamics Key distinction between classical and quantum is the tunneling phenomenon Tunneling – particle of energy E can penetrate barriers with energy, V >E
5	Quantum Dynamics 1-dimensional tunnelling (Burges & Downs) Painfully hard to integrate Schrödinger equation forward in time Simulating Quantum dynamics not efficient strategy for global optimization algorithm
6	Summary Global Optimization using QM Quantum Dynamics for Optimization Quantum Mathematics 1d and 2d Visual Examples Efficient N-dimensional Optimization Tricks from Quantum Mathematics How to truncate the set of basis functions ‘Hard’ Problems and Polynomial Cost Functions Classical vs. Quantum Factoring bi-primes Conclusions and ongoing work
7	Quantum Mathematics In classical mechanics particle is specified by velocity and position In QM particle is fully described by wavefunction, y(x,t) such that Dynamics are described by the Schrödinger Eqn.
8	Quantum Mathematics Solution by separating variables gives spatial eigenfunction equation Ladder of discrete eigenvalues are particle energies associated with the eigenfunctions Eigenfunctions are orthonormal, and describe a complete basis For quadratic V (harmonic oscillator)
9	Quantum Mathematics Key Theorem: For large enough mass, the lowest energy eigenfunction is localised to the global min. of the potential Solutions of Schrödinger for general V_full are intractable Approximate solutions for polynomial V_full Expand potential as V_full=V_simple+V_perturb Using completeness, expand eigenfunctions in terms of those of V_simple To approximate lowest energy eigenstate, choose a_i to minimise energy expectation
10	Quantum Mathematics Using V_simple= local quadratic approx (Harmonic Oscillator) this is tractable for any polynomial V_full Approximation Summary
11	Summary Global Optimization using QM Quantum Dynamics for Optimization Quantum Mathematics 1d and 2d Visual Examples Efficient N-dimensional Optimization Tricks from Quantum Mathematics How to truncate the set of basis functions ‘Hard’ Problems and Polynomial Cost Functions Classical vs. Quantum Factoring bi-primes Conclusions and ongoing work
12	Approximate Eigenfunctions
13	Approximate Eigenfunctions
14	Approx. Groundstate
15	Sanity Check!
16	2 dimensions In 2d we consider the 4-minimum. quartic potential
17	2 dimensions
18	2 dimensions
19	Summary Global Optimization using QM Quantum Dynamics for Optimization Quantum Mathematics 1d and 2d Visual Examples Efficient N-dimensional Optimization Tricks from Quantum Mathematics How to truncate the set of basis functions ‘Hard’ Problems and Polynomial Cost Functions Classical vs. Quantum Factoring bi-primes Conclusions and ongoing work
20	Extend this to N-dimensions Compute or set Hessian of V_simple at local minimum Change coordinates to the eigenbasis of the Hessian In eigenbasis the HO eigenfunctions factorize We evaluate matrix elements using products of the 1d HO ladder operators, and orthogonality
21	Choice of the HO Basis functions Consider problems with solutions of interest at vertices of binary hypercube Origin at centre of cube, then choose ‘width’ of Gaussian factor in HO basis functions to span the binary cube ħ becomes a parameter which is chosen to facilitate the large-mass limit and to accommodate the size of the hypercube
22	Which basis functions? Assuming problems on the binary hypercube, consider case of global min. at opposite diagonal, and in direction of largest eigenvalue of Hessian at local min. Place Gaussian of width equal to HO groundstate of local min., in global min. Compute overlap integrals between local min HO eigenstates and Gaussian.
23	Which basis functions? This gives a Poisson distribution with parameter a² over the overlap integral of the nth state
24	Which basis functions? Empirically, the representations are sparse in the significantly used basis functions (a) We might consider selecting functions which have low energy under the full Hamiltonian (b)
25	Summary Global Optimization using QM Quantum Dynamics for Optimization Quantum Mathematics 1d and 2d Visual Examples Efficient N-dimensional Optimization Tricks from Quantum Mathematics How to truncate the set of basis functions ‘Hard’ Problems and Polynomial Cost Functions Classical vs. Quantum Factoring bi-primes Conclusions and ongoing work
26	‘Hard’ Problems & Polynomial Potentials Finding the global minimum of an N-d quartic polynomial is NP-hard (Bellare et. al., 1993) Specific problems Factoring (Burges & Downs) Travelling Salesman (Downs & Attias) Polynomial potentials well suited to current approach since we can express polynomial terms as products of powers of operators
27	Classical vs. Quantum Why can’t we use the Diffusion equation? For Harmonic Oscillator potential Schrödinger and Diffusion are isomorphic
28	Classical vs. Quantum Similar matrix diagonalization problem to approximate ground state Integrating Factor transformation to convert diffusion operator to self-adjoint form Self-adjoint version of Diffusion operator is no-longer polynomial in V Cannot use harmonic oscillator ladder operator tricks No direct classical equivalent to Tunneling Salesman
29	Summary Global Optimization using QM Quantum Dynamics for Optimization Quantum Mathematics 1d and 2d Visual Examples Efficient N-dimensional Optimization Tricks from Quantum Mathematics How to truncate the set of basis functions ‘Hard’ Problems and Polynomial Cost Functions Classical vs. Quantum Factoring bi-primes Conclusions and ongoing work
30	Modest Results with Factoring Currently employ naïve cost function Toys: biprimes 6, 35, 143, 899 & 1073 Successful obtaining prime factors - 1073 compute time ~6 hours!
31	Summary Global Optimization using QM Quantum Dynamics for Optimization Quantum Mathematics 1d and 2d Visual Examples Efficient N-dimensional Optimization Tricks from Quantum Mathematics How to truncate the set of basis functions ‘Hard’ Problems and Polynomial Cost Functions Factoring bi-primes Conclusions and ongoing work
32	Conclusions Simple, novel approach to Optimization Made tractable by HO operator tricks, and Quantum intuition Complexity controlled by choice of basis functions (useful when sub-exponential?) Analogous mathematics do not transfer to Diffusion Equation Use Quantum Field Theory to model multiple non-interacting particles Patent Pending
33	Acknowledgements John Hopfield David Heckerman Chris Burges Robert Rounthwaite Machine Learning & Applied Statistics Group @ MS Research Microsoft Research Graduate Fellowship Jeanette Downs
34	For Info. Materials… Email: tunneling@analyticalinsights.com