Simplest bipartite perfect quantum strategies

• URL: http://arxiv.org/abs/2311.17735v2
• Date: Tue, 24 Sep 2024 07:21:58 GMT
• Title: Simplest bipartite perfect quantum strategies
• Authors: Adán Cabello,
• Abstract summary: A bipartite perfect quantum strategy (BPQS) allows two players who cannot communicate with each other to always win a nonlocal game. A more than 40-year old open problem is how many inputs (measurement settings) a BPQS requires. A related problem is how many inputs are needed if, in addition to the quantum system has minimum dimension.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A bipartite perfect quantum strategy (BPQS) allows two players who cannot communicate with each other to always win a nonlocal game. BPQSs are rare but fundamental in light of some recent results in quantum information, computation, and foundations. A more than 40-year old open problem is how many inputs (measurement settings) a BPQS requires. A related problem is how many inputs are needed if, in addition, the quantum system has minimum dimension. A third, apparently unrelated, problem is what is the connection between BPQSs and state-independent contextuality, which inspired the first BPQSs. Here, we solve the third problem: We prove that {\em every} BPQS defines a Kochen-Specker (KS) set. We use this result to identify the BPQS with the smallest number of inputs, both in the general case and in the case of minimum dimension, and solve some related problems. We argue that either the BPQSs presented are the solutions to the first and second problems or, after more than 56 years of research, we have missed some important KS set.

Related papers

• Revisiting BQP with Non-Collapsing Measurements [0.0]
  We show that when equipped with the ability to perform non-collapsing measurements, BQP contains both BQP and SZK. By formulating an alternative equivalent model of PDQP, we prove the positive weighted adversary method. We also explore related settings, obtaining tight bounds in BQP with the ability to copy arbitrary states.
  arXiv  Detail & Related papers  (2024-11-06T18:06:10Z)
• Optimal conversion of Kochen-Specker sets into bipartite perfect quantum strategies [0.0]
  We show that every BPQS has an associated Kochen-Specker (KS) set. We introduce an algorithm that identifies the BPQS with the minimum number of settings for any given KS set. In each dimension, the algorithm either obtains the best BPQS known or find one with fewer inputs.
  arXiv  Detail & Related papers  (2024-10-22T23:00:24Z)
• The status of the quantum PCP conjecture (games version) [0.6144680854063939]
  We show that multiprover interactive proof systems with polylogarithmically long messages can solve any decision problem in RE. This note contains two main results: (1) we give a "quantum games PCP for AM" in the form of a new construction of a succinct MIP* protocol with efficient provers for the canonical AM-complete problem, and (2) we explain an error in the energy amplification procedure of Natarajan and Vidick.
  arXiv  Detail & Related papers  (2024-03-19T18:30:32Z)
• 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)
• Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation [55.8930142490617]
  We propose a decoder for QLDPC codes based on BP guided decimation (BPGD) BPGD significantly reduces the BP failure rate due to non-convergence.
  arXiv  Detail & Related papers  (2023-12-18T05:58:07Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• A Generalized Quantum Branching Program [0.5584060970507505]
  We propose a quantum branching program model, referred to as GQBP, with the ability to query different variables in superposition. We show several equivalences, namely, between GQBP and AQBP, GQBP and NQBP, and GQBP and query complexities.
  arXiv  Detail & Related papers  (2023-07-21T07:27:51Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
  arXiv  Detail & Related papers  (2023-01-05T11:05:22Z)
• 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)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCS aims at index searching and counting in a quantum-classical hybrid system. We implement IQuCS with Qiskit and conduct intensive experiments. Results demonstrate that it reduces qubits consumption by up to 66.2%.
  arXiv  Detail & Related papers  (2022-09-22T21:54:28Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• BILP-Q: Quantum Coalition Structure Generation [0.0]
  We propose BILP-Q, the first-ever general quantum approach for solving the Coalition Structure Generation problem (CSGP) We run BILP-Q on medium-size problems using a real quantum annealer (D-Wave)
  arXiv  Detail & Related papers  (2022-04-28T22:19:50Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• 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)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59: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.