Quantum Advantage from Sequential-Transformation Contextuality

Abstract

We introduce a notion of contextuality for transformations in sequential contexts, distinct from the Bell-Kochen-Specker and Spekkens notions of contextuality. Within a transformation-based model for quantum computation we show that strong sequential-transformation contextuality is necessary and sufficient for deterministic computation of non-linear functions if classical components are restricted to mod2-linearity and matching constraints apply to any underlying ontology. For probabilistic computation, sequential-transformation contextuality is necessary and sufficient for advantage in this task and the degree of advantage quantifiably relates to the degree of contextuality.

arXiv comment8 pages, 1 figure

References in corpus (41)

• Improved Simulation of Stabilizer Circuits
• On the Power of One Bit of Quantum Information
• On the reality of the quantum state
• Contextuality for preparations, transformations, and unsharp measurements
• Contextuality supplies the magic for quantum computation
• The Sheaf-Theoretic Structure Of Non-Locality and Contextuality
• Quantum advantage with shallow circuits
• Negative Quasi-Probability as a Resource for Quantum Computation
• Graph-Theoretic Approach to Quantum Correlations
• Negativity and contextuality are equivalent notions of nonclassicality
• Specker's Parable of the Over-protective Seer: A Road to Contextuality, Nonlocality and Complementarity (PLUS AN ERRATUM)
• Contextuality in Measurement-based Quantum Computation
• Is a system's wave function in one-to-one correspondence with its elements of reality?
• Preparation contextuality powers parity-oblivious multiplexing
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Computational power of correlations
• A Combinatorial Approach to Nonlocality and Contextuality
• Are quantum states real?
• The contextual fraction as a measure of contextuality
• Contextuality as a resource for models of quantum computation on qubits
• Wigner function negativity and contextuality in quantum computation on rebits
• Discrete Wigner functions and quantum computational speedup
• Contextual advantage for state discrimination
• Quantifying Contextuality
• Necessary and Sufficient Conditions for Extended Noncontextuality in a Broad Class of Quantum Mechanical Systems
• Optimal bounds for parity-oblivious random access codes
• A system's wave function is uniquely determined by its underlying physical state
• Experimental fully contextual correlations
• Non-adaptive Measurement-based Quantum Computation and Multi-party Bell Inequalities
• Resource theory of contextuality for arbitrary prepare-and-measure experiments
• Noncontextual wirings
• Substituting a qubit for an arbitrarily large number of classical bits
• Axiomatic approach to contextuality and nonlocality
• Reality of the quantum state: Towards a stronger ψ-ontology theorem
• A Stronger Theorem Against Macro-realism
• Graph-theoretic strengths of contextuality
• Classical multiparty computation using quantum resources
• Communication complexity and the reality of the wave-function
• Enhanced delegated computing using coherence
• Complexity of the XY antiferromagnet at fixed magnetization
• Quantum Superpositions Cannot be Epistemic

Cited by in corpus (33)

• Kochen-Specker Contextuality
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Phase space simulation method for quantum computation with magic states on qubits
• Machine Learning meets Quantum Foundations: A Brief Survey
• Contextuality Test of the Nonclassicality of Variational Quantum Eigensolvers
• Contextuality as a resource for measurement-based quantum computation beyond qubits
• Contextual Subspace Variational Quantum Eigensolver
• Memory cost of temporal correlations
• Quantum Advantage in Information Retrieval
• Quantum computational advantage with string order parameters of 1D symmetry-protected topological order
• Classical Simulation of Noncontextual Pauli Hamiltonians
• Inequalities witnessing coherence, nonlocality, and contextuality
• 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
• Separability, Contextuality, and the Quantum Frame Problem
• Hierarchies of resources for measurement-based quantum computation
• The Sheaf-Theoretic Structure of Definite Causality
• Corrected Bell and Noncontextuality Inequalities for Realistic Experiments
• Closing Bell: Boxing black box simulations in the resource theory of contextuality
• Continuous-variable nonlocality and contextuality
• From the problem of Future Contingents to Peres-Mermin square experiments: An introductory review to Contextuality
• Connecting XOR and XOR* games
• Entanglement-breaking channels are a quantum memory resource
• A Model of Anaphoric Ambiguities using Sheaf Theoretic Quantum-like Contextuality and BERT
• Newton's laws of motion generating gravity-mediated entanglement
• Emergence of noncontextuality under quantum Darwinism
• Translating Bell Non-Locality to Prepare-and-Measure Scenarios under Dimensional Constraints
• Demonstration of universal contextuality through communication games free of both operational inequivalence and compatibility loopholes
• The Interplay between Quantum Contextuality and Wigner Negativity
• Noncontextual Pauli Hamiltonians
• All fundamental non-contextuality inequalities are unique
• Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits