Presentation
How Pupils Solved the n-Queens Problem on a D-Wave System
Speaker
Event Type
Focus Session
Quantum Computing
TimeWednesday, June 19th11:20am - 11:45am
LocationPanorama 1
DescriptionEight chess queens must be placed on a chessboard so that no two queens threaten each other. The general form of this well-known problem (n queens on an n × n board) was solves on a D-Wave quantum annealer by three schoolboys (age 14, 15 and 16) from the high school of the "Regensburger Domspatzen". Their project won the first price at a regional youth science competition (Jugend forscht 2019).
As the supervisor of the three boys I will explain what it took to teach the boys how to use a D-Wave quantum annealer, how much knowledge of quantum physics was necessary and what the pupils had to know about formulating a mathematical puzzle as a quadratic unconstrained binary optimization (QUBO) problem.
With this knowledge my students could develop an energy function for the n-queens problem on their own. Their function returns a value for every constellation from zero up to n × n queens on a n × n chessboard. The global minima of this function represent the solutions of the n-queens problem. Once the problem was well-matched to the hard-wired design of the quantum annealer chip of a D-Wave 2000Q system, the n-queen problem was solved really, really fast...
Details of the solving algorithm and how to determine the energy function for this problem will be explained by my students live on stage.
As the supervisor of the three boys I will explain what it took to teach the boys how to use a D-Wave quantum annealer, how much knowledge of quantum physics was necessary and what the pupils had to know about formulating a mathematical puzzle as a quadratic unconstrained binary optimization (QUBO) problem.
With this knowledge my students could develop an energy function for the n-queens problem on their own. Their function returns a value for every constellation from zero up to n × n queens on a n × n chessboard. The global minima of this function represent the solutions of the n-queens problem. Once the problem was well-matched to the hard-wired design of the quantum annealer chip of a D-Wave 2000Q system, the n-queen problem was solved really, really fast...
Details of the solving algorithm and how to determine the energy function for this problem will be explained by my students live on stage.
Speaker
