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

Three Puzzles on Mathematics, Computation, and Games

Gil Kalai

Published Jan 8, 2018• 2 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.48550/arxiv.1801.02602

Related papers

Three Puzzles on Mathematics, Computation, and Games

Gil Kalai

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?

Notices of the American Mathematical Society•Jul 13, 2018•3 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•9 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•Jan 1, 2018•0 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

Quantum Game Semantics

Marc de Visme

In this thesis, we study quantum programming languages, and focus on the quantum lambda-calculus, a paradigmatic language defined by Selinger and Valiron, which mixes a rich classical control flow (higher order functions, etc.) and quantum data (qubit creation, measure, and unitary operations). In this thesis, we search for a denotational semantics of this language, in other words, we extract the meaning and behaviour of programs by interpreting them in an adequately chosen mathematical universe. In order to model the quantum lambda-calculus, one must adapt the traditional denotational models to the mathematics of quantum computation (Hilbert spaces, density matrices, etc.). We have three main contributions:Firstly, we extend game semantics to the quantum case. Game semantics is a dynamic approach to denotational semantics, which focuses on the sequence of interactions between a program and its environment. We obtain the first denotational model of the full quantum lambda-calculus which is both compositional and interactive, meaning that it represents the dynamic of the execution. Our model generalise the recently developed model for the probabilistic case.Secondly, we formally link our model to the only pre-existing denotational model of the full lambda-calculus, the quantum relational model of Pagani, Selinger and Valiron.Lastly, we prove that our game model is fully abstract, the gold standard of denotational semantics, which ensures a total correspondence between the programming language and the model. We deduce that the quantum relational model was also fully abstract, which was an open problem.This thesis is constituted of three parts. The first part details some preliminaries on category theory, used for defining a formal framework including both the quantum game model and the quantum relational model, some preliminaries on the mathematics of quantum computation, and then some preliminaries on quantum programming and its models. The second part starts with some preliminaries on game semantics and defines our quantum game model in the simplified case of the linear quantum lambda-calculus. The third part builds on the second part to define the full quantum game model, prove its full abstraction, and deduce that the quantum relational model is fully abstract too.

•Sep 28, 2020•0 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
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.
In this thesis, we study quantum programming languages, and focus on the quantum lambda-calculus, a paradigmatic language defined by Selinger and Valiron, which mixes a rich classical control flow (higher order functions, etc.) and quantum data (qubit creation, measure, and unitary operations). In this thesis, we search for a denotational semantics of this language, in other words, we extract the meaning and behaviour of programs by interpreting them in an adequately chosen mathematical universe. In order to model the quantum lambda-calculus, one must adapt the traditional denotational models to the mathematics of quantum computation (Hilbert spaces, density matrices, etc.). We have three main contributions:Firstly, we extend game semantics to the quantum case. Game semantics is a dynamic approach to denotational semantics, which focuses on the sequence of interactions between a program and its environment. We obtain the first denotational model of the full quantum lambda-calculus which is both compositional and interactive, meaning that it represents the dynamic of the execution. Our model generalise the recently developed model for the probabilistic case.Secondly, we formally link our model to the only pre-existing denotational model of the full lambda-calculus, the quantum relational model of Pagani, Selinger and Valiron.Lastly, we prove that our game model is fully abstract, the gold standard of denotational semantics, which ensures a total correspondence between the programming language and the model. We deduce that the quantum relational model was also fully abstract, which was an open problem.This thesis is constituted of three parts. The first part details some preliminaries on category theory, used for defining a formal framework including both the quantum game model and the quantum relational model, some preliminaries on the mathematics of quantum computation, and then some preliminaries on quantum programming and its models. The second part starts with some preliminaries on game semantics and defines our quantum game model in the simplified case of the linear quantum lambda-calculus. The third part builds on the second part to define the full quantum game model, prove its full abstraction, and deduce that the quantum relational model is fully abstract too.