Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2410.17470 · Physical Review A

Optimal conversion of Kochen-Specker sets into bipartite perfect quantum strategies

Stefan Trandafir, Adán Cabello

Published Feb 7, 2025• 2 citations
arXivHTMLPDF

Abstract

Bipartite perfect quantum strategies (BPQSs) allow two players isolated from each other to win every trial of a nonlocal game. BPQSs have crucial roles in recent developments in quantum information and quantum computation. However, only few BPQSs with a small number of inputs are known and only one of them has been experimentally tested. It has recently been shown that every BPQS has an associated Kochen-Specker (KS) set. Here, we first prove that any BPQS of minimum input cardinality that can be obtained from a generalized KS set can also be obtained from a KS set of pure states. We address the problem of finding BPQSs of small input cardinality starting from KS sets. We introduce an algorithm that identifies the BPQS with the minimum number of settings for any given KS set. We apply it to many well-known KS sets of small cardinality in dimensions 3, 4, 5, 6, 7, and 8. In each dimension, the algorithm either recovers the best BPQS known or finds one with fewer inputs.

DOI
10.1103/physreva.111.022408

Related papers

Simplest Bipartite Perfect Quantum Strategies

Adán Cabello

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 every BPQS defines a Kochen-Specker 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 conjecture that the BPQSs presented here are the solutions to the first two problems.

arXiv:2311.17735•Physical Review Letters•Jan 2, 2025•8 citations

Perfect quantum strategies with small input cardinality

Stefan Trandafir, Junior R. Gonzales-Ureta, Adán Cabello

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.

arXiv:2407.21473•Jul 31, 2024•0 citations

Simplest Kochen-Specker Set

Adán Cabello

Kochen-Specker (KS) sets are fundamental in physics. Every time nature produces bipartite correlations attaining the nonsignaling limit, or two parties always win a nonlocal game impossible to always win classically, it is because the parties are measuring a KS set. The simplest quantum system in which all these phenomena occur is a pair of three-level systems. However, the simplest KS sets known in dimension three are asymmetrical and require a large number of bases (the current minimum is 16, set by Peres and Penrose). Here, we present a KS set that is much more symmetrical and easier to prove than any previous example. It sets a new record for minimum number of bases, 14, and enables us to refute Conjecture 2 in Cabello Simplest bipartite perfect quantum strategies, Phys. Rev. Lett. 134, 010201 (2025)PRLTAO0031-900710.1103/PhysRevLett.134.010201, setting a new record for qutrit-qutrit perfect strategies with a minimum number of inputs: 5-9. We establish the fundamental nature of this set in quantum theory.

arXiv:2508.07335•Physical Review Letters•Nov 6, 2025•4 citations

Reply to Pavi\v{c}i\'c's 'Comment on "Optimal conversion of Kochen-Specker sets into bipartite perfect quantum strategies"' (arXiv:2502.13787)

Stefan Trandafir, Adán Cabello

According to Pavi\v{c}i{\'c}, Kochen and Specker's 117-observable set is not a ``Kochen-Specker set''. By the same reason, in arXiv:2502.13787, Pavi\v{c}i{\'c} claims that 10 statements in our paper ``Optimal conversion of Kochen-Specker sets into bipartite perfect quantum strategies'' [Phys. Rev. A 111, 022408 (2025)] are ``wrong''. In all cases, Pavi\v{c}i{\'c}'s claims are based on the fact that he is assuming a different definition of Kochen-Specker (KS) set. Adopting a terminology used by, e.g., Larsson, the sets that Pavi\v{c}i{\'c} call KS sets can be called ``extended'' KS sets, since they are constructed by adding observables to the ``original'' KS sets. For example, Pavi\v{c}i{\'c} adds 75 observables to the original 117-observable KS set. Beyond terminology, there are fundamental physical reasons for focusing on the original KS sets. One reason is that, for experimentally observing quantum state-independent contextuality, there is no need to measure the observables added in the extended sets. Another reason is that, to produce bipartite perfect quantum strategies, or correlations in a face of the nonsignaling polytope with no local points, or correlations with nonlocal content 1, the two parties do not need to measure any of the observables added in the extended sets. We also respond to other claims made by Pavi\v{c}i{\'c} about our work.

arXiv:2503.02974•Mar 4, 2025•0 citations

Comment on "Optimal conversion of Kochen-Specker sets into bipartite perfect quantum strategies"

Mladen Pavičić

A recent paper of Trandafir and Cabello [Phys. Rev. A, 111, 022408 (2025)] contains a number of errors, inconsistencies, and inefficiencies. They are too numerous to be listed here, so we identify and discuss them in the main body of the comment.

arXiv:2502.13787•Feb 19, 2025•0 citations

Kochen-Specker set with seven contexts

Petr Lisoněk, Piotr Badziąg, José R. Portillo +1 more

The Kochen-Specker (KS) theorem is a central result in quantum theory and has applications in quantum information. Its proof requires several yes-no tests that can be grouped in contexts or subsets of jointly measurable tests. Arguably, the best measure of simplicity of a KS set is the number of contexts. The smaller this number is, the smaller the number of experiments needed to reveal the conflict between quantum theory and noncontextual theories and to get a quantum vs classical outperformance. The original KS set had 132 contexts. Here we introduce a KS set with seven contexts and prove that this is the simplest KS set that admits a symmetric parity proof.

arXiv:1308.6012•Physical Review A•Apr 1, 2014•52 citations
Bipartite perfect quantum strategies (BPQSs) allow two players isolated from each other to win every trial of a nonlocal game. BPQSs have crucial roles in recent developments in quantum information and quantum computation. However, only few BPQSs with a small number of inputs are known and only one of them has been experimentally tested. It has recently been shown that every BPQS has an associated Kochen-Specker (KS) set. Here, we first prove that any BPQS of minimum input cardinality that can be obtained from a generalized KS set can also be obtained from a KS set of pure states. We address the problem of finding BPQSs of small input cardinality starting from KS sets. We introduce an algorithm that identifies the BPQS with the minimum number of settings for any given KS set. We apply it to many well-known KS sets of small cardinality in dimensions 3, 4, 5, 6, 7, and 8. In each dimension, the algorithm either recovers the best BPQS known or finds one with fewer inputs.
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 every BPQS defines a Kochen-Specker 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 conjecture that the BPQSs presented here are the solutions to the first two problems.
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≥6d \ge 6d≥6 that, for many dimensions, require the smallest number of orthogonal bases known: d+1d+1d+1. This family was only defined for some ddd. 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)(2,d-1,d)(2,d−1,d) Bell scenario, with d=2kpmd = 2^kp^md=2kpm for ppp prime, m≥k≥0m \geq k \geq 0m≥k≥0 (excluding m=k=0m=k=0m=k=0), d=8pd = 8pd=8p for p≥19p \geq 19p≥19, d=kpd=kpd=kp for p>((k−2)2k−2)2p > ((k-2)2^{k-2})^2p>((k−2)2k−2)2 whenever there exists a Hadamard matrix of order kkk, other sporadic examples, as well as a recursive construction that produces perfect quantum strategies for infinitely many dimensions ddd from any dimension d′d'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.
Kochen-Specker (KS) sets are fundamental in physics. Every time nature produces bipartite correlations attaining the nonsignaling limit, or two parties always win a nonlocal game impossible to always win classically, it is because the parties are measuring a KS set. The simplest quantum system in which all these phenomena occur is a pair of three-level systems. However, the simplest KS sets known in dimension three are asymmetrical and require a large number of bases (the current minimum is 16, set by Peres and Penrose). Here, we present a KS set that is much more symmetrical and easier to prove than any previous example. It sets a new record for minimum number of bases, 14, and enables us to refute Conjecture 2 in Cabello Simplest bipartite perfect quantum strategies, Phys. Rev. Lett. 134, 010201 (2025)PRLTAO0031-900710.1103/PhysRevLett.134.010201, setting a new record for qutrit-qutrit perfect strategies with a minimum number of inputs: 5-9. We establish the fundamental nature of this set in quantum theory.
According to Pavi\v{c}i{\'c}, Kochen and Specker's 117-observable set is not a ``Kochen-Specker set''. By the same reason, in arXiv:2502.13787, Pavi\v{c}i{\'c} claims that 10 statements in our paper ``Optimal conversion of Kochen-Specker sets into bipartite perfect quantum strategies'' [Phys. Rev. A 111, 022408 (2025)] are ``wrong''. In all cases, Pavi\v{c}i{\'c}'s claims are based on the fact that he is assuming a different definition of Kochen-Specker (KS) set. Adopting a terminology used by, e.g., Larsson, the sets that Pavi\v{c}i{\'c} call KS sets can be called ``extended'' KS sets, since they are constructed by adding observables to the ``original'' KS sets. For example, Pavi\v{c}i{\'c} adds 75 observables to the original 117-observable KS set. Beyond terminology, there are fundamental physical reasons for focusing on the original KS sets. One reason is that, for experimentally observing quantum state-independent contextuality, there is no need to measure the observables added in the extended sets. Another reason is that, to produce bipartite perfect quantum strategies, or correlations in a face of the nonsignaling polytope with no local points, or correlations with nonlocal content 1, the two parties do not need to measure any of the observables added in the extended sets. We also respond to other claims made by Pavi\v{c}i{\'c} about our work.
The Kochen-Specker (KS) theorem is a central result in quantum theory and has applications in quantum information. Its proof requires several yes-no tests that can be grouped in contexts or subsets of jointly measurable tests. Arguably, the best measure of simplicity of a KS set is the number of contexts. The smaller this number is, the smaller the number of experiments needed to reveal the conflict between quantum theory and noncontextual theories and to get a quantum vs classical outperformance. The original KS set had 132 contexts. Here we introduce a KS set with seven contexts and prove that this is the simplest KS set that admits a symmetric parity proof.