Learning From Examples Using Quantum Annealing (Google Workshop on Quantum Biology)

Google Workshop on Quantum Biology Learning from Examples Using Quantum Annealing Presented by Hartmut Neven October 22, 2010 ABSTRACT The ability to learn from examples is a quintessential feature of higher intelligence. Machine learning theory shows how to formulate this task in terms of optimization problems. In their native format learning problems tend to be formally NP-hard. Therefore, in order to arrive at an efficiently solvable learning problem, relaxations need to be made. But recent advances in quantum computing, in particular in adiabatic quantum optimization, have shown how quantum resources can be employed to obtain solutions to hard optimization problems that are of higher quality than available classically. Hence, it is an interesting question whether an advantage can be gained by applying adiabatic quantum optimization to problems arising in learning. In particular we studied non-convex formulations of learning problems arising from non-convex loss functions, Gestalt constraints or L0-norm regularization. We will present results from numerical studies as well as from applying an adiabatic quantum chip manufactured by D-Wave. About the speaker: http://en.wikipedia.org/wiki/Hartmut_Neven