arXiv:quant-ph/0108010 · Physical Review A

Classical simulation of noninteracting-fermion quantum circuits

Barbara M. Terhal, David Peter Divincenzo

Published Mar 1, 2002• 328 citations

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

DOI: 10.1103/physreva.65.032325

Related papers

Extending matchgates to universal quantum computation via the Hubbard model

Jia-Wei Ji, David L. Feder

Quantum circuits solely comprising matchgates can perform nontrivial (but nonuniversal) quantum algorithms. Because matchgates can be mapped to noninteracting fermions, these circuits can be efficiently simulated on a classical computer. Universal quantum computation is attainable by adding any nonmatchgate parity-preserving gate, from which one may infer that interacting fermions are natural candidates for universal quantum computation. We consider the quantum computational power of fermions hopping on a one-dimensional double-well lattice within the context of matchgates. In particular, we show that universal quantum computation can be implemented using spinless (spin-polarized) fermions and nearest-neighbor interactions, as well as with spin-half fermions with on-site interactions (i.e., the Hubbard model). We suggest that these schemes are currently within reach in the context of ultracold atomic gases.

Physical Review ANov 19, 20193 citations

Matchgates and classical simulation of quantum circuits

Richard Jozsa, Akimasa Miyake, ,

Let G(A, B) denote the 2-qubit gate which acts as the 1-qubit SU(2) gates A and B in the even and odd parity subspaces respectively, of two qubits. Using a Clifford algebra formalism we show that arbitrary uniform families of circuits of these gates, restricted to act only on nearest neighbour (n.n.) qubit lines, can be classically efficiently simulated. This reproduces a result originally proved by Valiant using his matchgate formalism, and subsequently related by others to free fermionic physics. We further show that if the n.n. condition is slightly relaxed, to allowing the same gates to act only on n.n. and next-n.n. qubit lines, then the resulting circuits can efficiently perform universal quantum computation. From this point of view, the gap between efficient classical and quantum computational power is bridged by a very modest use of a seemingly innocuous resource (qubit swapping). We also extend the simulation result above in various ways. In particular, by exploiting properties of Clifford operations in conjunction with the Jordan-Wigner representation of a Clifford algebra, we show how one may generalise the simulation result above to provide further classes of classically efficiently simulatable quantum circuits, which we call Gaussian quantum circuits. 1

Jan 1, 2008103 citations

Jordan-Wigner formalism for classical simulation beyond binary matchgates

Richard Jozsa, Akimasa Miyake

The unitary matchgate circuits introduced by Valiant provide an interesting class of quantum circuits that are classically efficiently simulatable. They were shown by Terhal & DiVincenzo and Knill to be related to the physics of non-interacting fermions. The Jordan-Wigner (JW) formalism provides an efficient classical simulation of the latter, which turns out to be equivalent to the restricted case of circuits of binary (2-qubit) matchgates. Valiant's formalism allows further unitary gates: in particular we may include arbitrary 1-qubit gates on the first qubit line at any stage within a binary matchgate circuit. In this note we show how the JW formalism may be extended to provide an efficient classical simulation of such extended circuits, and we show how the simulability also follows from some elementary Lie algebra theory. The essential ingredients have been indicated previously by Knill in a condensed and abstract form, and our purpose is to make these results explicit and transparent.

Nov 13, 20133 citations

Digital quantum simulation of fermionic models with a superconducting circuit

R. Barends, Lucas Lamata, J. Kelly +21 more

One of the key applications of quantum information is simulating nature. Fermions are ubiquitous in nature, appearing in condensed matter systems, chemistry and high energy physics. However, universally simulating their interactions is arguably one of the largest challenges, because of the difficulties arising from anticommutativity. Here we use digital methods to construct the required arbitrary interactions, and perform quantum simulation of up to four fermionic modes with a superconducting quantum circuit. We employ in excess of 300 quantum logic gates, and reach fidelities that are consistent with a simple model of uncorrelated errors. The presented approach is in principle scalable to a larger number of modes, and arbitrary spatial dimensions.

arXiv:1501.07703Nature CommunicationsJul 8, 2015337 citations

Matchgates and classical simulation of quantum circuits

Richard Jozsa, Akimasa Miyake

Let G ( A , B ) denote the two-qubit gate that acts as the one-qubit SU (2) gates A and B in the even and odd parity subspaces, respectively, of two qubits. Using a Clifford algebra formalism, we show that arbitrary uniform families of circuits of these gates, restricted to act only on nearest neighbour (n.n.) qubit lines, can be classically efficiently simulated. This reproduces a result originally proved by Valiant using his matchgate formalism, and subsequently related by others to free fermionic physics. We further show that if the n.n. condition is slightly relaxed, to allow the same gates to act only on n.n. and next n.n. qubit lines, then the resulting circuits can efficiently perform universal quantum computation. From this point of view, the gap between efficient classical and quantum computational power is bridged by a very modest use of a seemingly innocuous resource (qubit swapping). We also extend the simulation result above in various ways. In particular, by exploiting properties of Clifford operations in conjunction with the Jordan–Wigner representation of a Clifford algebra, we show how one may generalize the simulation result above to provide further classes of classically efficiently simulatable quantum circuits, which we call Gaussian quantum circuits.

arXiv:0804.4050Proceedings of the Royal Society A Mathematical Physical and Engineering SciencesJul 22, 2008208 citations

The Hubbard Model for Universal Quantum Computation

Jiawei Ji

Quantum circuits based only on matchgates are able to perform non-trivial (but not universal) quantum algorithms. Because matchgates can be mapped to non-interacting fermions, these circuits can be efficiently simulated on a classical computer. One can perform universal quantum computation by adding any non-matchgate parity-preserving gate, implying that interacting fermions are natural candidates for universal quantum computation. Most work to date has focused on Majorana fermions, which are difficult to realize and manipulate in the laboratory, despite the advantage of topologically protecting quantum information. We instead show that universal quantum computation can be implemented using interacting spinless (spin-polarized) fermions and further propose a scheme for achieving universal quantum computation with the Hubbard model, which may be realized in the laboratory based on current experimental techniques.

Jan 24, 20190 citations