Source-linked AI summary
Computational power of correlations
Janet Anders, Dan E. Browne
TL;DR
The paper asks how correlations can augment a limited classical controller in measurement-based computation and develops a general framework to make that computational power precise. It shows that resource states can promote parity computation to classical universality, with three-qubit GHZ states providing deterministic NAND gates while bipartite quantum states cannot.
Problem
The paper asks which correlated resource states can raise a parity computer's computational power and what features enable measurement-based classical computation.
Method
The authors define a general framework in which a classical control computer exchanges data once with correlated, non-signalling parties, then analyze resource states under binary communication.
Results
Three-qubit GHZ measurements deterministically compute NAND and a polynomial supply promotes the parity computer from ⊕L to classical universality, whereas no bipartite quantum state can deterministically produce NAND.
Takeaways & Limitations
The GHZ and CHSH constructions, together with non-local boxes, connect violations of local realistic models with the computational power of entangled resource states.
Takeaways & Limitations
The framework restricts each party to a single data exchange and leaves higher communication degrees and alternative operation restrictions for further classification.
Abstract
from arXiv · showhide
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.