Winning Mastermind Overwhelmingly on Quantum Computers
- URL: http://arxiv.org/abs/2207.09356v3
- Date: Tue, 27 Sep 2022 07:07:04 GMT
- Title: Winning Mastermind Overwhelmingly on Quantum Computers
- Authors: Lvzhou Li, Jingquan Luo, Yongzhen Xu
- Abstract summary: We have a systematic study on quantum strategies for playing Mastermind.
We construct optimal quantum algorithms in both non-adaptive and adaptive settings.
We develop a framework for designing quantum algorithms for the general string learning problem.
- Score: 0.2320417845168326
- License: http://creativecommons.org/licenses/by/4.0/
- 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\in [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. Technically, we develop a framework for
designing quantum algorithms for the general string learning problem, by
discovering a new structure that not only allows quantum speedup to be
maximized on Mastermind in the non-adaptive setting, but also is very likely
helpful for addressing other string learning problems with different kinds of
query oracles.
Related papers
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - Making the cut: two methods for breaking down a quantum algorithm [0.0]
It remains a major challenge to find quantum algorithms that may reach computational advantage in the present era of noisy, small-scale quantum hardware.
We identify and characterize two methods of breaking down'' quantum algorithms into rounds of lower (query) depth.
We show that for the first problem parallelization offers the best performance, while for the second is the better choice.
arXiv Detail & Related papers (2023-05-17T18:00:06Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation.
For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
arXiv Detail & Related papers (2022-10-12T17:54:02Z) - Testing and Learning Quantum Juntas Nearly Optimally [3.030969076856776]
We consider the problem of testing and learning quantum $k$-juntas.
We give (a) a $widetildeO(sqrtk)$-query quantum algorithm that can distinguish quantum $k$-juntas from unitary matrices that are "far" from every quantum $k$-junta.
We complement our upper bounds for testing quantum $k$-juntas and learning quantum $k$-juntas with near-matching lower bounds of $Omega(sqrtk)$ and $Omega(frac
arXiv Detail & Related papers (2022-07-13T00:11:14Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Quantum Semi-Supervised Learning with Quantum Supremacy [0.0]
Quantum machine learning promises to efficiently solve important problems.
There are two persistent challenges in classical machine learning: the lack of labeled data, and the limit of computational power.
We propose a novel framework that resolves both issues: quantum semi-supervised learning.
arXiv Detail & Related papers (2021-10-05T20:15:58Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$.
This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
We establish the first general connection between the design of quantum algorithms and circuit lower bounds.
Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
arXiv Detail & Related papers (2020-12-03T14:03:20Z) - Quantum-over-classical Advantage in Solving Multiplayer Games [0.0]
Subtraction games 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 games.
For a narrower subset of Subtraction games, an exact quantum sublinear algorithm is known that surpasses all deterministic algorithms.
arXiv Detail & Related papers (2020-06-12T06:36:07Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.