Classical simulation of noninteracting-fermion quantum circuits
- 1 March 2002
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 65 (3), 032325
- https://doi.org/10.1103/physreva.65.032325
Abstract
We show that a class of quantum computations that was recently shown to be efficiently simulatable on a classical computer by Valiant [in Proceedings of the 33rd ACM Symposium on the Theory of Computing (2001), p. 114] corresponds to a physical model of noninteracting fermions in one dimension. We give an alternative proof of his result using the language of fermions and extend the result to noninteracting fermions with arbitrary pairwise interactions, where gates can be conditioned on outcomes of complete von Neumann measurements in the computational basis on other fermionic modes in the circuit. This last result is in remarkable contrast with the case of noninteracting bosons where universal quantum computation can be achieved by allowing gates to be conditioned on classical bits [E. Knill, R. Laflamme, and G. Milburn, Nature (London) 409, 46 (2001)].Keywords
Other Versions
This publication has 9 references indexed in Scilit:
- Unpaired Majorana fermions in quantum wiresPhysics-Uspekhi, 2001
- A scheme for efficient quantum computation with linear opticsNature, 2001
- An Introduction to Coupled Cluster Theory for Computational ChemistsReviews in Computational Chemistry, 2000
- Quantum Information Processing Using Quantum Dot Spins and Cavity QEDPhysical Review Letters, 1999
- Simulation of Many-Body Fermi Systems on a Universal Quantum ComputerPhysical Review Letters, 1997
- Experimental realization of any discrete unitary operatorPhysical Review Letters, 1994
- The complexity of computing the permanentTheoretical Computer Science, 1979
- The Evaluation of the Collision MatrixPhysical Review B, 1950
- ber das Paulische quivalenzverbotThe European Physical Journal A, 1928