Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · 2009 · 177 citations · 20 references
ComputingComputer SciencePhysicsQuantum ComputingQuantum MechanicsTheory Of ComputationQuantum AlgorithmsQuantum BitsQuantum ComputationQuantum DynamicsQuantum Hardware ArchitecturesBinary MatroidsQuantum Computing ArchitectureQuantum Interactive Proof Systems
We examine theoretic architectures and an abstract model for a restricted class of quantum computation, called here temporally unstructured (‘ 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 efficiently and accurately. This paradigm also admits simple interactive proof games that may convince a sceptic 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.
20
Algorithms for quantum computation: discrete logarithms and factoring
Peter W. Shor · 2002 · 8.5K citations
Computing, Computer Science, Physics +12
Robert Raussendorf, Hans J. Briegel · Physical Review Letters · 2001 · 4.5K citations
Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
Lieven M. K. Vandersypen, Matthias Steffen, Gregory Breyta et al. · Nature · 2001 · 1.7K citations · Full text
Computing, Computer Science, Physics +15
Measurement-based quantum computation on cluster states
Robert Raussendorf, Dan E. Browne, Hans J. Briegel · Physical Review A · 2003 · 1.7K citations · Full text
Computing, Computer Science, Physics +17
On the Power of Quantum Computation
Daniel Simón · SIAM Journal on Computing · 1997 · 1.3K citations
Computing, Computer Science, Physics +14