Instantaneous Quantum Computation

Understand

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.