• Register
PhysicsOverflow is a next-generation academic platform for physicists and astronomers, including a community peer review system and a postgraduate-level discussion forum analogous to MathOverflow.

Welcome to PhysicsOverflow! PhysicsOverflow is an open platform for community peer review and graduate-level Physics discussion.

Please help promote PhysicsOverflow ads elsewhere if you like it.


PO is now at the Physics Department of Bielefeld University!

New printer friendly PO pages!

Migration to Bielefeld University was successful!

Please vote for this year's PhysicsOverflow ads!

Please do help out in categorising submissions. Submit a paper to PhysicsOverflow!

... see more

Tools for paper authors

Submit paper
Claim Paper Authorship

Tools for SE users

Search User
Reclaim SE Account
Request Account Merger
Nativise imported posts
Claim post (deleted users)
Import SE post

Users whose questions have been imported from Physics Stack Exchange, Theoretical Physics Stack Exchange, or any other Stack Exchange site are kindly requested to reclaim their account and not to register as a new user.

Public \(\beta\) tools

Report a bug with a feature
Request a new functionality
404 page design
Send feedback


(propose a free ad)

Site Statistics

205 submissions , 163 unreviewed
5,054 questions , 2,207 unanswered
5,345 answers , 22,719 comments
1,470 users with positive rep
818 active unimported users
More ...

  partial trace with sparse matrices

+ 4 like - 0 dislike

Let $\rho_{ABCD}$ be a sparse matrix of 4 systems each in a $d$-dimensional Hilbert space.

For $d<7$ in a reasonable time (few seconds) I able to perform the partial trace $\rho_{AD}$ using the code proposed in http://www3.imperial.ac.uk/people/m.tame/research. I would need an efficient algorithm for calculating $\rho_{AD}$ where $d\geq7$. The algorithm of the site above does not exploit any properties of the matrix and it requires a lot of permutations and rearrangements.

Do you know an efficient algorithm for calculating the partial trace of qudit which uses the fact that the matrix is sparse? It would also be interesting if the algorithm can take advantage of parallel computation.

Thank you very much in advance for your answers.



This post has been migrated from (A51.SE)
asked Apr 17, 2012 in Theoretical Physics by Silvio Abruzzo (70 points) [ no revision ]
Strictly speaking, you can only hope for a polynomial scaling with the dimension of the system $d$ (I would not call this efficient in computational complexity terms, unless you set d to be a constant). It would be useful to know how sparse is your density matrix: how does the maximal number-of-coefficients per rows *and* column asymptotically scale with the dimesion of the system $d$?

This post has been migrated from (A51.SE)
In general, a partial trace of a sparse matrix does not yield a sparse matrix, so you will get only limited improvement by using the fact that the matrix is sparse (maybe a factor of d/s).

This post has been migrated from (A51.SE)

1 Answer

+ 1 like - 0 dislike

If you want something specific to Mathematica then I don't know, but in general:

Let $\sigma = \rho_{AD} = \textrm{Tr}_{BC}(\rho)$. $\rho$ is an operator on four subsystems, so it has four inputs and four outputs making it a rank 8 tensor. Let $i,i'$ be the indices corresponding to the input and output of $\rho$ on subsystem $A$, let $j,j'$ correspond to $B$, etc. The components of $\sigma$ are then $\sigma_{ii'll'} = \sum_{jk} \rho_{ii'jjkkll'}$.

If $\rho$ is sparse you only need to sum the entries which are nonzero. If $\rho$ is Hermitian then $\sigma$ will be Hermitian and it is enough to only compute the upper triangle (the lower triangle is then the conjugate of that). I don't believe there are any other optimizations available unless you know of further structure on $\rho$. The sum is trivially parallelizable - each combination $ii'll'$ is completely independent of the others.

This post has been migrated from (A51.SE)
answered Apr 17, 2012 by Dan Stahlke (70 points) [ no revision ]
The efficiency of this method strongly depends on how costly is to list the coefficients of the sparse which are non-zero. It would be good if the OP could clarify this point.

This post has been migrated from (A51.SE)
Thank you very much for your answer. Using your suggestion and looking more carefully to the algorithm proposed in Mathematica (link in the question) I was able to parallelize the algorithm and now I am able to arrive until $d\leq9$. Regarding further structures or the asymptotic scaling of the non-zero elements I don't have a so deep analysis because it is not needed for my problem. I do believe that there is not any interesting property that can be used for the partial trace because I apply one unitaries to some states and I see that there are "a lot" of zeros. Thank you very much again.

This post has been migrated from (A51.SE)

Your answer

Please use answers only to (at least partly) answer questions. To comment, discuss, or ask for clarification, leave a comment instead.
To mask links under text, please type your text, highlight it, and click the "link" button. You can then enter your link URL.
Please consult the FAQ for as to how to format your post.
This is the answer box; if you want to write a comment instead, please use the 'add comment' button.
Live preview (may slow down editor)   Preview
Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
If you are a human please identify the position of the character covered by the symbol $\varnothing$ in the following word:
Then drag the red bullet below over the corresponding character of our banner. When you drop it there, the bullet changes to green (on slow internet connections after a few seconds).
Please complete the anti-spam verification

user contributions licensed under cc by-sa 3.0 with attribution required

Your rights