Contextuality in Measurement-based Quantum Computation

Abstract

We show, under natural assumptions for qubit systems, that measurement-based quantum computations (MBQCs) which compute a non-linear Boolean function with high probability are contextual. The class of contextual MBQCs includes an example which is of practical interest and has a super-polynomial speedup over the best known classical algorithm, namely the quantum algorithm that solves the Discrete Log problem.

Version 3: probabilistic version of Theorem 1 added

References in corpus (14)

• Hidden Variables and the Two Theorems of John Bell
• Multi-party entanglement in graph states
• The Sheaf-Theoretic Structure Of Non-Locality and Contextuality
• State-independent experimental test of quantum contextuality
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Measurement-based quantum computation beyond the one-way model
• Computational power of correlations
• Logical Bell Inequalities
• Universal quantum computation with little entanglement
• Classical simulation versus universality in measurement based quantum computation
• Some Open Problems in Quantum Information Theory
• Stronger Quantum Correlations with Loophole-free Post-selection
• Permutational Quantum Computing
• Exponential quantum enhancement for distributed addition with local nonlinearity

Cited by in corpus (162)

• The Variational Quantum Eigensolver: a review of methods and best practices
• Contextuality supplies the magic for quantum computation
• An experimental test of noncontextuality without unwarranted idealizations
• Kochen-Specker Contextuality
• Quasi-quantization: classical statistical theories with an epistemic restriction
• Introduction to the book "Quantum Theory: Informational Foundations and Foils"
• The completeness of quantum theory for predicting measurement outcomes
• Quantum from principles
• The contextual fraction as a measure of contextuality
• Wigner function negativity and contextuality in quantum computation on rebits
• Contextual advantage for state discrimination
• Quantifying Contextuality
• Prime factorization using quantum annealing and computational algebraic geometry
• Equivalence between contextuality and negativity of the Wigner function for qudits
• The Characterization of Noncontextuality in the Framework of Generalized Probabilistic Theories
• State independent contextuality advances one-way communication
• Measurement incompatibility and steering are necessary and sufficient for operational contextuality
• Sustained state-independent quantum contextual correlations from a single ion
• Machine Learning meets Quantum Foundations: A Brief Survey
• All the noncontextuality inequalities for arbitrary prepare-and-measure experiments with respect to any fixed sets of operational equivalences
• Why interference phenomena do not capture the essence of quantum theory
• Necessary and sufficient condition for quantum state-independent contextuality
• Uniqueness of noncontextual models for stabilizer subtheories
• Quantum Advantage from Sequential-Transformation Contextuality
• Contextuality Test of the Nonclassicality of Variational Quantum Eigensolvers
• Converting contextuality into nonlocality
• Contextuality as a resource for measurement-based quantum computation beyond qubits
• Resource theory of contextuality for arbitrary prepare-and-measure experiments
• Noncontextual wirings
• Leggett-Garg macrorealism and the quantum nondisturbance conditions
• Nonlocality from local contextuality
• Experimental observation of Hardy-like quantum contextuality
• Significant-loophole-free test of Kochen-Specker contextuality using two species of atomic-ions
• Contextuality and Wigner negativity are equivalent for continuous-variable quantum measurements
• Necessary and sufficient condition for contextuality from incompatibility
• Axiomatic approach to contextuality and nonlocality
• Measurement-based classical computation
• One-Shot Manipulation of Dynamical Quantum Resources
• Contextuality in phase space
• Generalized Cluster States Based on Finite Groups
• Experimental Test of the Quantum Violation of the Noncontextuality Inequalities for the n-Cycle Scenario
• Quantum correlations from simple assumptions
• Local convertibility and the quantum simulation of edge states in many-body systems
• Proof of the Peres conjecture for contextuality
• Contextuality without incompatibility
• Experimental test of contextuality in quantum and classical systems
• Contextual Subspace Variational Quantum Eigensolver
• Quantum theory allows for absolute maximal contextuality
• Memory cost of temporal correlations
• Measuring coherence of quantum measurements
• Measurement-based quantum computation in finite one-dimensional systems: string order implies computational power
• Quantum computational advantage with string order parameters of 1D symmetry-protected topological order
• Contextuality-by-Default description of Bell tests: Contextuality as the rule not as an exception
• Beyond the Cabello-Severini-Winter framework: Making sense of contextuality without sharpness of measurements
• Classical Simulation of Noncontextual Pauli Hamiltonians
• Sum-of-squares decompositions for a family of noncontextuality inequalities and self-testing of quantum devices
• Memory cost for simulating all quantum correlations of the Peres-Mermin scenario
• Contextuality in spin-orbit laser modes
• Inequalities witnessing coherence, nonlocality, and contextuality
• Bounds on the power of proofs and advice in general physical theories
• Graph-theoretic strengths of contextuality
• Kirkwood-Dirac representations beyond quantum states (and their relation to noncontextuality)
• Classical multiparty computation using quantum resources
• A comonadic view of simulation and quantum resources
• Neither Contextuality nor Nonlocality Admits Catalysts
• Tsirelson's bound and Landauer's principle in a single-system game
• Quantum Protocols within Spekkens' Toy Model
• Arbitrarily exhaustive hypergraph generation of 4-, 6-, 8-, 16-, and 32-dimensional quantum contextual sets
• The role of cohomology in quantum computation with magic states
• Correlations for computation and computation for correlations
• Classical causal models cannot faithfully explain Bell nonlocality or Kochen-Specker contextuality in arbitrary scenarios
• A mathematical framework for operational fine tunings
• Contextuality as a Precondition for Quantum Entanglement
• Necessary Conditions for Extended Noncontextuality in General Sets of Random Variables
• A proof of the Kochen-Specker theorem can always be converted to a state-independent noncontextuality inequality
• Non-locality, contextuality and valuation algebras: a general theory of disagreement
• Spekkens' toy model in all dimensions and its relationship with stabilizer quantum mechanics
• Separability, Contextuality, and the Quantum Frame Problem
• Topological contextuality and anyonic statistics of photonic-encoded parafermions
• When Federated Learning Meets Quantum Computing: Survey and Research Opportunities
• Homotopical approach to quantum contextuality
• Contextuality in multipartite pseudo-telepathy graph games
• General conditions for maximal violation of non-contextuality in discrete and continuous variables
• Hardy is (almost) everywhere: nonlocality without inequalities for almost all entangled multipartite states
• A review and reformulation of macroscopic realism: resolving its deficiencies using the framework of generalized probabilistic theories
• Graph Approach to Extended Contextuality
• Reliable computation from contextual correlations
• Contextuality degree of quadrics in multi-qubit symplectic polar spaces
• Enhanced delegated computing using coherence
• Hierarchies of resources for measurement-based quantum computation
• Decomposable coherence and quantum fluctuation relations
• Contextuality and bundle diagrams
• Contextuality beyond the Kochen-Specker theorem
• A complete characterisation of All-versus-Nothing arguments for stabiliser states
• Playing nonlocal games across a topological phase transition on a quantum computer
• Experimental test of high-dimensional quantum contextuality based on contextuality concentration
• Towards a complete cohomology invariant for non-locality and contextuality
• On Possibilistic Conditions to Contextuality and Nonlocality
• Universal resources for quantum computing
• Experimental demonstration of fully contextual quantum correlations on an NMR quantum information processor
• Contextuality and noncommutative geometry in quantum mechanics
• Logical and inequality based contextuality for qudits
• No-broadcasting characterizes operational contextuality
• Corrected Bell and Noncontextuality Inequalities for Realistic Experiments
• Logical structures underlying quantum computing
• State-independent quantum contextuality with projectors of nonunit rank
• Closing Bell: Boxing black box simulations in the resource theory of contextuality
• Non-adaptive measurement-based quantum computation on IBM Q
• On characterising assemblages in Einstein-Podolsky-Rosen scenarios
• Classical Limits and Contextuality in a Scenario of Multiple Observers
• Continuous-variable nonlocality and contextuality
• My discussions of quantum foundations with John Stewart Bell
• Relativity of quantum states in entanglement swapping: Violation of Bell's inequality with no entanglement
• Cohomology and the Algebraic Structure of Contextuality in Measurement Based Quantum Computation
• Contextuality and the fundamental theorems of quantum mechanics
• Sheaf-Theoretic Methods in Quantum Mechanics and Quantum Information Theory
• Connecting XOR and XOR* games
• Irreducible magic sets for $n$-qubit systems
• Hidden variable model for quantum computation with magic states on qudits of any dimension
• Non-classical Correlations in n-Cycle Setting
• A Logical Proof of Quantum Correlations Requiring Entanglement Measurements
• Revisiting the admissibility of non-contextual hidden variable models in quantum mechanics
• A Model of Anaphoric Ambiguities using Sheaf Theoretic Quantum-like Contextuality and BERT
• The many mathematical faces of Mermin's proof of the Kochen-Specker theorem
• Tsirelson inequalities: Detecting cheating and quantumness in a single framework
• Lifting noncontextuality inequalities
• Generalised Kochen-Specker Theorem for Finite Non-Deterministic Outcome Assignments
• The Influence of Experimental Imperfections on Photonic GHZ State Generation
• Newton's laws of motion generating gravity-mediated entanglement
• The six blinds and the elephant or an interdisciplinary selection of measurement features
• Contextuality and Nonlocality in Decaying Multipartite Systems
• No quantum solutions to linear constraint systems in odd dimension from Pauli group and diagonal Cliffords
• Generalised Winograd Schema and its Contextuality
• Contextuality of Quantum Error-Correcting Codes
• Emergence of noncontextuality under quantum Darwinism
• Topos logic in measurement-based quantum computation
• Exploring the boundary of quantum correlations with a time-domain optical processor
• How contextuality and antidistinguishability are related
• Twenty years of quantum contextuality at USTC
• Experimental Approach to Demonstrating Contextuality for Qudits
• Classical Invasive Description of Informationally-Complete Quantum Processes
• An Entanglement Monotone from the Contextual Fraction
• Maximal Non-Kochen-Specker Sets and a Lower Bound on the Size of Kochen-Specker Sets
• Non-onsite symmetries and quantum teleportation in split-index matrix product states
• Trade-off relations between Bell nonlocality and local Kochen-Specker contextuality in generalized Bell scenarios
• Quantum foundations for quantum technologies in the International Year of Quantum (2025)
• Demonstration of universal contextuality through communication games free of both operational inequivalence and compatibility loopholes
• Contextuality, Witness of Quantum Weirdness
• Quantum computational advantage implies contextuality
• A Classification Program for Nonlocality Paradoxes of Three Qubits
• Convexity of noncontextual wirings and how they order the set of correlations
• Revealing universal quantum contextuality through communication games
• k-Contextuality as a Heuristic for Memory Separations in Learning
• Periodic Fourier representation of Boolean functions
• Quantum contextuality from measurement invasiveness
• Noncontextual Pauli Hamiltonians
• All fundamental non-contextuality inequalities are unique
• The Interplay between Quantum Contextuality and Wigner Negativity
• Frame dependence of Spekkens' contextuality for relativistic spin systems
• Contextuality from the vacuum
• Analogs of absolutely maximally entangled states in nonlocal correlations via the sheaf-theoretic framework and its applications
• Duality of Graph Invariants