Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1801.02602 · Notices of the American Mathematical Society

Three Puzzles on Mathematics, Computation, and Games

Gil Kalai

Published Jul 13, 2018• 4 citations
arXivHTMLPDF

Abstract

In this lecture I will talk about three mathematical puzzles involving mathematics and computation that have preoccupied me over the years. The first puzzle is to understand the amazing success of the simplex algorithm for linear programming. The second puzzle is about errors made when votes are counted during elections. The third puzzle is: are quantum computers possible?

DOI
10.1090/noti1696

Related papers

Game Theory: With Quantum Mechanics, Odds Are Always in Your Favor

Vladimir Silva

This chapter explores two game puzzles that show the remarkable power of quantum algorithms over their classical counterparts:

Apress eBooks•Jan 1, 2018•0 citations

Inclusive learning for quantum computing: supporting the aims of quantum literacy using the puzzle game Quantum Odyssey

Laurentiu Nita, Nicholas Chancellor, Laura Mazzoli Smith +2 more

With a vast domain of applications and now having quantum computing hardware available for commercial use, an education challenge arises in getting people of various background to become quantum literate. Quantum Odyssey is a new piece of computer software that promises to be a medium where people can learn quantum computing without any previous requirements. It aims to achieve this through visual cues and puzzle play, without requiring the user to possess a background in computer coding or even linear algebra, which are traditionally a must to work on quantum algorithms. In this paper we report our findings on an UKRI Citizen Science grant that involves using Quantum Odyssey to teach how to construct quantum computing algorithms. Sessions involved 30 minutes of play, with 10 groups of 5 students, ranging between 11 to 18 years old, in two schools in the UK. Results show the Quantum Odyssey visual methods are efficient in portraying counterintuitive quantum computational logic in a visual and interactive form. This enabled untrained participants to quickly grasp difficult concepts in an intuitive way and solve problems that are traditionally given today in Masters level courses in a mathematical form. The results also show an increased interest in quantum physics after play, a higher openness and curiosity to learn the mathematics behind computing on quantum systems. Participants developed a visual, rather than mathematical intuition, that enabled them to understand and correctly answer entry level technical quantum information science.

arXiv:2106.07077•Jun 13, 2021•24 citations

Game Theory: With Quantum Mechanics, Odds Are Always in Your Favor

Vladimir Silva

This chapter explores two game puzzles that show the remarkable power of quantum algorithms over their classical counterparts:

Apress eBooks•Dec 18, 2023•0 citations

Getting the public involved in Quantum Error Correction

James R. Wootton

The Decodoku project seeks to let users get hands-on with cutting-edge quantum research through a set of simple puzzle games. The design of these games is explicitly based on the problem of decoding qudit variants of surface codes. This problem is presented such that it can be tackled by players with no prior knowledge of quantum information theory, or any other high-level physics or mathematics. Methods devised by the players to solve the puzzles can then directly be incorporated into decoding algorithms for quantum computation. In this paper we give a brief overview of the novel decoding methods devised by players, and provide short postmortem for Decodoku v1.0-v4.1.

arXiv:1712.09649•Dec 27, 2017•16 citations

Contemplating quantum computation

D. Mermin

People with surprisingly diverse points of view see quantum computation as vindicating their pet idea of what quantum mechanics is all about. The present speaker is no exception. In this introductory talk I shall describe a few elementary quantum algorithms with a view to revealing their intrinsic charm, and illustrating this blind-men-and-the-elephant aspect of that charm.

Optical Fiber Communication Conference•Jan 1, 2001•0 citations

The complexity of joint computation

Scott Aaronson, Andrew Drucker

Joint computation is the ubiquitous scenario in which a computer is presented with not one, but many computational tasks to perform.A fundamental question arises: when can we cleverly combine computations, to perform them with greater efficiency or reliability than by tackling them separately?This thesis investigates the power and, especially, the limits of efficient joint computation, in several computational models: query algorithms, circuits, and Turing machines.We significantly improve and extend past results on limits to efficient joint computation for multiple independent tasks; identify barriers to progress towards better circuit lower bounds for multiple-output operators; and begin an original line of inquiry into the complexity of joint computation.In more detail, we make contributions in the following areas:Improved direct product theorems for randomized query complexity: The "direct product problem" seeks to understand how the difficulty of computing a function on each of k independent inputs scales with k.We prove the following direct product theorem (DPT) for query complexity: if every T-query algorithm has success probability at most 1-e in computing the Boolean function f on input distribution p, then for a < 1, every aeTk-query algorithm has success probability at most (2 6(1 -E)) in computing the k-fold direct product f k correctly on k independent inputs from p.In light of examples due to Shaltiel, this statement gives an essentially optimal tradeoff between the query bound and the error probability.Using this DPT, we show that for an absolute constant a > 0, the worst-case success probability of any aR 2 (f)k-query randomized algorithm for f k falls exponentially with k.The best previous statement of this type, due to Klauck, Spalek, and de Wolf, required a query bound of O(bs(f)k).Our proof technique involves defining and analyzing a collection of martingales associated with an algorithm attempting to solve f*k.Our method is quite general This thesis was a long time in the making, and accordingly is indebted to many people.First of all, I would like to thank my advisor, Scott Aaronson, for the innumerable forms of support he has shown me over the years it's been my privilege to know him.Scott has always treated me as a colleague and an equal.He has always enthusiastically invited me to explore the many wonderful ideas that have excited him over the years, and has taught me a huge amount about computational complexity and allied fields.At the same time he has placed faith in me to plot my own course of research.My collaborations with Ronald de Wolf were in many ways akin to a second advisorship.In addition to sharing his scientific expertise, he generously shared his time to help me develop as a writer and editor.His formidable skills and work ethic have served as a model for me ever since.I am grateful to Russell Impagliazzo for his kind support and guidance during my first year of graduate study at UC San Diego.I thank Michael Sipser and Scott Aaronson for each giving me valuable teaching opportunities at MIT, and for leading by example with their own inspiring teaching.Fellow students have supported me and taught me a great deal over the years.Their guidance has come in many forms-from mathematical discussions, to practical advice about school and life.(I regard many of these talented individuals more as role models than as peers.)I have also valued their friendship and camaraderie through the academic process.A very partial list of fellow students who've given me valuable support and advice includes:

•Jan 1, 2012•3 citations
In this lecture I will talk about three mathematical puzzles involving mathematics and computation that have preoccupied me over the years. The first puzzle is to understand the amazing success of the simplex algorithm for linear programming. The second puzzle is about errors made when votes are counted during elections. The third puzzle is: are quantum computers possible?
With a vast domain of applications and now having quantum computing hardware available for commercial use, an education challenge arises in getting people of various background to become quantum literate. Quantum Odyssey is a new piece of computer software that promises to be a medium where people can learn quantum computing without any previous requirements. It aims to achieve this through visual cues and puzzle play, without requiring the user to possess a background in computer coding or even linear algebra, which are traditionally a must to work on quantum algorithms. In this paper we report our findings on an UKRI Citizen Science grant that involves using Quantum Odyssey to teach how to construct quantum computing algorithms. Sessions involved 30 minutes of play, with 10 groups of 5 students, ranging between 11 to 18 years old, in two schools in the UK. Results show the Quantum Odyssey visual methods are efficient in portraying counterintuitive quantum computational logic in a visual and interactive form. This enabled untrained participants to quickly grasp difficult concepts in an intuitive way and solve problems that are traditionally given today in Masters level courses in a mathematical form. The results also show an increased interest in quantum physics after play, a higher openness and curiosity to learn the mathematics behind computing on quantum systems. Participants developed a visual, rather than mathematical intuition, that enabled them to understand and correctly answer entry level technical quantum information science.
The Decodoku project seeks to let users get hands-on with cutting-edge quantum research through a set of simple puzzle games. The design of these games is explicitly based on the problem of decoding qudit variants of surface codes. This problem is presented such that it can be tackled by players with no prior knowledge of quantum information theory, or any other high-level physics or mathematics. Methods devised by the players to solve the puzzles can then directly be incorporated into decoding algorithms for quantum computation. In this paper we give a brief overview of the novel decoding methods devised by players, and provide short postmortem for Decodoku v1.0-v4.1.
Joint computation is the ubiquitous scenario in which a computer is presented with not one, but many computational tasks to perform.A fundamental question arises: when can we cleverly combine computations, to perform them with greater efficiency or reliability than by tackling them separately?This thesis investigates the power and, especially, the limits of efficient joint computation, in several computational models: query algorithms, circuits, and Turing machines.We significantly improve and extend past results on limits to efficient joint computation for multiple independent tasks; identify barriers to progress towards better circuit lower bounds for multiple-output operators; and begin an original line of inquiry into the complexity of joint computation.In more detail, we make contributions in the following areas:Improved direct product theorems for randomized query complexity: The "direct product problem" seeks to understand how the difficulty of computing a function on each of k independent inputs scales with k.We prove the following direct product theorem (DPT) for query complexity: if every T-query algorithm has success probability at most 1-e in computing the Boolean function f on input distribution p, then for a < 1, every aeTk-query algorithm has success probability at most (2 6(1 -E)) in computing the k-fold direct product f k correctly on k independent inputs from p.In light of examples due to Shaltiel, this statement gives an essentially optimal tradeoff between the query bound and the error probability.Using this DPT, we show that for an absolute constant a > 0, the worst-case success probability of any aR 2 (f)k-query randomized algorithm for f k falls exponentially with k.The best previous statement of this type, due to Klauck, Spalek, and de Wolf, required a query bound of O(bs(f)k).Our proof technique involves defining and analyzing a collection of martingales associated with an algorithm attempting to solve f*k.Our method is quite general This thesis was a long time in the making, and accordingly is indebted to many people.First of all, I would like to thank my advisor, Scott Aaronson, for the innumerable forms of support he has shown me over the years it's been my privilege to know him.Scott has always treated me as a colleague and an equal.He has always enthusiastically invited me to explore the many wonderful ideas that have excited him over the years, and has taught me a huge amount about computational complexity and allied fields.At the same time he has placed faith in me to plot my own course of research.My collaborations with Ronald de Wolf were in many ways akin to a second advisorship.In addition to sharing his scientific expertise, he generously shared his time to help me develop as a writer and editor.His formidable skills and work ethic have served as a model for me ever since.I am grateful to Russell Impagliazzo for his kind support and guidance during my first year of graduate study at UC San Diego.I thank Michael Sipser and Scott Aaronson for each giving me valuable teaching opportunities at MIT, and for leading by example with their own inspiring teaching.Fellow students have supported me and taught me a great deal over the years.Their guidance has come in many forms-from mathematical discussions, to practical advice about school and life.(I regard many of these talented individuals more as role models than as peers.)I have also valued their friendship and camaraderie through the academic process.A very partial list of fellow students who've given me valuable support and advice includes: