Contextuality in Measurement-based Quantum Computation

Robert Raussendorf

Published 2009-07-31, updated 2013-04-27Version 3

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