Time-evolving Block Decimation

Website Links For Block

Information About Time-evolving Block Decimation

	CATEGORIES ABOUT TIME-EVOLVING BLOCK DECIMATION
	quantum mechanics
	computational physics

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME
	MORE SHOPPING...

It is dubbed Time-evolving Block Decimation because it dynamically identifies the relevant low-dimensional Hilbert subspaces of an exponentially larger original Hilbert Space . The algorithm, based on the Matrix Product States formalism, is highly efficient when the amount of Entanglement in the system is limited, a requirement which is fulfilled by a large class of quantum many-body systems in one dimension. INTRODUCTION There is nowadays a considerable interest in the field of quantum theory for computational methods well-suited to the physics of many-body systems. Considering the inherent difficulties of simulating general quantum many-body systems, the Exponential Increase in parameters with the size of the system, and correspondingly, the high computational costs, one solution would be to look for numerical methods which deal with special cases, where one can profit from the physics of the system. The raw approach, by directly dealing with all the parameters used to fully characterize a quantum many-body system is seriously impeded by the lavishly exponential buildup with the system size of the amount of variables needed for simulation , which leads, in the best cases, to unreasonably long computational times and extended use of memory. To get around this problem a number of various methods have been developed and put into practice in the course of time, one of the most successful ones being the Quantum Monte Carlo Method (QMC). Also the Density Matrix Renormalization Group (DMRG) method, next to QMC, is a very reliable method, with an expanding community of users and an increasing number of applications to physical systems. When the first Quantum Computer will be plugged in and functioning, the perspectives for the field of computational physics will look rather promising, but until that day one has to restrict oneself to the mundane tools offered by classical computers. While experimental physicists are putting a lot of effort in trying to build the first quantum computer, theoretical physicists are searching, in the field of Quantum Information Theory (QIT), for genuine quantum algorithms, appropriate for problems which would perform badly when trying to be solved on a classical computer but pretty fast and successful on a quantum one. The search for such algorithms is still going, the best-known (and almost the only ones found) being the Shor's Algorithm , for Factoring large numbers, and Grover's Search Algorithm . In the field of QIT one has to identify the primary resources necessary for genuine quantum computation. Such a resource may be responsible for the speedup gain in quantum versus classical, identifying them means also identifying systems which can be simulated in a reasonably efficient manner on a classical computer. Such a resource is Quantum Entanglement ; hence, it is possible to establish a distinct lower bound for the entanglement needed for quantum computational speedups. Guifré Vidal, from Institute for Quantum Information, CalTech , has recently proposed a scheme useful for simulating a certain category of quantum Guifré Vidal, ''Efficient Classical Simulation of Slightly Entangled Quantum Computations'', PRL 91, 147902 (2003) {Link without Title} systems. He asserts that ''"any quantum computation with pure states can be efficiently simulated with a classical computer provided the amount of entanglement involved is sufficiently restricted" ''. This happens to be the case with generic Hamiltonians displaying local interactions, as for example, Hubbard -like Hamiltonians. The method exhibits a low-degree polynomial behavior in the increase of computational time with respect to the amount of entanglement present in the system. The algorithm is based on a scheme which exploits the fact that in these one-dimensional systems the eigenvalues of the reduced Density Matrix on a bipartite split of the system are exponentially decaying, thus allowing us to work in a resized space spanned by the eigenvectors corresponding to the Eigenvalues we selected. One can also estimate the amount of computational resources required for the simulation of a quantum system on a classical computer, knowing how the entanglement contained in the system scales with the size of the system. The classically (and quantum, as well) feasible simulations are those which involve systems which are only a trifle entangled, the strongly entangled ones being, on the other hand, good candidates only for genuine quantum computations. The numerical method is efficient in simulating real-time dynamics or calculations of Ground States using imaginary-time evolution or Isentropic interpolations between a target Hamiltonian and a Hamiltonian with an already-known ground state. The computational time scales Linearly with the system size, hence many-particles systems in 1D can be investigated. A very useful feature of the TEBD algorithm is that it can be reliably employed for Time Evolution simulations of time-dependent Hamiltonians, describing systems which can be realized with Cold atoms in Optical Lattices , or in systems far from equilibrium in quantum transport. From this point of view, TEBD had a certain ascendance over DMRG, a very powerful technique, but until recently not very well suited for simulating time-evolutions. The Matrix Product States formalism being at the mathematical heart of DMRG, the TEBD scheme was adopted by the DMRG community, thus giving birth to the time dependent DMRG {Link without Title} , t-DMRG for short. After Vidal's proposal, other groups have developed similar approaches in which quantum information plays a predominat role as, for example, for studying mixed-state dynamics in one-dimensional quantum lattice systems for calculating finite-temperature and dissipative 1D systems [http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cond-mat/0501493 or in DMRG implementations for periodic boundary conditions [http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cond-mat/0404706]. THE DECOMPOSITION OF STATE Introducing the decomposition of State   :<math> \Psi Angle \sum\limits_{i=1}^{M}c_{i_1i_2i_N} {i_1,i_2,,i_{N-1},i_N} angle</math> This may seem rather esoteric in the beginning but let's try take a look at how this decomposition is obtained and what it is good for. For this we have to make use of another piece of mathematics called the Schmidt Decomposition of a state, or Singular Value Decomposition . The Schmidt decomposition
	:<math>{\Psi} Angle	\sum\limits_{i=1}^{M}a_i{\Phi^A_i \Phi^B_i} angle</math>
	Where <math>{\Phi^A I \Phi^B I} Angle	{\Phi^A_i} angle\otimes {\Phi^B_i} angle</math> are formed with vectors <math>{\Phi^A_i} angle</math> that make an orthonormal basis in <math>H_A</math> and, correspondingly, vectors <math>{\Phi^B_i} angle</math> which form an orthonormal basis in <math>{H_B}</math>, with the coefficients <math>a_i</math> being real and positive, <math>\sum\limits_{i=1}^{M}a^2_i = 1</math> This is called the Schmidt decomposition (SD) of a state The summation can go up to <math>M_{max}=min(dim(),dim())</math>, the lowest of the two Hilbert spaces The Schmidt rank of a bipartite split is given by the number of non-zero Schmidt coefficients If the Schmidt rank is one, the split is characterized by a product state The vectors of the SD are determined up to a phase and the eigenvalues and the Schmidt rank are unique

  :<math> Au^{[3N]} {\alpha 1i 2} Angle \sum_{\alpha_2}\Gamma^{[2]i_2}_{\alpha_1\alpha_2}\lambda^{[2]}_ angle
  :<math>{\Psi} Angle \sum_{i_1,1_2,\alpha_1,\alpha_2}\Gamma^{ {Link without Title} i_1}_{\alpha_1}\lambda^{ {Link without Title} }_{\alpha_1}\Gamma^{ {Link without Title} i_2}_{\alpha_1\alpha_2}\lambda^{ {Link without Title} }_ angle</math>








  The OQGs Are Affecting Only The Qubit They Are Acting Upon, The Update Of The State <math>{\psi} Angle</math> After An "http://wwwinformationdelightinfo/information/entry/Unitary_matrix" class="copylinks">Unitary Operator at qubit ''k'' does not modify the Schmidt eigenvalues or vectors on the left, consequently the <math>\Gamma^{ or on the right, hence the <math>\Gamma^{[k+1 }</math>'s The only <math>\Gamma</math>'s that will be updated are the <math>\Gamma^{[k]}</math>'s (requiring only at most <math>(M^2\cdot\chi^2)</math> operations), as
  The "http://wwwinformationdelightinfo/information/entry/Linear_subspace" class="copylinks">Subspace ''J'' is spanned by the eigenvectors of the reduced density matrix <math> ho^{J}=Tr_{CDK}\psi angle\langle\psi</math>:




  :<math>{\psi} Angle \sum\limits_{\alpha,\beta,\gamma=1}^{\chi}\sum\limits_{i,j=1}^{M}\lambda^{ {Link without Title} }_{\alpha}\Gamma^{ {Link without Title} i}_{\alpha\beta}\lambda^{ {Link without Title} }_{\beta}\Gamma^{ {Link without Title} i}_{\beta\gamma}\lambda^{ {Link without Title} }_{\gamma} angle</math>
  We Can Write <math>{\psi'} Angle V{\psi} angle</math> as:
  :<math>{\psi'} Angle \sum\limits_{\alpha,\gamma=1}^{\chi}\sum\limits_{i,j=1}^{M}\lambda_{\alpha}\Theta^{ij}_{\alpha\gamma}\lambda_{\gamma}{{\alpha}ij\gamma} angle</math>

:<math> Ho^{' "DK" class="copylinks" target="_blank">{Link without Title} }=Tr_{JC}{\psi'} angle\langle{\psi'}=\sum_{j,j',\gamma,\gamma'} ho^{jj'}_{\gamma\gamma'}{j\gamma} angle\langle{j'\gamma'}</math>

  After Expressing Them In The Basis <math>\{{i\alpha} Angle\}</math>, The <math>\Gamma^{ "{C}" class="copylinks" target="_blank">{Link without Title} }</math>'s are:





:$H\_n=\backslash sum\backslash limits\_\{l=1\}^\{N\}K^\{+\; \backslash sum\backslash limits\_\{l=1\}^\{N\}K^\{[l,l+1\}\_2.$

It is useful to decompose $H\_n$ as a sum of two possibly non-comuting terms, $H\_n\; =\; F\; +\; G$, where

:$F\; \backslash equiv\; \backslash sum\_\{even\backslash \; \backslash \; l\}(K^\{l\}\_1\; +\; K^\{l,l+1\}\_2)\; =\; \backslash sum\_\{even\backslash \; \backslash \; l\}F^\{${Link without Title} },

:$G\; \backslash equiv\; \backslash sum\_\{odd\; \backslash \; \backslash \; l\}(K^\{l\}\_1\; +\; K^\{l,l+1\}\_2)\; =\; \backslash sum\_\{odd\; \backslash \; \backslash \; l\}G^\{${Link without Title} }.

Any two-body terms commute:
This is done in order to be able to make the Suzuki-Trotter expansion (ST)Naomichi Hatano and Masuo Suzuki, ''Finding Exponential Product Formulas of Higher Orders'' {Link without Title} of the exponential operator.


The Suzuki-Trotter expansion


The Suzuki-Trotter expansion of the first order (ST1) represents a general way of writing exponential operators:

:

or, equivalently

:$e^\}(\backslash delta^2)].$

The correction term vanishes in the limit $\backslash delta\; ightarrow0$

For simulations of quantum dynamics it is useful to use operators which are Unitary , conserving the norm (unlike power series expansions), and there's where the Trotter-Suzuki expansion comes in. In problems of quantum dynamics the unitarity of the operators in the ST expansion proves to be quite practical, since the error tends to concentrate in the overall Phase , thus allowing us to faithfully compute expectation values and conserved quantities. Because the ST conserves the phase-space volume, it is also called a symplectic integrator.

The trick of the ST2 is to write the unitary operators $e^\{-iHt\}$ as:

:

where . The number $\{\backslash it\{n\}\}$ is called the Trotter number.


Simulation of the time-evolution




:$e^$

since any two operators ,$G^\{[l\text{'}]\}$) commute for $l\{$
eq}l' and a ST expansion of the first order keeps only the product of the exponentials, the approximation becoming, in this case, exact.

The time-evolution can be made according to






Instead, one can try to do the following:









  :<math>{\psi } Angle e^{-iH_nT}{\psi_0} angle</math>



:











where $\backslash epsilon\_n\; =\; \backslash sum\backslash limits\_\{\backslash alpha=\backslash chi\_c\}^\{\backslash chi\}(\backslash lambda^\{${Link without Title} }_{\alpha})^2 is the sum of all the discarded eigenvalues of the reduced density matrix, at the bond $\{\backslash it\{n\}\}$.






  Now, <math>\langle\psi^{\bot} {D}\psi {D} Angle 0</math> because they are spanned by vectors corresponding to orthogonal spaces Using the same argument as for the Trotter expansion, the error after the truncation is:
  \epsilon N 1 - \langle{\psi}\psi_{D} angle^2 = \sum\limits_{\alpha=\chi_c}^{\chi}(\lambda^{ {Link without Title} }_{\alpha})^2</math>


  :<math>\epsilon 1 - \langle{\psi}\psi'_{D} angle^2 = 1 - (1-\epsilon_{n+1})\langle{\psi}\psi_{D} angle^2 = 1 - (1-\epsilon_{n+1})(1-\epsilon_{n})</math>



As we calculated before, the renormalization constant after making the truncation at bond $\{\backslash it\{l\}\}$ $(${Link without Title} : {Link without Title} ) is:

• }\Gamma^{ {Link without Title} i_l}_{\alpha_{l-1}\alpha_{l}}.

Taking into account the truncated space, the norm is:

:

Taking the difference, $\backslash epsilon\; =\; n\_2\; -\; n\_1\; =\; n\_2\; -\; 1$, we get:

:

Hence, when constructing the reduced density matrix, the Trace of the matrix is multiplied by the factor:




When using the Trotter expansion, we do not move from bond to bond, but between bonds of same parity; moreover, for the ST2, we make a sweep of the even ones and two for the odd. But nevertheless, the calculation presented above still holds. The error is evaluated by repeatingly multiplying with the renormalization constant, each time we build the reduced density matrix and select its relevant eigenvalues.


"ADAPTIVE" SCHMIDT DIMENSION


One thing that can save a lot of computational time without loss of accuracy is to use a different Schmidt dimension for each bond instead of a fixed one for all bonds, keeping only the necessary amount of relevant coefficients, as usual. For example, taking the first bond, in the case of qubits, the Schmidt dimension will be just two. Hence, at the first bond, instead of futilely diagonalizing, let us say, 10 by 10 or 20 by 20 matrices, we can just restrict ourselves to ordinary 2 by 2 ones, thus making the algorithm generally faster. What we can do instead is set a threshold for the eigenvalues of the SD, keeping only those that are above the threshold.