Temporally unstructured quantum computation
- 20 February 2009
- journal article
- Published by The Royal Society in Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
- Vol. 465 (2105), 1413-1439
- https://doi.org/10.1098/rspa.2008.0443
Abstract
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.Comment: Significantly rewritten for clarity, more explanation addeKeywords
Other Versions
This publication has 14 references indexed in Scilit:
- On entropy growth and the hardness of simulating time evolutionNew Journal of Physics, 2008
- Entropy Scaling and Simulability by Matrix Product StatesPhysical Review Letters, 2008
- Experimental Demonstration of a Compiled Version of Shor’s Algorithm with Quantum EntanglementPhysical Review Letters, 2007
- Demonstration of a Compiled Version of Shor’s Quantum Factoring Algorithm Using Photonic QubitsPhysical Review Letters, 2007
- Experimental Realization of Deutsch’s Algorithm in a One-Way Quantum ComputerPhysical Review Letters, 2007
- Quantum computing, postselection, and probabilistic polynomial-timeProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2005
- Measurement-based quantum computation on cluster statesPhysical Review A, 2003
- Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonanceNature, 2001
- A One-Way Quantum ComputerPhysical Review Letters, 2001
- On the Power of Quantum ComputationSIAM Journal on Computing, 1997