2009/07/31 by Robert Raussendorf · 1 citation
Physics and Astronomy · #quant-ph
paper · pdf · doi:10.1103/physreva.88.022322
Version 3: probabilistic version of Theorem 1 added
arxiv created 2013/04/27 · arxiv updated 2013/08/28
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.