Editing Density matrix renormalization group

{{short description|Numerical variational technique}}
{{More footnotes|date=July 2019}}
The '''density matrix renormalization group''' ('''DMRG''') is a numerical [[Variational method (quantum mechanics)|variational]] technique devised to obtain the [[Macroscopic scale|low-energy physics]] of [[Many-body problem|quantum many-body systems]] with high accuracy. As a [[Variational method (quantum mechanics)|variational method]], DMRG is an efficient algorithm that attempts to find the lowest-energy [[matrix product state]] wavefunction of a [[Hamiltonian (quantum mechanics)|Hamiltonian]]. It was invented in 1992 by [[Steven R. White]] and it is nowadays the most efficient method for 1-dimensional systems.<ref>{{Citation|last=Nakatani|first=Naoki|title=Matrix Product States and Density Matrix Renormalization Group Algorithm|date=2018|url=http://dx.doi.org/10.1016/b978-0-12-409547-2.11473-8|work=Reference Module in Chemistry, Molecular Sciences and Chemical Engineering|publisher=Elsevier|doi=10.1016/b978-0-12-409547-2.11473-8|isbn=978-0-12-409547-2|access-date=2021-04-21|url-access=subscription}}</ref>

== History ==
The first application of the DMRG, by [[Steven R. White]] and [[Reinhard Noack]], was a ''toy model'': to find the spectrum of a [[Spin (physics)|spin]] 0 particle in a 1D box.{{When|date=July 2023}} This model had been proposed by [[Kenneth G. Wilson]] as a test for any new [[renormalization group]] method, because they all happened to fail with this simple problem.{{When|date=July 2023}} The DMRG overcame the problems of previous [[renormalization group]] methods by connecting two blocks with the two sites in the middle rather than just adding a single site to a block at each step as well as by using the [[density matrix]] to identify the most important states to be kept at the end of each step. After succeeding with the ''toy model'', the DMRG method was tried with success on the [[Heisenberg model (quantum)|quantum Heisenberg model]].
==Principle==

The main problem of [[Many-body problem|quantum many-body physics]] is the fact that the [[Hilbert space]] grows exponentially with size. In other words if one considers a lattice, with some Hilbert space of dimension <math>d</math> on each site of the lattice, then the total Hilbert space would have dimension <math>d^{N}</math>, where <math>N</math> is the number of sites on the lattice. For example, a [[spin-1/2]] chain of length&nbsp;''L'' has 2<sup>''L''</sup> degrees of freedom. The DMRG is an [[iterative]], variational method that reduces effective [[degrees of freedom]] to those most important for a target state. The state one is most often interested in is the [[ground state]].

After a warmup cycle{{Definition needed|date=October 2020}}, the method splits the system into two subsystems, or blocks, which need not have equal sizes, and two sites in between. A set of ''representative states'' has been chosen for the block during the warmup. This set of left blocks&nbsp;+&nbsp;two sites&nbsp;+&nbsp;right blocks is known as the '''superblock'''. Now a candidate for the ground state of the superblock, which is a reduced version of the full system, may be found. It may have a rather poor accuracy, but the method is [[iterative]] and improves with the steps below.

[[Image:Dmrg1.png|thumb|300px|right|Decomposition of the system into left and right blocks, according to DMRG.]]

The candidate ground state that has been found is projected into the [[Linear subspace|Hilbert subspace]] for each block using a [[density matrix]], hence the name. Thus, the ''relevant states'' for each block are updated. {{Explain|date=October 2020}}

Now one of the blocks grows at the expense of the other and the procedure is repeated. When the growing block reaches maximum size, the other starts to grow in its place. Each time we return to the original (equal sizes) situation, we say that a ''sweep'' has been completed. Normally, a few sweeps are enough to get a precision of a part in&nbsp;10<sup>10</sup> for a 1D lattice.

[[Image:Dmrg2.png|thumb|300px|right|The DMRG sweep.]]

==Implementation guide==

A practical implementation of the DMRG algorithm is a lengthy work{{Opinion|date=October 2020}}. A few of the main computational tricks are these:

* Since the size of the renormalized Hamiltonian is usually in the order of a few or tens of thousand while the sought eigenstate is just the ground state, the ground state for the superblock is obtained via iterative algorithm such as the [[Lanczos algorithm]] of matrix diagonalization.  Another choice is the [[Arnoldi iteration|Arnoldi method]], especially when dealing with non-hermitian matrices.
* The Lanczos algorithm usually starts with the best guess of the solution. If no guess is available a random vector is chosen. In DMRG, the ground state obtained in a certain DMRG step, suitably transformed, is a reasonable guess and thus works significantly better than a random starting vector at the next DMRG step.
* In systems with symmetries, we may have conserved quantum numbers, such as total spin in a Heisenberg model. It is convenient to find the ground state within each of the sectors into which the Hilbert space is divided.

==Applications==

The DMRG has been successfully applied to get the low energy properties of spin chains: [[Ising model]] in a transverse field, [[Heisenberg model (quantum)|Heisenberg model]], etc., fermionic systems, such as the [[Hubbard model]], problems with impurities such as the [[Kondo effect]], [[boson]] systems, and the physics of [[quantum dots]] joined with [[quantum wire]]s. It has been also extended to work on [[tree graph]]s, and has found applications in the study of [[dendrimers]]. For 2D systems with one of the dimensions much larger than the other DMRG is also accurate, and has proved useful in the study of ladders.

The method has been extended to study equilibrium [[statistical physics]] in 2D, and to analyze [[non-equilibrium statistical mechanics|non-equilibrium]] phenomena in 1D.

The DMRG has also been applied to the field of [[Quantum Chemistry|quantum chemistry]] to study strongly correlated systems.

== Example: Quantum Heisenberg model ==
Let us consider an "infinite" DMRG algorithm for the <math>S=1</math> antiferromagnetic [[Quantum Heisenberg model|quantum Heisenberg chain]]. The recipe can be applied for every translationally invariant one-dimensional [[Lattice (group)|lattice]].

DMRG  is a [[Renormalization group|renormalization-group]] technique because it offers an efficient truncation of the [[Hilbert space]] of one-dimensional quantum systems.

=== Starting point ===
To simulate an infinite chain, start with four sites. The first is the ''block site'', the last the ''universe-block site''  and the remaining are the ''added sites'', the right one is added to the universe-block site and the other to the block site.

The Hilbert space for the single site is <math>\mathfrak{H}</math> with the base <math>\{|S,S_z\rangle\}\equiv\{|1,1\rangle,|1,0\rangle,|1,-1\rangle\}</math>. With this base the [[Spin (physics)|spin]] operators are   <math>S_x</math>, <math>S_y</math> and <math>S_z</math> for the single site. For every block, the two blocks and the two sites, there is its own Hilbert space <math>\mathfrak{H}_b</math>, its base <math>\{|w_i\rangle\}</math> (<math>i:1\dots \dim(\mathfrak{H}_b)</math>)and its own operators<math display="block">O_b:\mathfrak{H}_b\rightarrow\mathfrak{H}_b</math>where

* block: <math>\mathfrak{H}_B</math>, <math>\{|u_i\rangle\}</math>, <math>H_B</math>, <math>S_{x_B}</math>, <math>S_{y_B}</math>, <math>S_{z_B}</math>
* left-site: <math>\mathfrak{H}_l</math>, <math>\{|t_i\rangle\}</math>, <math>S_{x_l}</math>, <math>S_{y_l}</math>, <math>S_{z_l}</math>
* right-site: <math>\mathfrak{H}_r</math>, <math>\{|s_i\rangle\}</math>, <math>S_{x_r}</math>, <math>S_{y_r}</math>, <math>S_{z_r}</math>
* universe: <math>\mathfrak{H}_U</math>, <math>\{|r_i\rangle\}</math>, <math>H_U</math>, <math>S_{x_U}</math>, <math>S_{y_U}</math>, <math>S_{z_U}</math>

At the starting point all four Hilbert spaces are equivalent to <math>\mathfrak{H}</math>, all spin operators are equivalent to <math>S_x</math>, <math>S_y</math> and <math>S_z</math> and <math>H_B=H_U=0</math>. In the following iterations, this is only true for the left and right sites.

=== Step 1: Form the Hamiltonian matrix for the superblock ===
The ingredients are the four block operators and the four universe-block operators, which at the first iteration are <math>3\times3</math> [[Matrix (mathematics)|matrices]], the three left-site spin operators and the three right-site spin operators, which are always <math>3\times3</math> matrices. The [[Hamiltonian system|Hamiltonian]] matrix of the ''superblock''  (the chain), which at the first iteration has only four sites, is formed by these operators. In the Heisenberg antiferromagnetic S=1 model the Hamiltonian is:

<math>
\mathbf{H}_{SB}=-J\sum_{\langle i,j\rangle}\mathbf{S}_{x_i}\mathbf{S}_{x_j}+\mathbf{S}_{y_i}\mathbf{S}_{y_j}+\mathbf{S}_{z_i}\mathbf{S}_{z_j}
</math>

These operators live in the superblock state space: <math>\mathfrak{H}_{SB}=\mathfrak{H}_B\otimes\mathfrak{H}_l\otimes\mathfrak{H}_r\otimes\mathfrak{H}_U</math>, the base is <math>\{|f\rangle=|u\rangle\otimes|t\rangle\otimes|s\rangle\otimes|r\rangle\}</math>. For example: (convention):

<math>
|1000\dots0\rangle\equiv|f_1\rangle=|u_1,t_1,s_1,r_1\rangle\equiv|100,100,100,100\rangle
</math>

<math>
|0100\dots0\rangle\equiv|f_2\rangle=|u_1,t_1,s_1,r_2\rangle\equiv|100,100,100,010\rangle
</math>

The Hamiltonian in the ''DMRG form'' is  (we set <math>J=-1</math>):

<math>
\mathbf{H}_{SB}=\mathbf{H}_B+\mathbf{H}_U+\sum_{\langle i,j\rangle}\mathbf{S}_{x_i}\mathbf{S}_{x_j}+\mathbf{S}_{y_i}\mathbf{S}_{y_j}+\mathbf{S}_{z_i}\mathbf{S}_{z_j}
</math>

The operators are <math>(d*3*3*d)\times(d*3*3*d)</math> matrices, <math>d=\dim(\mathfrak{H}_B)\equiv\dim(\mathfrak{H}_U)</math>, for example:

<math>
\langle f|\mathbf{H}_B|f'\rangle\equiv\langle u,t,s,r|H_B\otimes\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}|u',t',s',r'\rangle
</math>

<math>
\mathbf{S}_{x_B}\mathbf{S}_{x_l}=S_{x_B}\mathbb{I}\otimes\mathbb{I}S_{x_l}\otimes\mathbb{I}\mathbb{I}\otimes\mathbb{I}\mathbb{I}=S_{x_B}\otimes S_{x_l}\otimes\mathbb{I}\otimes\mathbb{I}
</math>

=== Step 2: Diagonalize the superblock Hamiltonian ===
At this point you must choose the [[Eigenvalue, eigenvector and eigenspace|eigenstate]] of the Hamiltonian for which some [[Observable|observables]] is calculated, this is the ''target state'' . At the beginning you can choose the [[Stationary state|ground state]] and use some advanced algorithm to find it, one of these is described in:

* ''The Iterative Calculation of a Few of the Lowest Eigenvalues and Corresponding [[Eigenvalue, eigenvector and eigenspace|Eigenvectors]] of Large Real-[[Symmetric matrix|Symmetric Matrices]]'', [[Ernest R. Davidson]]; Journal of Computational Physics 17, 87-94 (1975)

This step is the most time-consuming part of the algorithm.

If <math>|\Psi\rangle=\sum\Psi_{i,j,k,w}|u_i,t_j,s_k,r_w\rangle</math> is the target state, [[Expected value|expectation value]] of various operators can be measured at this point using <math>|\Psi\rangle</math>.

=== Step 3: Reduce density matrix ===
Form the reduced density matrix <math>\rho</math> for the first two block system, the block and the left-site. By definition it is the <math>(d*3)\times(d*3)</math> matrix: <math>
\rho_{i,j;i',j'}\equiv\sum_{k,w}\Psi_{i,j,k,w}\Psi^*_{i',j',k,w}
</math>

[[Matrix diagonalization|Diagonalize]] <math>\rho</math> and form the <math>m\times (d*3)</math> matrix <math>T</math>, which rows are the <math>m</math> eigenvectors associated with the <math>m</math> largest eigenvalues <math>e_\alpha</math> of <math>\rho</math>. So <math>T</math> is formed by the most significant eigenstates of the reduced density matrix. You choose <math>m</math> looking to the parameter <math>P_m\equiv\sum_{\alpha=1}^m e_\alpha</math>: <math>1-P_m\cong 0</math>.

=== Step 4: New block and universe-block operators ===
Form the <math>(d*3)\times(d*3)</math> matrix representation of operators for the system composite of the block and left-site, and for the system composite of right-site and universe-block, for example:

<math>
H_{B-l}=H_B\otimes\mathbb{I}+S_{x_B}\otimes S_{x_l}+S_{y_B}\otimes S_{y_l}+S_{z_B}\otimes S_{z_l}
</math>

<math>
S_{x_{B-l}}=\mathbb{I}\otimes S_{x_l}
</math>

<math>
H_{r-U}=\mathbb{I}\otimes H_U+S_{x_r}\otimes S_{x_U}+S_{y_r}\otimes S_{y_U}+S_{z_r}\otimes S_{z_U}
</math>

<math>
S_{x_{r-U}}=S_{x_r}\otimes\mathbb{I}
</math>

Now, form the <math>m\times m</math> matrix representations of the new block and universe-block operators, form a new block by changing basis with the transformation <math>T</math>, for example:<math display="block">\begin{matrix}
&H_B=TH_{B-l}T^\dagger

&S_{x_B}=TS_{x_{B-l}}T^\dagger

\end{matrix}</math>At this point the iteration is ended and the algorithm goes back to step 1.

The algorithm stops successfully when the observable converges to some value.

==Matrix product ansatz==

The success of the DMRG for 1D systems is related to the fact that it is a variational method within the space of [[matrix product state]]s (MPS). These are states of the form

: <math>|\Psi\rangle = 
\sum_{s_1\cdots s_N} \operatorname{Tr}(A^{s_1}\cdots A^{s_N}) | s_1 \cdots s_N\rangle</math>

where <math>s_1\cdots s_N</math> are the values of the e.g. ''z''-component of the spin in a spin chain, and the ''A''<sup>''s''<sub>''i''</sub></sup> are matrices of arbitrary dimension&nbsp;''m''.  As ''m''&nbsp;→&nbsp;∞, the representation becomes exact. This theory was exposed by S. Rommer and S. Ostlund in [https://arxiv.org/abs/cond-mat/9606213].

In quantum chemistry application, <math> s_i </math> stands for the four possibilities of the projection of the spin quantum number of the two electrons that can occupy a single orbital, thus <math> s_i = | 00\rangle, |10\rangle, |01\rangle, |11\rangle </math>, where the first (second) entry of these kets corresponds to the spin-up(down) electron. In quantum chemistry, <math> A^{s_1} </math> (for a given <math> s_i </math>) and <math> A^{s_N} </math> (for a given <math> s_N </math>) are traditionally chosen to be row and column matrices, respectively. This way, the result of <math> A^{s_1} \ldots A^{s_N} </math> is a scalar value and the trace operation is unnecessary. <math> N </math> is the number of sites (the orbitals basically) used in the simulation.

The matrices in the MPS ansatz are not unique, one can, for instance, insert <math> B^{-1} B </math> in the middle of <math>A^{s_i}A^{s_{i+1}}</math>, then define <math>\tilde{A}^{s_i} = A^{s_i}B^{-1}</math> and <math>\tilde{A}^{s_{i+1}} = BA^{s_{i+1}}</math>, and the state will stay unchanged. Such gauge freedom is employed to transform the matrices into a canonical form. Three types of canonical form exist: (1) left-normalized form, when 

:<math>\sum_{s_i} \left(\tilde{A}^{s_i}\right)^\dagger \tilde{A}^{s_i} = I</math>
for all <math>i</math>, (2) right-normalized form, when
:<math>\sum_{s_i} \tilde{A}^{s_i} \left(\tilde{A}^{s_i}\right)^\dagger  = I </math>
for all <math>i</math>, and (3) mixed-canonical form when both left- and right-normalized matrices exist among the <math>N</math> matrices in the above MPS ''ansatz''.

The goal of the DMRG calculation is then to solve for the elements of each of the <math> A^{s_i} </math> matrices. The so-called one-site and two-site algorithms have been devised for this purpose. In the one-site algorithm, only one matrix (one site) whose elements are solved for at a time. Two-site just means that two matrices are first contracted (multiplied) into a single matrix, and then its elements are solved. The two-site algorithm is proposed because the one-site algorithm is much more prone to getting trapped at a local minimum. Having the MPS in one of the above canonical forms has the advantage of making the computation more favorable - it leads to the ordinary eigenvalue problem. Without canonicalization, one will be dealing with a generalized eigenvalue problem.

==Extensions==

In 2004 the [[time-evolving block decimation]] method was developed to implement real-time evolution of matrix product states. The idea is based on the classical simulation of a [[quantum computer]]. Subsequently, a new method was devised to compute real-time evolution within the DMRG formalism - See the paper by A. Feiguin and S.R. White [https://arxiv.org/abs/cond-mat/0502475].

In recent years, some proposals to extend the method to 2D and 3D have been put forward, extending the definition of the matrix product states. See this paper by [[Frank Verstraete|F. Verstraete]] and [[Juan Ignacio Cirac Sasturain|I. Cirac]], [https://arxiv.org/abs/cond-mat/0407066].

==Further reading==

* The original paper, by S. R. White, [https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.69.2863] or [https://web.archive.org/web/20070721172908/http://hedrock.ps.uci.edu/dmrgpaper/dmrgpap.pdf]
* A textbook on DMRG and its origins: https://www.springer.com/gp/book/9783540661290
* A broad review, by [[Karen Hallberg]], [https://arxiv.org/abs/cond-mat/0609039].
* Two reviews by Ulrich Schollwöck, one discussing the original formulation [https://arxiv.org/abs/cond-mat/0409292], and another in terms of matrix product states [https://arxiv.org/abs/1008.3477]
* The Ph.D. thesis of Javier Rodríguez Laguna [https://arxiv.org/abs/cond-mat/0207340].
* An introduction to DMRG and its time-dependent extension [https://arxiv.org/abs/cond-mat/0603842].
* A list of DMRG e-prints on arxiv.org [http://quattro.phys.sci.kobe-u.ac.jp/dmrg/condmat.html].
* A review article on DMRG for [[ab initio quantum chemistry methods|ab initio quantum chemistry]] [https://arxiv.org/abs/1407.2040].
* An introduction video on DMRG for [[ab initio quantum chemistry methods|ab initio quantum chemistry]] [https://www.youtube.com/watch?v=U96atV5Akx4].

* {{cite journal |last1=White |first1=Steven R. |last2=Huse |first2=David A. |date=1993-08-01 |title=Numerical renormalization-group study of low-lying eigenstates of the antiferromagnetic S=1 Heisenberg chain |journal=Physical Review B |publisher=American Physical Society (APS) |volume=48 |issue=6 |pages=3844–3852 |bibcode=1993PhRvB..48.3844W |doi=10.1103/physrevb.48.3844 |issn=0163-1829 |pmid=10008834}}

==Related software==
* [https://people.smp.uq.edu.au/IanMcCulloch/mptoolkit/index.php The Matrix Product Toolkit]: A free [[GPL]] set of tools for manipulating finite and infinite matrix product states written in [[C++]] [https://people.smp.uq.edu.au/IanMcCulloch/mptoolkit/index.php]
* [https://gitlab.com/uni10/uni10/ Uni10]: a library implementing numerous tensor network algorithms (DMRG, TEBD, MERA, PEPS ...) in [[C++]] 
* Powder with Power: a free distribution of time-dependent DMRG code written in [[Fortran]] [http://qti.sns.it/dmrg/phome.html] {{Webarchive|url=https://web.archive.org/web/20171204225717/http://qti.sns.it/dmrg/phome.html |date=2017-12-04 }}
* The ALPS Project: a free distribution of time-independent DMRG code and [[Quantum Monte Carlo]] codes written in [[C++]] [http://alps.comp-phys.org]
* [https://g1257.github.io/dmrgPlusPlus/index.html DMRG++]: a free implementation of DMRG written in [[C++]] [https://g1257.github.io/dmrgPlusPlus/index.html]
* The [http://itensor.org/ ITensor] (Intelligent Tensor) Library: a free library for performing tensor and matrix-product state based DMRG calculations written in [[C++]] [http://itensor.org/]
* [https://sourceforge.net/projects/openmps/ OpenMPS]: an open source DMRG implementation based on Matrix Product States written in Python/Fortran2003. [https://sourceforge.net/projects/openmps/]
* Snake DMRG program:  open source DMRG, tDMRG and finite temperature DMRG program written in C++ [https://github.com/entron/snake-dmrg]
* [https://github.com/SebWouters/CheMPS2 CheMPS2]: open source (GPL) spin-adapted DMRG code for [[ab initio quantum chemistry methods|ab initio quantum chemistry]] written in C++ [https://dx.doi.org/10.1016/j.cpc.2014.01.019]
* [https://github.com/sanshar/Block Block]: open source DMRG framework for quantum chemistry and model Hamiltonians. Supports SU(2) and general non-Abelian symmetries. Written in C++.
* [https://pypi.org/project/block2/ Block2]: An efficient [[Parallel algorithm|parallel]] implementation of DMRG, dynamical DMRG, tdDMRG, and finite temperature DMRG for quantum chemistry and models. Written in [[Python (programming language)|Python]]/[[C++]].

==See also==
*[[Quantum Monte Carlo]]
*[[Time-evolving block decimation]]
*[[Configuration interaction]]

==References==
{{reflist}}

[[Category:Theoretical physics]]
[[Category:Computational physics]]
[[Category:Statistical mechanics]]