Measurement-based Classical Computation

Hoban, Matty J.; Wallman, Joel J.; Anwar, Hussain; Usher, Naïri; Raussendorf, Robert and Browne, Daniel. 2014. Measurement-based Classical Computation. Physical Review Letters, 112(14), 140505. ISSN 0031-9007 [Article]

ArxivV4New.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial.

Download (594kB) | Preview

Abstract or Description

Measurement-based quantum computation (MBQC) is a model of quantum computation, in which computation proceeds via adaptive single qubit measurements on a multiqubit 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 Proc. R. Soc. A 467, 459 (2010)] 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, if widely held beliefs about computational complexity are true, they, nevertheless, exhibit nonclassicality when used as a computational resource—an imprint of their quantum origin.

Item Type:


Identification Number (DOI):

Departments, Centres and Research Units:



7 February 2014Accepted
9 April 2014Published

Item ID:


Date Deposited:

01 Oct 2018 10:49

Last Modified:

03 Aug 2021 15:03

Peer Reviewed:

Yes, this version has been peer-reviewed.


View statistics for this item...

Edit Record Edit Record (login required)