Computational Power of Correlations: A Framework Linking Non-Locality and Measurement-Based Computation

Table of Contents

• 1.1 Introduction & Overview
• 1.2 Core Framework: Measurement-Based Computation
• 1.3 Defining Computational Power of Correlations
• 2.1 Link to Quantum Non-Locality
• 2.2 GHZ and CHSH as Optimal Resource States
• 3.1 Technical Framework & Mathematical Formulation
• 3.2 Experimental Implications & Results
• 4.1 Analysis Framework: A Non-Code Case Study
• 4.2 Future Applications & Research Directions
• 5. References
• 6. Analyst's Perspective: Core Insight, Logical Flow, Strengths & Flaws, Actionable Insights

1.1 Introduction & Overview

This work by Anders and Browne investigates a fundamental question at the intersection of quantum information and computation theory: What is the intrinsic computational power of correlations? Moving beyond specific implementations like the one-way quantum computer, the authors construct a general framework to precisely quantify how correlated resources—accessed via measurements—can enhance the power of a classical control computer. The central, striking finding is a direct connection between the violation of local realistic models (quantum non-locality) and the computational utility of an entangled state within this framework.

1.2 Core Framework: Measurement-Based Computation

The authors define a general model consisting of two components:

1. Correlated Multi-Partite Resource: A set of parties (e.g., qubits) that do not communicate during computation. Each party receives a classical input (one of $k$ choices) from a control computer and returns a classical output (one of $l$ outcomes). The correlations in their outputs are predetermined by their shared state or history.
2. Classical Control Computer: A device of specified computational power (e.g., bounded memory, limited circuit depth) that orchestrates the computation. It sends inputs to the resource parties, receives their outputs, and performs classical processing, potentially using the outcomes to adaptively choose future inputs.

The key restriction is that each resource party is interacted with only once during a given computation. This framework abstracts away quantum mechanics, focusing solely on the classical input-output behavior facilitated by non-classical correlations.

1.3 Defining Computational Power of Correlations

The "computational power" of a correlated resource is defined relative to the classical control computer. A resource provides computational power if, by using it, the control computer can solve a computational problem that it could not solve on its own. This leads to the concept of resource states for measurement-based classical computation (MBCC). The authors seek to characterize which correlation patterns (modeled by conditional probability distributions $P(\text{outputs}|\text{inputs})$) are useful resources.

2.1 Link to Quantum Non-Locality

The paper establishes a profound connection: correlations that violate Bell inequalities (and thus have no local hidden-variable model) are precisely the ones that can serve as non-trivial computational resources in the MBCC framework. This is because the non-locality enables the resource to create dependencies between measurement outcomes that the classical computer, operating under locality constraints, could not generate independently.

2.2 GHZ and CHSH as Optimal Resource States

Surprisingly, well-known non-locality paradigms emerge as optimal examples:

• Greenberger-Horne-Zeilinger (GHZ) State: The correlations in the GHZ paradox provide a resource for solving a specific distributed computation problem (related to the "GHZ game" or computing the XOR of parity bits) that a classical computer cannot solve without communication between the parties.
• Clauser-Horne-Shimony-Holt (CHSH) Inequality: The bipartite correlations that maximally violate the CHSH inequality ($S = 2\sqrt{2}$) correspond to a resource that offers an advantage in computing a Boolean function, outperforming any classical correlated resource bounded by $S \leq 2$.
• Popescu-Rohrlich (PR) Box: This theoretical maximally non-local (but non-signaling) box represents an idealized resource that would provide maximal computational advantage in this model, solving problems with certainty that are impossible for classical resources.

This result reframes these foundational quantum phenomena not just as tests of local realism, but as benchmarks for computational utility.

3.1 Technical Framework & Mathematical Formulation

The framework can be formalized using conditional probability distributions. A resource $R$ is defined by the set of probabilities $P(a_1, a_2, ..., a_n | x_1, x_2, ..., x_n)$, where $x_i$ is the input to party $i$ and $a_i$ is its output. The resource is non-signaling if:

$\sum_{a_i} P(a_1,...,a_n|x_1,...,x_n)$ is independent of $x_i$ for all $i$.

A computation is specified by a function $f$ that the control computer must evaluate, potentially using adaptive strategies based on intermediate results from the resource. The computational power is assessed by comparing the success probability or efficiency of computing $f$ with the resource $R$ versus without it (or with only classical correlations).

3.2 Experimental Implications & Results

While the paper is theoretical, its implications are testable. An experiment demonstrating MBCC would involve:

1. Setup: Preparing a multipartite entangled state (e.g., a GHZ state of photons).
2. Control: A classical computer (e.g., an FPGA) that decides measurement bases (inputs $x_i$) for each photon detector.
3. Computation: The computer receives the detection outcomes ($a_i$) and uses them, following a pre-defined algorithm, to compute the value of a function (e.g., the parity of a distributed input).
4. Result: The success rate of this computation would surpass the maximum achievable if the photon sources were replaced by classical random number generators with shared randomness, bounded by Bell inequalities. The "chart" would show success probability on the y-axis versus the strength of correlations (e.g., the CHSH value $S$) on the x-axis, with a clear threshold at the classical bound ($S=2$).

4.1 Analysis Framework: A Non-Code Case Study

Case: The CHSH Game as a Computational Task.

Task: Two separated parties, Alice and Bob, receive independent random bits $x$ and $y$ (respectively) from the Control Computer. Their goal is to produce outputs $a$ and $b$ such that $a \oplus b = x \cdot y$ (XOR equals AND).

Classical Strategy (with shared randomness): The maximum success probability is $75\%$ ($3/4$). This is the classical bound, equivalent to $S \leq 2$.

Quantum Strategy (using entangled qubits): By sharing an entangled pair and measuring in bases chosen according to $x$ and $y$, they can achieve a success probability of $\cos^2(\pi/8) \approx 85.4\%$. This corresponds to the Tsirelson bound $S = 2\sqrt{2}$.

Analysis: In the MBCC framework, the Control Computer feeds $x$ and $y$ as inputs to the quantum resource (the entangled pair). The outputs $a$ and $b$ are returned. The computer then computes $a \oplus b$, which will equal $x \cdot y$ with $\sim85.4\%$ probability. This is a computational task—calculating the distributed AND function via XOR—that the control computer executes more reliably using the quantum-correlated resource than it could using any classical correlated resource. The non-local correlation is the computational fuel.

4.2 Future Applications & Research Directions

• Benchmarking Quantum Devices: This work provides a new operational meaning for Bell inequality violations—not just as tests of physics, but as calibrations of computational utility. A device's CHSH value directly indicates its power as a resource for certain distributed computing primitives.
• Design of Quantum-Classical Hybrid Algorithms: Understanding which quantum correlations solve which classical problems can guide the design of hybrid algorithms where a small quantum device acts as a "correlation accelerator" for a larger classical processor, a concept gaining traction in the NISQ era.
• Cryptography and Verification: The intrinsic link between non-locality and computational power strengthens device-independent cryptographic protocols. If a remote device can help solve a classically hard problem via MBCC, it certifies the presence of genuine quantum resources.
• Beyond Quantum Theory: The framework allows exploration of theories with stronger-than-quantum correlations (like PR boxes) and their computational consequences, informing the search for physical principles that limit quantum mechanics.

5. References

1. R. Raussendorf and H. J. Briegel, "A One-Way Quantum Computer," Phys. Rev. Lett. 86, 5188 (2001).
2. D. E. Browne and H. J. Briegel, "One-way quantum computation," in Lectures on Quantum Information, Wiley-VCH (2006).
3. M. A. Nielsen, "Cluster-state quantum computation," Rep. Math. Phys. 57, 147 (2006).
4. N. Brunner et al., "Bell nonlocality," Rev. Mod. Phys. 86, 419 (2014).
5. J. F. Clauser et al., "Proposed experiment to test local hidden-variable theories," Phys. Rev. Lett. 23, 880 (1969).
6. D. M. Greenberger et al., "Bell's theorem without inequalities," Am. J. Phys. 58, 1131 (1990).
7. S. Popescu and D. Rohrlich, "Quantum nonlocality as an axiom," Found. Phys. 24, 379 (1994).
8. IBM Quantum, "What is the quantum volume metric?" [Online]. Available: https://www.ibm.com/quantum/computing/volume/

6. Analyst's Perspective: Core Insight, Logical Flow, Strengths & Flaws, Actionable Insights

Core Insight: Anders and Browne deliver a conceptual masterstroke by reframing quantum non-locality—long a subject of foundational debate—as a quantifiable computational resource. Their central thesis is that the "magic" of quantum correlations isn't just about defying local realism; it's a fungible currency that can be spent to solve specific, well-defined classical problems beyond the reach of classical correlations. This bridges a chasm between abstract quantum foundations and applied quantum information science.

Logical Flow: The argument is elegantly constructed. 1) Abstract: Strip away quantum mechanics to define a generic "classical computer + correlated black boxes" model (MBCC). 2) Quantify: Define computational power as an advantage relative to the classical computer alone. 3) Connect: Prove that the resources providing such an advantage are precisely those that violate Bell inequalities. 4) Exemplify: Show that canonical examples (GHZ, CHSH, PR box) are not just curiosities but optimal resources in this computational marketplace. The flow from abstraction to concrete examples is compelling.

Strengths & Flaws: The paper's strength is its profound simplicity and generality. By moving to a device-independent, input-output framework, it makes a result applicable to any physical system exhibiting non-local correlations. However, a significant flaw—or more charitably, a limitation—is its focus on single-round access to the resource. This is a highly restrictive computational model. As noted in works on circuit-based quantum supremacy (like Google's "Quantum Supremacy" experiment in Nature 2019), the power of quantum systems often lies in the depth of sequential, coherent operations. The MBCC model, while clean, may miss the computational value of coherence over time, focusing solely on correlation in space. It brilliantly captures one slice of quantum computational advantage but not its full spectrum.

Actionable Insights: For industry and researchers, this work is a clarion call to think differently about benchmarking. Instead of just reporting a Bell violation or a state fidelity, teams should ask: What specific computational task does this correlation allow us to do better? This could lead to new, application-driven benchmarks for quantum processors, akin to how ML models are benchmarked on specific datasets. Furthermore, it suggests a roadmap for NISQ devices: rather than forcing them to run full quantum algorithms, design hybrid protocols where their primary role is to generate a burst of non-local correlation to accelerate a critical step in a classical pipeline. The paper provides the theoretical justification for viewing a quantum chip not (only) as a miniaturized computer, but as a specialized correlation co-processor.