Quantum Magic Rectangles: Characterization and Application to Certified Randomness Expansion

• URL: http://arxiv.org/abs/2008.02370v3
• Date: Wed, 9 Dec 2020 20:49:54 GMT
• Title: Quantum Magic Rectangles: Characterization and Application to Certified Randomness Expansion
• Authors: Sean A. Adamson and Petros Wallden
• Abstract summary: We study a generalization of the Mermin-Peres magic square game to arbitrary rectangular dimensions. We find that for $m times n$ rectangular games of dimensions $m,n geq 3$ there are quantum strategies that win with certainty. For dimensions $1 times n$ quantum strategies do not outperform classical strategies.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a generalization of the Mermin-Peres magic square game to arbitrary rectangular dimensions. After exhibiting some general properties, these rectangular games are fully characterized in terms of their optimal win probabilities for quantum strategies. We find that for $m \times n$ rectangular games of dimensions $m,n \geq 3$ there are quantum strategies that win with certainty, while for dimensions $1 \times n$ quantum strategies do not outperform classical strategies. The final case of dimensions $2 \times n$ is richer, and we give upper and lower bounds that both outperform the classical strategies. Finally, we apply our findings to quantum certified randomness expansion to find the noise tolerance and rates for all magic rectangle games. To do this, we use our previous results to obtain the winning probability of games with a distinguished input for which the devices give a deterministic outcome, and follow the analysis of C. A. Miller and Y. Shi [SIAM J. Comput. 46, 1304 (2017)].

Related papers

• Perfect quantum strategies with small input cardinality [0.0]
  We show how to produce qudit-qudit perfect quantum strategies with a small number of settings. We present a family of perfect quantum strategies in any $(2,d-1,d)$ Bell scenario.
  arXiv  Detail & Related papers  (2024-07-31T09:33:52Z)
• Exploiting Finite Geometries for Better Quantum Advantages in Mermin-Like Games [0.0]
  Quantum games embody non-intuitive consequences of quantum phenomena, such as entanglement and contextuality. In this paper we look at the geometric structure behind such classical strategies, and borrow ideas from the geometry of symplectic polar spaces to maximise this quantum advantage.
  arXiv  Detail & Related papers  (2024-03-14T15:56:43Z)
• 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)
• Repeated quantum game as a stochastic game: Effects of the shadow of the future and entanglement [0.0]
  We present a systematic investigation of the quantum games, constructed using a novel repeated game protocol. We find that how two pure strategies fare against each other is crucially dependent on the discount factor. In the quantum game setup, always-defect strategy can be beaten by the tit-for-tat strategy for high enough discount factor.
  arXiv  Detail & Related papers  (2023-12-08T15:54:51Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
  We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria. This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
  arXiv  Detail & Related papers  (2023-11-17T20:38:38Z)
• Photonic implementation of the quantum Morra game [69.65384453064829]
  We study a faithful translation of a two-player quantum Morra game, which builds on previous work by including the classical game as a special case. We propose a natural deformation of the game in the quantum regime in which Alice has a winning advantage, breaking the balance of the classical game. We discuss potential applications of the quantum Morra game to the study of quantum information and communication.
  arXiv  Detail & Related papers  (2023-11-14T19:41:50Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• On the relation between completely bounded and $(1,cb)$-summing maps with applications to quantum XOR games [65.51757376525798]
  We show that given a linear map from a general operator space into the dual of a C$*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  arXiv  Detail & Related papers  (2021-12-09T21:06:52Z)
• Practical parallel self-testing of Bell states via magic rectangles [0.0]
  Self-testing is a method to verify that one has a particular quantum state from purely classical statistics. We use the $3 times n$ magic rectangle games to obtain a self-test for $n$ Bell states where the one side needs only to measure single-qubit Pauli observables.
  arXiv  Detail & Related papers  (2021-05-09T23:07:18Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  We investigate the increasingly important and common game-solving setting where we do not have an explicit description of the game but only oracle access to it through gameplay. During a limited-duration learning phase, the algorithm can control the actions of both players in order to try to learn the game and how to play it well. Our motivation is to quickly learn strategies that have low exploitability in situations where evaluating the payoffs of a queried strategy profile is costly.
  arXiv  Detail & Related papers  (2020-02-24T20:30:38Z)

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.