Affordable Access

Publisher Website

Measurement-based classical computation

Authors
  • Hoban, Matty J.
  • Wallman, Joel J.
  • Anwar, Hussain
  • Usher, Naïri
  • Raussendorf, Robert
  • Browne, Dan E.
Type
Published Article
Publication Date
Nov 13, 2014
Submission Date
Apr 09, 2013
Identifiers
DOI: 10.1103/PhysRevLett.112.140505
Source
arXiv
License
Yellow
External links

Abstract

Measurement-based quantum computation (MBQC) is a model of quantum computation, in which computation proceeds via adaptive single qubit measurements on a multi-qubit quantum state. It is computationally equivalent to the circuit model. Unlike the circuit model, however, its classical analog is little studied. Here we present a classical analog of MBQC whose computational complexity presents a rich structure. To do so, we identify uniform families of quantum computations (refining the circuits introduced by Bremner, Jozsa and Shepherd in Proc. R. Soc. A 467, 459 (2011)) whose output is likely hard to exactly simulate (sample) classically. We demonstrate that these circuit families can be efficiently implemented in the MBQC model without adaptive measurement, and thus can be achieved in a classical analog of MBQC whose resource state is a probability distribution which has been created quantum mechanically. Such states (by definition) violate no Bell inequality, but nevertheless exhibit non-classicality when used as a computational resource - an imprint of their quantum origin.

Report this publication

Statistics

Seen <100 times