Computational power of correlations

Abstract

We study the intrinsic computational power of correlations exploited in measurement-based quantum computation. By defining a general framework the meaning of the computational power of correlations is made precise. This leads to a notion of resource states for measurement-based \textit{classical} computation. Surprisingly, the Greenberger-Horne-Zeilinger and Clauser-Horne-Shimony-Holt problems emerge as optimal examples. Our work exposes an intriguing relationship between the violation of local realistic models and the computational power of entangled resource states.

4 pages, 2 figures, 2 tables, v2: introduction revised and title changed to highlight generality of established framework and results, v3: published version with additional table II

References in corpus (11)

• Measurement-based quantum computation with cluster states
• Improved Simulation of Stabilizer Circuits
• Cluster-state quantum computation
• Novel schemes for measurement-based quantum computation
• Universal resources for measurement-based quantum computation
• Measurement-based quantum computation beyond the one-way model
• Generalized Flow and Determinism in Measurement-based Quantum Computation
• Fundamentals of universality in one-way quantum computation
• Violating Bell's inequality beyond Cirel'son's bound
• On the power of non-local boxes
• Feats, Features and Failures of the PR-box

Cited by in corpus (115)

• Circuit Quantum Electrodynamics
• The classical-quantum boundary for correlations: discord and related measures
• Universal blind quantum computation
• Most quantum states are too entangled to be useful as computational resources
• Unconditionally verifiable blind computation
• Contextuality in Measurement-based Quantum Computation
• Kochen-Specker Contextuality
• Introduction to the book "Quantum Theory: Informational Foundations and Foils"
• Quantum from principles
• Quasi-quantization: classical statistical theories with an epistemic restriction
• The completeness of quantum theory for predicting measurement outcomes
• All noncontextuality inequalities for the n-cycle scenario
• The contextual fraction as a measure of contextuality
• Wigner function negativity and contextuality in quantum computation on rebits
• Are random pure states useful for quantum computation?
• Observation of tunable Popescu-Rohrlich correlations through post-selection of a gaussian state
• Experimental implementation of a Kochen-Specker set of quantum tests
• Enhancing Generative Models via Quantum Correlations
• Nonclassical correlations from randomly chosen local measurements
• Equivalence between contextuality and negativity of the Wigner function for qudits
• State independent contextuality advances one-way communication
• Towards device-independent information processing on general quantum networks
• Proposal for generating and detecting multi-qubit GHZ states in circuit QED
• Nonlocality of Symmetric States
• All the noncontextuality inequalities for arbitrary prepare-and-measure experiments with respect to any fixed sets of operational equivalences
• Quantum computation by local measurement
• Uniqueness of noncontextual models for stabilizer subtheories
• Quantum Advantage from Sequential-Transformation Contextuality
• Basic exclusivity graphs in quantum correlations
• Non-adaptive Measurement-based Quantum Computation and Multi-party Bell Inequalities
• Converting contextuality into nonlocality
• Contextuality as a resource for measurement-based quantum computation beyond qubits
• Nonlocality from local contextuality
• Significant-loophole-free test of Kochen-Specker contextuality using two species of atomic-ions
• Necessary and sufficient condition for contextuality from incompatibility
• Measurement-based classical computation
• Measurement-Based Quantum Computation
• Generalized Cluster States Based on Finite Groups
• Hybrid valence-bond states for universal quantum computation
• Quantum correlations from simple assumptions
• Controlled Quantum Teleportation in the Presence of an Adversary
• Proof of the Peres conjecture for contextuality
• Generalized Bell Inequality Experiments and Computation
• Secure Multi-Party Computation with a Dishonest Majority via Quantum Means
• Quantum computational advantage with string order parameters of 1D symmetry-protected topological order
• Measurement-based quantum computation in finite one-dimensional systems: string order implies computational power
• Contextuality bounds the efficiency of classical simulation of quantum processes
• Contextuality in spin-orbit laser modes
• Stronger Quantum Correlations with Loophole-free Post-selection
• Classical multiparty computation using quantum resources
• Noncontextuality Inequalities from Antidistinguishability
• Single-photon quantum contextuality on a chip
• Graph-theoretic strengths of contextuality
• The role of cohomology in quantum computation with magic states
• Neither Contextuality nor Nonlocality Admits Catalysts
• Correlations for computation and computation for correlations
• Classical causal models cannot faithfully explain Bell nonlocality or Kochen-Specker contextuality in arbitrary scenarios
• The compositional structure of multipartite quantum entanglement
• Non-signaling Causal Hierarchy of General Multisource Networks
• Multipartite Nonlocality as a Resource and Quantum Correlations Having Indefinite Causal Order
• Self-testing and certification using trusted quantum inputs
• Homotopical approach to quantum contextuality
• Enhanced delegated computing using coherence
• Reliable computation from contextual correlations
• Primitive Nonclassical Structures of the $N$-qubit Pauli Group
• Contextuality and bundle diagrams
• Hierarchies of resources for measurement-based quantum computation
• Playing nonlocal games across a topological phase transition on a quantum computer
• Universal resources for quantum computing
• A complete characterisation of All-versus-Nothing arguments for stabiliser states
• The power of qutrits for non-adaptive measurement-based quantum computing
• A Framework for Heterotic Computing
• Adiabatic graph-state quantum computation
• The Gauge Theory of Measurement-Based Quantum Computation
• Logical and inequality based contextuality for qudits
• All tight correlation Bell inequalities have quantum violations
• Logical structures underlying quantum computing
• Quantum linear network coding as one-way quantum computation
• Relativity of quantum states in entanglement swapping: Violation of Bell's inequality with no entanglement
• Contextuality and the fundamental theorems of quantum mechanics
• On characterising assemblages in Einstein-Podolsky-Rosen scenarios
• Quantum circuit dynamics via path integrals: Is there a classical action for discrete-time paths?
• Increasing complexity with quantum physics
• Generalized spin squeezing inequalities for particles number with quantum fluctuations
• Werner gap in presence of simple coloured noise
• Quantum bit commitment with cheat sensitive binding and approximate sealing
• Irreducible magic sets for $n$-qubit systems
• A Logical Proof of Quantum Correlations Requiring Entanglement Measurements
• Combining contextuality and causality: a game semantics approach
• Finding resource states of measurement-based quantum computing is harder than quantum computing
• Classifying space for quantum contextuality
• Universal quantum computation via quantum controlled classical operations
• Generalized parity proofs of the Kochen-Specker theorem
• A Model of Anaphoric Ambiguities using Sheaf Theoretic Quantum-like Contextuality and BERT
• Quantum advantage in temporally flat measurement-based quantum computation
• Exploring the boundary of quantum correlations with a time-domain optical processor
• Topos logic in measurement-based quantum computation
• Generalised Winograd Schema and its Contextuality
• Experimental Approach to Demonstrating Contextuality for Qudits
• Quantum Merlin-Arthur with Clifford Arthur
• Quantum-enhanced Secure Delegated Classical Computing
• How contextuality and antidistinguishability are related
• Quantum formalism on the plane: POVM-Toeplitz quantization, Naimark theorem and linear polarisation of the light
• Quantum computational advantage implies contextuality
• Discord in relation to resource states for measurement-based quantum computation
• Periodic Fourier representation of Boolean functions
• Contextuality, superlocality and nonclassicality of supernoncontextuality
• Lossy-and-Constrained Extended Non-Local Games with Applications to Quantum Cryptography
• k-Contextuality as a Heuristic for Memory Separations in Learning
• Resource complexity of Symmetry Protected Topological phases
• Analogs of absolutely maximally entangled states in nonlocal correlations via the sheaf-theoretic framework and its applications
• A Classification Program for Nonlocality Paradoxes of Three Qubits
• The Interplay between Quantum Contextuality and Wigner Negativity
• Integration Testing of Heterotic Systems
• Entanglement, Flow and Classical Simulatability in Measurement Based Quantum Computation