Skip to content

tensornetwork.md

Latest commit

 

History

History
207 lines (172 loc) · 7.31 KB

tensornetwork.md

File metadata and controls

207 lines (172 loc) · 7.31 KB

Tensor networks

1. Mathematic foundation

Definition

A tensor network is a triple ${\Lambda, {T^{(i)}_{\sigma_i}}, \sigma_0}$1, where

  • $\Lambda$ is a set of indices,
  • ${T^{(i)}_{\sigma_i}}$ is a set of tensors and the associated indices, and
  • $\sigma_0$ is the output indices.

The contraction of a tensor network is defined as

$${\rm con}(\Lambda, \{T^{(i)}_{\sigma_i}\}, \sigma_0) = \sum_{\Lambda\setminus\sigma_0} \prod_{i=1}^m T^{(i)}_{\sigma_i}$$

Diagrammatic representation

We use a node to denote a tensor and a line to denote an index.

Example 1.1: Trace Permutation

Diagram:

Math:

$${\rm con}(\{i, j, k\}, \{A_{ij}, B_{jk}, C_{ki}\}, \{\})$$

Julia:

ein"ij,jk,ki->"(A, B, C)

Example 1.2: SVD decomposition

Diagram:

Math:

$${\rm con}(\{i, j, k\}, \{U_{ij}, S_{j}, V_{jk}\}, \{i, k\})$$

Julia:

ein"ij,j,jk->ik"(U, S, V)

Contraction order

  1. A good contraction order reduces: space complexity, time complexity and read-write complexity
  2. The space complexity of a contraction order is related to tree width in graph theory
  3. Algorithms to find the optimal contraction order, Please check: https://github.com/TensorBFS/OMEinsumContractionOrders.jl

Example 1.3: Contraction order

Q1: What is the Julia code for the above diagram? $$ \begin{align} \begin{split} &{\rm con}({i,j,k,l,m,n}, \ & \quad\quad{A_{{i, l}}, B_{{l}}, C_{{k, j, l}}, D_{{k, m, n}}, E_{{j, n}}},\ & \quad\quad{i,m}) \ & =\sum_{j,k,l,n}A_{{i,l}} B_{{l}} C_{{k,l}} D_{{k, m}} E_{{j, n}}. \end{split} \end{align} $$

Q2: Given the contraction tree below, what is the corresponding time complexity, space complexity and read-write complexity?

Slicing technique can be used to reduce the space complexity of the contraction order.

Example 3: Fast Fourier Transform (FFT)

2. Matrix Product States (MPS)

A matrix product state is a tensor network representation of a quantum state.

Q: What is the rank of the above MPS? Q: Let the virtual bond dimension be $D$, what is the space complexity of the MPS?

  1. Example: product state
  2. Example: GHZ state
  3. Example: AKLT state (Ref. 2 P31)

Entanglement entropy and the area law

  1. Every multipartite quantum state has a Schmidt decomposition
$$\ket{\psi} = \sum_{i} \lambda_i \ket{i}_A \ket{i}_B,\\\ \sum_{i} \lambda_i^2 = 1, \lambda_i \geq 0.$$
  1. Schmidt decomposition can be related to singular value decomposition (SVD).
  2. The entanglement entropy is defined as
$$S = -\sum_i \lambda_i^2 \log_2 \lambda_i^2.$$
  1. Reduced density matrix - the tensor network representation
$$\rho_A = \text{Tr}_B \ket{\psi}\bra{\psi}.$$

  1. The eigenvalues of the reduced density matrix are the squares of the Schmidt coefficients.

  2. Schmidt decomposition

  3. Systems with area law

  4. Compression: How does truncation error relate to the expectation value?

Fidelity & expectation value

  1. Norm of the state
  2. Reduced density matrix

Canonical form and Vidal form

Time evolution

  1. Baker–Campbell–Hausdorff (BCH) formula and Trotter decomposition The dual of the BCH formula is the Zassenhaus formula 
    e^{t(X+Y)}=e^{tX}~e^{tY}~e^{-{\frac {t^{2}}{2}}[X,Y]}~e^{{\frac {t^{3}}{6}}(2[Y,[X,Y]]+[X,[X,Y]])}~e^{{\frac {-t^{4}}{24}}([[[X,Y],X],X]+3[[[X,Y],X],Y]+3[[[X,Y],Y],Y])}\cdots
    When $dt$ is small, the first order Trotter decomposition is accurate 
    e^{dt(X+Y)} \approx e^{dtX} e^{dtY}
  2. Time-evolving block decimation (TEBD) Consider the time evolution of a local Hamiltonian
$$H = \sum_i h_{i,i+1}$$

where $h_{i, i+1}$ is a local Hamiltonian. The time evolution operator is

$$U(dt) = e^{-iHdt} \approx \prod_i e^{-ih_{i,i+1} dt}$$

Video

Automatic differentiation

Differentiating a tensor in a tensor network contraction is equivalent to removing the tensor.

Adjoint:

$$\overline{x} = \frac{\partial \mathcal{L}}{\partial x}$$

where $\mathcal{L}$ is the loss function and $x$ is a vector.

Differential form:

$$\delta \mathcal{L} = \overline{x}^T \delta x$$

Backward rule of einsum: Consider

$$T^{(0)} = {\rm con}(\Lambda, \{T^{(i)}_{\sigma_i} \mid i=1,\ldots,m\}, \sigma_0)$$

where $\Lambda = \cup_{i=0}^m \sigma_i$ is a set of indices, $T^{(i)}$ are tensors, and $\sigma_0$ is the output index.

$$\delta T^{(0)} = \sum_k{\rm con}(\Lambda, \{T^{(i)}_{\sigma_i} \mid i=1,\ldots,m, i\neq k\} \cup \{\delta T^{(k)}_{\sigma_k}\}, \sigma_0)$$

The differential form is:

$$\delta \mathcal{L} = \sum_{k=1}^m{\rm con}(\sigma_k, \{\delta T^{(k)}_{\sigma_k}, \overline T_{\sigma_k}\}, \emptyset) = {\rm con}(\sigma_0, \{\delta T^{(0)}_{\sigma_0}, \overline T_{\sigma_0}\}, \emptyset)$$

We have

$$\overline T^{(k)}_{\sigma_k} = {\rm con}(\Lambda, \{T^{(i)}_{\sigma_i} \mid i=1,\ldots,m, i\neq k\} \cup \{\overline T^{(0)}_{\sigma_0}\}, \sigma_k)$$

Q: How about complex numbers?

  • Rule based AD: derive the rules using the Wirtinger calculus
  • Source-to-source AD: same as real numbers

From Quantum Circuit to Tensor Networks

  1. Tensor network based simulation
  2. Special gates
  3. Expectation value
  4. ZX-calculus
  5. Optimal contraction order and treewidth
  6. Entanglement propagation
    1. Lieb Robinson bound, check entanglement entropy

Classical Tensor Networks

  1. Tensor renormalization group (TRG)
  2. Probabilistic graphical models
  3. Combinatorial optimization
    1. Example: Spin-glass
    2. Example: Maximum independent set
    3. Example: Circuit SAT
      1. Is it possible to reduce spin-glass to circuit SAT?
  4. Generic tensor networks
  5. Overlap gap property
    1. Discuss hardest instance complexity and average complexity
  6. From factoring to independent set problem

References

Footnotes

  1. Roa-Villescas, M., Gao, X., Stuijk, S., Corporaal, H., Liu, J.-G., 2024. Probabilistic Inference in the Era of Tensor Networks and Differential Programming. https://doi.org/10.48550/arXiv.2405.14060 ↩

  2. Schollwöck, U., 2011. Schollwöck, U. (2011). The density-matrix renormalization group in the age of matrix product states. Annals of Physics 326, 96–192. https://doi.org/10.1016/j.aop.2010.09.012 ↩