How to measure entanglement in an algorithm?

Question

Entanglement in Algorithms

Most algorithms in quantum computing find their strength in making use of entanglement.

I am interested in evaluating the amount of entanglement generated within an algorithm, maybe even being able to think of knowing how this information changes for different numbers of runs of the algorithm or if the algorithm is run on different numbers of qubits.

How would one best do this?

My thoughts are to calculate the density matrix of the computational qubits at every time step and to find the von Neumann entropy of this multipartite state and work from there but it appears that there are many different kinds of entanglement measures useful for different kinds of situations [1].

Take Shor's factoring algorithm for example. How would you go about calculating the entanglement at each time step? I have found two approaches thus far, [2] which takes into account mixed states using the notion of a Groverian measure and [3] which makes use of standard von Neumann entropy.

Answer 1

This is not much of an answer, but is probably too long for a comment...

I don't believe that there's a canonical way of doing this. You'd be best off understanding why you're asking the question, and what you want to get out of it. From there, you tailor how you're going to measure it. But multipartite entanglement is a really messy problem, even just for pure states.

Let me give an example of how messy and confusing it can be. There is a paper about "the power of one clean qubit" which introduces a computational model that is known as DQC1. One of the first questions asked about this computation was "is there any entanglement?" Not even how much, just a simple yes or no. Originally, it was concluded that there is no entanglement is this system because they looked at one particular bipartition of the qubits (the most obvious one), and there was no entanglement across that bipartition (I'm not sure if this is explicitly stated anywhere, but this is how it has been read by many). However, later studies looked more in-depth at other bipartitions and found the existence of entanglement there.