Systematic dimensionality reduction for continuous-time quantum walks of interacting fermions

To extend the continuous-time quantum walk (CTQW) to simulate $P$ distinguishable particles on a graph $G$ composed of $N$ vertices, the Hamiltonian of the system is expanded to act on an $N^P$-dimensional Hilbert space, in effect, simulating the multiparticle CTQW on graph $G$ via a single-particle CTQW propagating on the Cartesian graph product $G^{\square P}$. The properties of the Cartesian graph product have been well studied, and classical simulation of multiparticle CTQWs are common in the literature. However, the above approach is generally applied as is when simulating indistinguishable particles, with the particle statistics then applied to the propagated $N^P$ state vector to determine walker probabilities. We address the following question: How can we modify the underlying graph structure $G^{\square P}$ in order to simulate multiple interacting fermionic CTQWs with a reduction in the size of the state space? In this paper, we present an algorithm for systematically removing “redundant” and forbidden quantum states from consideration, which provides a significant reduction in the effective dimension of the Hilbert space of the fermionic CTQW. As a result, as the number of interacting fermions in the system increases, the classical computational resources required no longer increases exponentially for fixed $N$.

Figure 1

Four-vertex star graph.

Figure 2

(a) Cartesian product of the star graph with itself, $G\square G$. (b) Reduced antisymmetric two-fermion star graph $\tilde{G}$. The edges $\left(\right|12\rangle ,|23\rangle ), \left(\right|12\rangle ,|24\rangle )$, and $\left(\right|13\rangle ,|34\rangle )$ have an edge weighting of $-1$ due to particle exchange. Note that we use the vertex labeling $|ij\rangle$ as shorthand to indicate the allowed fermionic state $\left(\right|i,j\rangle -|j,i\rangle )/\sqrt{2}\in |F_n\rangle$.

Figure 3

Reduced fermionic graph $\tilde{G}$ representing (a) one-, (b) two-, (c) three-, and (d) four-fermion CTQWs on a four-vertex star graph with nearest-neighbor interactions. Edges marked $-1$ have an edge weighting of $-1$, while unlabeled edges have an edge weighting of 1. Self-loops represent nearest-neighbor interactions of strength $\alpha$ and have an edge weighting of $\alpha$.

Figure 4

Reduced fermionic graph $\tilde{G}$ representing (a) one-, (b) two-, (c) three-, and (d) four-fermion CTQWs on a five-vertex cycle graph with nearest-neighbor interactions. Edges marked $-1$ have an edge weighting of $-1$, while unlabeled edges have an edge weighting of 1. Self-loops represent nearest-neighbor interactions of strength $\alpha$ and have an edge weighting of $\alpha$.

Figure 5

Wall time required to construct the $P$-fermion CTQW Hamiltonian on (a) $N=15$ and (b) $N=20$ vertex graphs with nearest-neighbor interactions. The solid black (upper) line indicates the Kronecker sum approach $H^{\oplus P}+\mathrm{\Gamma }$ and the solid red (lower) line indicates the reduced fermion graph approach detailed in Programs 1 and 2, for a randomly generated Erdős-Rényi graph $G(N,0.3)$. The corresponding dashed lines represent regression fits of the form $a{N}^P$ (upper, black dashed line), and $aP(P-1)\left(\begin{array}{c}N\\ P\end{array}\right)$ (lower, red dashed line) for constant $a$.

Figure 6

Qubits required to simulate a $P$-fermion CTQW walking on a graph of $N=50$ vertices, by either (a) introducing additional particles to the system (black solid line) or (b) performing a single-particle walk on the equivalent reduced fermionic graph (red dashed line).