Contextuality in measurement-based quantum computation

We show, under natural assumptions for qubit systems, that measurement-based quantum computations (MBQCs) which compute a nonlinear Boolean function with a high probability are contextual. The class of contextual MBQCs includes an example which is of practical interest and has a superpolynomial speedup over the best-known classical algorithm, namely, the quantum algorithm that solves the “discrete log” problem.

Figure 1

Timeline of events in an MBQC. (1) The resource quantum state is prepared. (2) The computational input $\mathbf{i}$ is chosen. (3) The measurements comprising the computation are performed, and their outcomes are processed. The hidden variable model attempting to describe the computation is fixed before the input $\mathbf{i}$ is chosen.

Figure 2

Origin of the linear processing relations (by example). (a) MBQC on a three-particle cluster state. It can be used to simulate the circuit shown in (b) but—if run straightforwardly—executes the probabilistic circuit (c). The need to compensate for the random measurement outcomes enforces a temporal order among the measurements. For explanation see text.