Finite automata for caching in matrix product algorithms

A diagram is introduced for visualizing matrix product states which makes transparent a connection between matrix product factorizations of states and operators, and complex weighted finite state automata. It is then shown how one can proceed in the opposite direction: writing an automaton that “generates” an operator gives one an immediate matrix product factorization of it. Matrix product factorizations have the advantage of reducing the cost of computing expectation values by facilitating caching of intermediate calculations. Thus our connection to complex weighted finite state automata yields insight into what allows for efficient caching in matrix product algorithms. Finally, these techniques are generalized to the case of multiple dimensions.

Figure 1

Matrix product diagrams. (a) Diagram representing the matrix product form of the W state. Each possible walk from left to right generates a term in the state, as illustrated in (b). (b) Example walk through the matrix product state illustrated in (a), which generates the term $\uparrow \uparrow \downarrow \uparrow$. (c) Mapping of edges to matrix elements.

Figure 2

Matrix product diagram for a magnetic field operator.

Figure 3

(Color online) Example finite state automaton which recognizes any string that ends in either two 0s or two 1’s.

Figure 4

(Color online) Examples of finite state automata that recognize quantum states. Finite state automaton recognizing (a) the W state and (b) a state with neighboring 1’s.

Figure 5

(Color online) Example of converting a finite state automaton (in this case, for the W state) into a matrix product state diagram. Note how some edges have been faded in order to indicate that they have been removed.

Figure 6

(Color online) An example of what happens to an automaton (a) and a matrix product state (b) when translational invariance is lost.

Figure 7

An example of using box-and-line notation to represent a network of tensors.

Figure 8

Box-and-line notation applied to matrix product states.(a) Matrix product state by itself. (b) Expectation of an arbitrary state. (c) Expectation of a matrix product operator.

Figure 9

Building transfer matrices for the expectation of a matrix product operator.

Figure 10

Formation of a matrix that allows us to express the expectation of $\mathcal{O}$ in quadratic form with respect to site 3.

Figure 11

Tensor contractions used to compute $L_3$ and $R_3$

Figure 12

Use of recursion and caching to calculate $L$ and $R$ in amortized $O\left(1\right)$ time at each site.

Figure 13

(Color online) A total ordering is imposed on the two-dimensional grid in (a); this allows us to write down a finite state automaton representation of the 4$X$ operator shown in (b), where the $X$’s represent the locations of the $X$ operators on the grid and at all other sites there are $I$ operators. (c) The resulting finite state automaton needed for the operator in (b) given the total ordering shown in (a) is less than ideal.

Figure 14

Tensor product state diagrams. (a) Diagram representing the tensor product structure of Eq. (5). (b) An invalid walk through (a). (c) An acceptable walk through (a).

Figure 15

Flow of information for finite signaling agent on two-dimensional grid.

Figure 16

Transitions experienced by an agent for two possible terms. (a) A term accepted by the agent. (b) A term rejected by the the agent due to intersecting boundaries.

Figure 17

Tensor network giving the expectation of some operator with respect to the site shown in Fig. 14a. Note that the index $l$ connects three tensors.

Figure 18

Use of recursion to calculate ${\mathcal{O}}_{33}$.