Matchgates and classical simulation of quantum circuits

By Richard Jozsa, Akimasa Miyake. Proceedings of the Royal Society A, 2008

309 citations recorded by the source corpus.

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.

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

View Paper: https://www.semanticscholar.org/paper/e67e38433849ee56d7a144fd42440db5668bdf45

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

Barren plateaus in variational quantum computing (2024, unknown): “One can explicitly verify this by using the Baker–Campbell–Hausdorff formula to re-express the composition of layers as the exponential of a linear combination of the nested commutators of the generators, which by definition belongs in g .”
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].”