Perfect quantum strategies with small input cardinality

• URL: http://arxiv.org/abs/2407.21473v1
• Date: Wed, 31 Jul 2024 09:33:52 GMT
• Title: Perfect quantum strategies with small input cardinality
• Authors: Stefan Trandafir, Junior R. Gonzales-Ureta, Adan Cabello,
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A perfect strategy is one that allows the mutually in-communicated players of a nonlocal game to win every trial of the game. Perfect strategies are basic tools for some fundamental results in quantum computation and crucial resources for some applications in quantum information. Here, we address the problem of producing qudit-qudit perfect quantum strategies with a small number of settings. For that, we exploit a recent result showing that any perfect quantum strategy induces a Kochen-Specker set. We identify a family of KS sets in even dimension $d \ge 6$ that, for many dimensions, require the smallest number of orthogonal bases known: $d+1$. This family was only defined for some $d$. We first extend the family to infinitely many more dimensions. Then, we show the optimal way to use each of these sets to produce a bipartite perfect strategy with minimum input cardinality. As a result, we present a family of perfect quantum strategies in any $(2,d-1,d)$ Bell scenario, with $d = 2^kp^m$ for $p$ prime, $m \geq k \geq 0$ (excluding $m=k=0$), $d = 8p$ for $p \geq 19$, $d=kp$ for $p > ((k-2)2^{k-2})^2$ whenever there exists a Hadamard matrix of order $k$, other sporadic examples, as well as a recursive construction that produces perfect quantum strategies for infinitely many dimensions $d$ from any dimension $d'$ with a perfect quantum strategy. We identify their associated Bell inequalities and prove that they are not tight, which provides a second counterexample to a conjecture of 2007.

Related papers

• Better bounds on Grothendieck constants of finite orders [20.068273625719943]
  We exploit a recent Frank-Wolfe approach to provide good candidates for lower bounding some Grothendieck constants. The complete proof relies on solving difficult binary quadratic optimisation problems.
  arXiv  Detail & Related papers  (2024-09-05T17:53:52Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  We present an exact quantum algorithm for computing $textMOD_mn$. We show exact quantum query complexity of a broad class of symmetric functions that map $0,1n$ to a finite set $X$ is less than $n$.
  arXiv  Detail & Related papers  (2023-03-20T08:17:32Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Winning Mastermind Overwhelmingly on Quantum Computers [0.2320417845168326]
  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.
  arXiv  Detail & Related papers  (2022-07-19T16:02:28Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• 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)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• 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)
• Quantum Magic Rectangles: Characterization and Application to Certified Randomness Expansion [0.0]
  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.
  arXiv  Detail & Related papers  (2020-08-05T21:19:34Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

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.