Measurement-Based Classical Computation

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.

Figure 1

(a) Standard form of an IQP circuit, where each gate is diagonal in the Pauli-$X$ basis and ($x_1$, $x_2$) is the two bit input string. All measurements are in the computational (Pauli-$Z$) basis. The boxed gates give the unitary $D$. (b) A MBQC implementation of the circuit in (a), where each circle represents a qubit prepared in the state $|+⟩$ and edges between circles represent the application of a controlled-$Z$ gate. The contents of the circles represent the basis in which the corresponding qubit is measured, where $X$ represents the Pauli-$X$ basis, and ${\theta }_j$ represents the basis $U_X(-{\theta }_j)Z{U}_X({\theta }_j)$, where $U_X({\theta }_j)$ is a rotation by ${\theta }_j$ about the Pauli-$X$ axis. The angles ${\theta }_j$ are in one-to-one correspondence with the ${\theta }_z$ in the representation of $D_j$ in Eq. (1). All of these measurements can be implemented simultaneously (nonadaptively) in MBQC.