Speaker
Description
The teleportation model of quantum computation introduced by Gottesman and Chuang [1] motivated the development of the Clifford hierarchy, an increasing sequence of sets of quantum gates critical for fault-tolerant quantum computation based on Clifford circuits. We propose an analogous hierarchy in the context of matchgate circuits, another restricted class of quantum circuits that can be efficiently classically simulated but are promoted to quantum universality via injection of matchgate "magic" states. We completely characterize the hierarchy in the 2-qubit case. For higher number of qubits, inspired by the work of de Silva [2], we propose a characterization of the matchgate hierarchy by leveraging the fermionic Stone-von Neumann theorem.
Apart from the well-known stabilizer subtheory, where circuits are built out of Clifford gates, another interesting restricted class of quantum circuits consists of those made out of a special set of two-qubit gates, called matchgates, restricted to act on nearest-neighbour (n.n.) qubits [3]. A matchgate is a two-qubit unitary $G(A, B) = A \oplus B$, where $A, B \in U(2)$ act on the even and odd parity subspaces respectively and satisfy $\det A = \det B$. The analogue of Gottesman-Knill theorem for matchgate circuits was shown by Valiant [4]. It asserts that circuits of n.n. matchgates can be classically efficiently simulated. Incidentally, such matchgate circuits have a profound physical significance in that they correspond to quantum evolutions of non-interacting ("free") fermions. This correspondence is given explicitly by the Jordan-Wigner (JW) transformation, a mapping between fermionic creation and annihilation operators and qubit operators. Like for Clifford circuits, a way to promote matchgate circuits to quantum universality is via access to a so-called "magic" state. Using a "gate-gadget" construction, it was shown that any pure fermionic state that is not Gaussian will do, i.e. any state that cannot be prepared by applying a matchgate circuit (evolution under quadratic fermionic Hamiltonian) to a computational basis state [5].
The technique of gate-gadget construction used for promoting restricted classes of circuits to quantum universality was introduced by Gottesman and Chuang [1] and is known as quantum gate teleportation. In that work, they also introduced the Clifford hierarchy: sets of unitary operations that can be executed fault-tolerantly on qubits encoded via a quantum error-correcting code. The level of a unitary in the hierarchy can be interpreted as a measure of the complexity of implementing it in this teleportation model of computation. The first level of the hierarchy is the Pauli group and second level is the Clifford group. Gates of the third level can be implemented using magic states of $2n$ qubits on Clifford circuits. Gates at higher levels of the hierarchy are implemented fault-tolerantly using the gate-gadget construction involving lower-level gates in the hierarchy. Mathematically, $k$-level gates are defined recursively as those gates that map Pauli operators to $(k-1)$-level gates under conjugation.
Inspired by the Clifford hierarchy, we develop an analogous hierarchy for matchgate circuit computation, which we dub the matchgate hierarchy. The first level of the hierarchy consists of linear combinations of Majorana fermion operators. The Majorana operators, denoted by $c_i$, are a set of $2n$ Hermitian operators that satisfy the canonical anticommutation relations (Majorana operators can be defined from fermionic creation and annihilation operators). The second level of the hierarchy consists of unitaries implemented by (generalized) matchgate circuits. Mathematically, these unitaries conjugate Majorana operators to linear combinations of Majoranas, with coefficients given by from a $2n \times 2n$ orthogonal matrix. We fully characterize the hierarchy in the 2-qubit case. Moreover, we propose an alternative gate teleportation protocol to the one used in [5] to implement the non-matchgate SWAP, as well as any higher-level non-matchgate, based on the teleportation protocol used in [1]. For higher numbers of qubits, inspired by [4], we propose a characterization of the gates at any level of the matchgate hierarchy based on the fermionic Stone-von Neumann theorem.
[1] Daniel Gottesman and Isaac L. Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402(6760):390–393, nov 1999.
[2] Nadish de Silva. Efficient quantum gate teleportation in higher dimensions. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 477(2251):20200865, jul 2021.
[3] Richard Jozsa and Akimasa Miyake. Matchgates and classical simulation of quantum circuits. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 464(2100):3089–3106, 2008.
[4] Leslie G. Valiant. Quantum computers that can be simulated classically in polynomial time. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC 2001), pages 114––123, 2001.
[5] Martin Hebenstreit, Richard Jozsa, Barbara Kraus, Sergii Strelchuk, and Mithuna Yoganathan. All pure fermionic non-Gaussian states are magic states for matchgate computations. Physical Review Letters, 123:080503, 2019.
