@inproceedings{357f01be42cf4950a84919e228394944,
title = "Quantum-over-Classical Advantage in Solving Multiplayer Games",
abstract = "We study the applicability of quantum algorithms in computational game theory and generalize some results related to Subtraction games, which are sometimes referred to as one-heap Nim games. In quantum game theory, a subset of Subtraction games became the first explicitly defined class of zero-sum combinatorial games with provable separation between quantum and classical complexity of solving them. For a narrower subset of Subtraction games, an exact quantum sublinear algorithm is known that surpasses all deterministic algorithms for finding solutions with probability 1. Typically, both Nim and Subtraction games are defined for only two players. We extend some known results to games for three or more players, while maintaining the same classical and quantum complexities: respectively.",
keywords = "Nim, Quantum algorithm, Quantum combinatorial games, Quantum game theory, Quantum multiplayer games, Subtraction game",
author = "Dmitrijs Krav{\v c}enko and Kamil Khadiev and Danil Serov and Ruslan Kapralov",
note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.",
year = "2020",
doi = "10.1007/978-3-030-61739-4\_6",
language = "English",
isbn = "978-303061738-7",
volume = "12448 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "83--98",
editor = "Sylvain Schmitz and Igor Potapov",
booktitle = "Reachability Problems - 14th International Conference, RP 2020, Proceedings",
}