Partial trace is a very important mathematical operation in quantum mechanics. It is not only helpful in studying the subsystems of a composite quantum system but also used in computing a vast majority of quantum entanglement measures. Calculating
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 computationally 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
combinatorial 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 twoqubit pure states, block entropy [5] for multipartite pure states
and concurrence [6] for a twoqubit 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 eﬃcient 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 ﬁnitesystems [8].
II. THE USUAL METHOD TO CALCULATE PARTIAL TRACE
If we a have density matrix
ρ
AB
and we partially trace oﬀ 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 subsystem
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 (Wstate)

ψ
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 diﬃcult 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 nonnull 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