Dan Shepherd and I have a new paper on the arXiv today:
Instantaneous Quantum Computation
We examine theoretic architectures and an abstract model for a restricted class of quantum computation, called here instantaneous quantum computation because it allows for essentially no temporal structure within the quantum dynamics. Using the theory of binary matroids, we argue that the paradigm is rich enough to enable sampling from probability distributions that cannot, classically, be sampled from efficiently and accurately. This paradigm also admits simple interactive proof games that may convince a skeptic of the existence of truly quantum effects. Furthermore, these effects can be created using significantly fewer qubits than are required for running Shor’s Algorithm.
For a rundown of some of what this paper is about I’m going to do something a little different and point you to the blog that we set up to accompany this paper: Alice’s quantum challenge.