Contextuality in multipartite pseudo-telepathy graph games
arXiv:1609.09689 · doi:10.1016/j.jcss.2019.06.005
Abstract
Analyzing pseudo-telepathy graph games, we propose a way to build contextuality scenarios exhibiting the quantum supremacy using graph states. We consider the combinatorial structures that generate equivalent scenarios. We introduce a new tool called multipartiteness width to investigate which scenarios are harder to decompose and show that there exist graphs generating scenarios with a linear multipartiteness width.
References in corpus (22)
- Contextuality supplies the magic for quantum computation
- Graph States for Quantum Secret Sharing
- The Sheaf-Theoretic Structure Of Non-Locality and Contextuality
- Contextuality in Measurement-based Quantum Computation
- Multipartite entanglement in spin chains
- Local orthogonality as a multipartite principle for quantum correlations
- Preparation contextuality powers parity-oblivious multiplexing
- Popescu-Rohrlich correlations as a unit of nonlocality
- A Combinatorial Approach to Nonlocality and Contextuality
- The contextual fraction as a measure of contextuality
- Contextuality as a resource for models of quantum computation on qubits
- Generalized Flow and Determinism in Measurement-based Quantum Computation
- Logical Bell Inequalities
- Quantifying Contextuality
- Interactive proofs for BQP via self-tested graph states
- Family of Bell-like inequalities as device-independent witnesses for entanglement depth
- On the power of non-local boxes
- Graph States, Pivot Minor, and Universality of (X,Z)-measurements
- Minimum Degree up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms
- Graph reductions, binary rank, and pivots in gene assembly
- Linear game non-contextuality and Bell inequalities - a graph-theoretic approach
- From quantum foundations via natural language meaning to a theory of everything