Tree tensor network approach to simulating Shor's algorithm

Constructively simulating quantum systems furthers our understanding of qualitative and quantitative features which may be analytically intractable. In this paper, we directly simulate and explore the entanglement structure present in the paradigmatic example for exponential quantum speedups: Shor's algorithm. To perform our simulation, we construct a dynamic tree tensor network which manifestly captures two salient circuit features for modular exponentiation. These are the natural two-register bipartition and the invariance of entanglement with respect to permutations of the top-register qubits. Our construction help identify the entanglement entropy properties, which we summarize by a scaling relation. Further, the tree network is efficiently projected onto a matrix product state from which we efficiently execute the quantum Fourier transform. Future simulation of quantum information states with tensor networks exploiting circuit symmetries is discussed.

Figure 1

Schematic of Shor's algorithm with the ME (QFT) components highlighted in yellow (blue) boxes. Equation (1) describes the state of the system one time step before the bottom register measurements preceding the ME subcircuit.

Figure 2

Intermediate virtual networks for (b)–(d) between the application of a controlled modular multiplication gate (a) and the updated tree network (e). Red (black) lines denote physical (virtual) degrees of freedom. The thick red line at the base of the tree denotes the $2^l$-dimensional qudit bottom register state. Top register qubits are represented by thin red lines at the bottom of the tree. The dashed black line denotes the bipartition defined by Eq. (1). The scissors icon and dashed purple lines (purple box) denote the bipartition chosen for tensor decompositions (contraction) generating the next tree configuration.

Figure 3

Tree tensor network decomposition of $|\mathrm{\Psi }\rangle$ from Eq. (1) for an $l=12$ size system with $N=3403=41\times 83$, $x=346$, and cyclic order $r=410$. Edge widths are ${log}_2\left(d_i\right)+1$ where $d_i$ is the $i\mathrm{th}$ bond dimension which has been labeled. Top qubit (qudit) physical degrees of freedom appear as red edges along the bottom (top). Highlighted regions are entangled with their complement by a common parent branch whose dimension follows Eq. (2).

Figure 4

Entanglement as quantified by MPS auxiliary bond dimensions for an $N=1763,l=12$ system. The virtual bond dimensions and entanglement grow exponentially between adjacent bipartitions for the first few sites from both the left and right end points and are saturated in the bulk of the system by the characteristic modular periodicity $\tilde{r}$.