International Joint Conference On Theoretical Computer Science – Frontier of Algorithmic Wisdom

August 15-19, 2022, City University of Hong Kong, Hong Kong

 

Invited Speakers

Quantum Computing


Winning Mastermind Overwhelmingly on Quantum Computers

Lvzhou Li

Sun Yat-Sen University

Abstract:
From the 1970s up to now, Mastermind, a classic two-player game, has attracted plenty of attention, not only from the public as a popular game, but also from the academic community as a scientific issue. Mastermind with n positions and k colors is formally described as: the codemaker privately chooses a secret s∈[k]^n, and the coderbreaker want to determine s in as few queries like f_s (x) as possible to the codemaker, where f_s (x) indicates how x is close to s. The complexity of a strategy is measured by the number of queries used. In this work we have a systematic study on quantum strategies for playing Mastermind, obtaining a complete characterization of the quantum complexity and constructing optimal quantum algorithms in both non-adaptive and adaptive settings. Our results show that the codebreaker wins greatly more on quantum computers than on classical computers, since he can win the game with superexponentially less queries. Some other interesting differences between quantum and classical strategies have also been revealed for Mastermind.

Bio:
Lvzhou Li is currently a professor at the Institute of Quantum Computing and Computer Theory from Sun Yat-Sen University, Deputy Director of the CCF Quantum Computing Professional Group, and CCF Distinguished Member. From the perspective of computer science, he conducts research on quantum computing models, quantum algorithms and complexity, quantum machine learning, quantum compilation and optimization, etc.