.A faster combinatorial algorithm to calculate partial trace in quantum mechanics

    a  r   X   i  v  :   1   7   0   9 .   0   6   3   4   6  v   1   [  q  u  a  n   t  -  p   h   ]   1   9   S  e  p   2   0   1   7 A faster combinatorial algorithm to calculate partial trace inquantum mechanics Pranay Barkataki ∗ and M. S. Ramkarthik † Department of Physics, Visvesvaraya National Institute of Technology, Nagpur - 440010  (Dated: September 20, 2017) Abstract Partial trace is a very important mathematical operation in quantum mechanics. It is not onlyhelpful in studying the subsystems of a composite quantum system but also used in computinga vast majority of quantum entanglement measures. Calculating partial trace becomes computa-tionally very intensive with increasing number of qubits as the Hilbert space dimension increasesexpotentially. In this paper we discuss about our new method of partial tracing called the  com-binatorial method of partial tracing   which is more faster and accurate than the existing methodsof partial tracing. The combinatorial method of partial tracing overcomes all the limitations of the other well known methods such as being computationally intensive and being limited to lowdimensional Hilbert spaces. We give a detailed theoretical description of our method and alsoprovide an explicit example of the computation. The merits of the new method and other keyideas are discussed. ∗ Electronic address: pranaybarkataki@students.vnit.ac.in † Electronic address: ramkarthik@phy.vnit.ac.in 1  I. INTRODUCTION In quantum mechanics a general state of the quantum system can be represented by adensity matrix  ρ  [1] from which we can calculate every observable quantity related to thesystem. A composite quantum system which is composed of two subsystems is described bythe density matrix  ρ AB , where  A  and  B  represent the subsystems. Given the density matrixof the composite system, if we have to determine the quantum state of the subsystems, thenthe mathematical operation we perform is a map called the partial trace [1]. This map acts onthe density matrix  ρ AB of the total system and as a result gives us the states of the individualsubsystems which are in turn described by the corresponding reduced density matrices [2].Mathematically the reduced density matrix of subsystem  A  is written as  ρ A =  tr B ( ρ AB ), whatwe have done is to take the trace over the complimentary subsystem. The partial trace isthe  only   operation which is used to determine the states of the subsystems. Not only this,the reduced density matrices and their eigenvalues are the most important ingredients incomputing a vast majority of the entanglement measures [3] used in quantum informationtheory and other allied areas of physics. The entanglement of a system is measured by vonNeumann entropy [4] for two-qubit pure states, block entropy [5] for multipartite pure states and concurrence [6] for a two-qubit pure or mixed state. It is also well known that if we havea composite system to be an entangled state, then partially tracing out a subsystem resultsin the reduced density matrix being a mixed state and this is one of the central features of the phenomenon of entanglement. Due to the aforesaid facts, partial tracing becomes animportant mathematical operation in quantum mechanics as a whole. An efficient way tocalculate the partial trace of any quantum state has been recently reported [7] and we willbe discussing this in section III for completeness. However, our new method which will be2  discussed at length in section IV of this paper for calculating partial trace is much moresimpler and has other interesting features. With the thin line between quantum informationtheory and condensed matter physics disappearing in the last few years, our method can beof value to such condensed matter physicists who work on many body problems and finitesystems [8]. II. THE USUAL METHOD TO CALCULATE PARTIAL TRACE If we a have density matrix  ρ AB and we partially trace off subsystem  B  out of the densitymatrix  ρ AB , the mathematical operation can be written as : ρ A =  tr B ( ρ AB ) = η B   j =1 ( I  a  ⊗  b  j | ) ρ AB ( I  a  ⊗ | b  j  ) ,  (1)where  η B  is the dimension of the Hilbert space and  | b  j  ’s are the basis vectors of the subsys-tem  B . The operator  I  a  is the identity matrix in the Hilbert space of the subsystem  A . If wehave multiple subsytems say  A,B,C   of Hilbert space dimension  η A ,η B ,η C   respectively, wecan trace out two subsytems  B,C   out of the density matrix  ρ ABC  , then the reduced densitymatrix  ρ A is written as : ρ A =  tr BC  ( ρ ABC  ) =  tr B { tr C  ( ρ ABC  ) }  =  tr C  { tr B ( ρ ABC  ) } ,  (2)= η B  i =1 η C    j =1 ( I  a  ⊗  b i | ⊗  c  j | ) ρ ABC  ( I  a  ⊗ | b i  ⊗ | c  j  ) .  (3)We illustrate the above mathematical operation with an example, if we have a three qubitnormalized pure state (W-state)  | ψ  ABC   which is written as: | ψ  ABC   =  | 001  ABC   +  | 010  ABC   +  | 100  ABC  √  3 ,  (4)3  then, the corresponding pure state density matrix of all the 3 qubits is ρ ABC  =  | ψ  ABC ABC   ψ |  = 13  | 001  001 | +  | 001  010 | +  | 001  100 | +  | 010  001 | +  | 010  010 | +  | 010  100 | +  | 100  001 | +  | 100  010 | +  | 100  100 |  . (5)Sequentially tracing out subsystems  B  and  C   in succession using the density matrix  ρ ABC  of the composite system we obtain the reduced density matrix of the subsystem  A  as ρ A =  tr B { tr C  ( ρ ABC  ) }  = 13 tr B  | 00  00 | +  | 01  01 |  +  | 01  10 | +  | 10  10 |  ,  (6) ρ A = 13  2 | 0  0 | +  | 1  1 |  .  (7)If the dimension of the Hilbert space of the composite system is large then partially tracingout subsystems becomes more and more complex as the number of matrix multiplications andthe number of associated inner products to be calculated increases expotentially. This makesthe computation of the reduced density matrix difficult both analytically and numerically. III. CALCULATING PARTIAL TRACEA. Biparition system We a have density matrix  ρ  of a composite system whose subsystems are  A  and  B  withHilbert space dimension  η A  and  η B  respectively. In the density matrix  ρ  we partially traceout any one of the subsystem, let us consider we partially trace out subsystem  B . We haddevised a method independently but later it was brought to our notice that it was alreadypublished [7]. For partially tracing out any one of the subsystem of a bipartition systemthis method is much more faster than the usual method of partial tracing. The state vector |  j   spans the Hilbert space of the subsystem  B . It has only one non-null element in the  j th position of the matrix of dimension  η B  × 1, so when we calculate the reduced density matrix4  ρ A by tracing out the subsystem  B  which now spannned in the  |  j   basis, we do not multiplywith null elements of   |  j   but simply add those terms which will contribute to the matrixelement of the resulting reduced density matrix. On replacing  | b  j   by  |  j   in Eq.[1] it can betrivially seen that the matrix element  ρ Ak,l  is ρ Ak,l  = η B   j =1 ρ ( k − 1) η B +  j, ( l − 1) η B +  j .  (8) B. Multiple partition system In the paper [7], the author has given a method for computing partial trace of multiplepartitions system which is faster than usual method of calculating partial trace. We givea birds eye view of this method. The composite system density matrix  ρ ABC  has threesubsystems  A,B,C   of Hilbert space dimensions  η A ,  η B ,  η C   respectively. We write the matrix ρ ABC  in the computational basis as follows ρ ABC  = η A   j,m =1 η B  k,n =1 η C   l,o =1   jkl | ρ ABC  | mno  ( |  j  m | )  ⊗  ( | k  n | )  ⊗  ( | l  o | ) .  (9)Partially tracing out subsystem  B  from the composite system  ABC   to get the reduceddensity matrix  ρ AC  as under ρ AC  = η A   j,m =1 η B  k,n =1 η C   l,o =1   jkl | ρ ABC  | mno  ( |  j  m | )  ⊗  tr B ( | k  n | )  ⊗  ( | l  o | ) ,  (10) ρ AC  = η A   j,m =1 η C   l,o =1   η B  k =1   jkl | ρ ABC  | mko   ( |  j  m | )  ⊗  ( | l  o | ) ,  (11) ρ AC  = η A   j,m =1 η C   l,o =1   jl | ρ AC  | mo  ( |  j  m | )  ⊗  ( | l  o | ) .  (12)The state vector  | mno   has only one non null element in the matrix at the position  α  =( m − 1) η B η C   +( n − 1) η C   + o , the matrix  ρ ABC  | mno   is equivalent to  α th column of the matrix5