Extending matchgates to universal quantum computation via the Hubbard model

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.

Figure 1

The complete graph $G$ and the graph $G^{\prime }$ resulting from deleting the omittable node $T=\left\{2\right\}$. The input and output nodes are $X=\left\{1\right\}$ and $Y=\left\{4\right\}$, respectively.

Figure 2

The double-well lattice potential for spinless fermions. Each successive double well contains at most one fermion. Hopping with amplitude $t$ is only permitted between sites of a given double well $j$. Local potentials in the left ($\ell$) and right ($r$) sites are denoted by ${\mu }_{{\ell }_j}$ and ${\mu }_{r_j}$, respectively. The nearest-neighbor interaction strength between sites $i$ and $j$ is ${\lambda }_{i,j}$.

Figure 3

The matchgate graph representation of arbitrary single-qubit gates. The weights of the edges depend on the specific realization of the single-qubit operation.

Figure 4

The double-well lattice potential for spin-half fermions. Each successive double well contains at most one fermion with alternating spin projection. The spin-dependent hopping amplitudes are $t_{\sigma }$ and ${\tilde{t}}_{\sigma }$ for intra- and interwell hopping, respectively. Local spin-dependent potentials are ${\mu }_{j_{\sigma }}$, and on-site interactions are denoted by $g$.