Classical simulation of noninteracting-fermion quantum circuits

By Barbara M. Terhal, David P. DiVincenzo. arXiv.org, 2001

366 citations recorded by the source corpus.

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)].

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/1c1499b7dc3d29b84dce365674629ee7435663de

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

A Simple Proof that Toffoli and Hadamard are Quantum Universal (2003, background): “Valiant [18] and Terhal and DiVincenzo [17] gave classical simulations for another restricted set of gates, relating them to non interacting fermionic systems.”
Improved Simulation of Stabilizer Circuits (2004, background): “olvable in classical polynomial time.1 However, Valiant’s model has thus far not found any application, although Terhal and DiVincenzo have shown that it applies to a model of noninteracting fermions [31]. There is one class of quantum circuits that is known to be simulable in classical polynomial t”
Simulating Quantum Computation by Contracting Tensor Networks (2005, neutral): “This ﬁnding is consistent with the obstacles to efﬁcient simulation that are evident in the results of Terhal and DiVincenzo [33], later extended by Fenner et al. [14].”
A Race-Track Trapped-Ion Quantum Processor (2023, methodology): “01, as determined by explicit calculations of the noiseless Trotterized dynamics [82] and comparison to exact results for the continuoustime evolutions [83].”
Qulacs: a fast and versatile quantum circuit simulator for research purpose (2020, methodology): “When quantum circuits are constructed only with efficiently simulatable quantum gates such as Clifford gates [78, 79] or matchgates [80–82], these circuits are efficiently simulated via specialized algorithms.”
The computational complexity of linear optics (2010, background): “Previously, in 2002, Terhal and DiVincenzo [34] showed that constant-depth quantum circuits can sample from probability distributions that cannot be e.ciently sampled by a classical computer, unless BQP .”
Quantum computing and the entanglement frontier (2012, background): “17,18 But if we add four-fermion operators to the Hamiltonian, or if we allow nondestructive measurements of four-fermion operators, then universal quantum computation is achievable.”
Variational quantum algorithms (2020, background): “For instance, in quantum chemistry one can exploit the classical simulability of free fermion dynamics to apply quantum operations via classical post-processing [38–43].”
Geometric (2019, background): “Apparently, a single twist operation with 𝑣 = 𝑧 ⊕ 𝑥 proves insufficient to resolve the cubic XOR problem (Fig 3C, middle).”
Matchgates and classical simulation of quantum circuits (2008, methodology): “A (2008) Theorem 1.1 is very similar to the classical simulation result of Terhal & DiVincenzo (2002) and Valiant (2002).”
Universal Computation by Multiparticle Quantum Walk (2012, background): “However, these experiments only involve non-interacting particles; a nontrivial interaction appears necessary for universality [1, 13].”