I wanted to verify two intuitions about the entanglement entropy of quantum states.

Consider an $n$ qubit quantum state, prepared by a depth $d$ circuit acting on $|0\rangle^{\otimes n}$ and a bipartition of the state into two systems, $A$ and $B$. Let the boundary between $A$ and $B$ be of size $M$.

The von Neumann entanglement entropy of the reduced density matrix, for each bipartition, should be at most $Md$. This is because there can be at most $Md$ entangling gates across the bipartition ($M$ gates for each time-step), and each gate would increase the entanglement entropy by at most $1$.

Hence, for all 1D circuits of depth $d$, where $M$ is a constant, the entanglement entropy is at most a constant times $d$.

Are these intuitions correct?

The source of the confusion is this paper, where on page 19, they exhibit a $\text{poly}\log$ depth 1D circuit with entropy ~$n$.


1 Answer 1


It is not true that the increase in von Neumann entropy of entanglement between the two partitions due to a single cross-partition two-qubit gate is at most one. See below for an example where the increase is two. However, we can use log Schmidt rank to justify a different asymptotically linear upper bound.

Product states

A two-qubit gate cannot produce more than one ebit of entanglement when applied to a product state. This follows from Schmidt decomposition and the fact that the Hilbert space of one qubit is two-dimensional.


However, the argument fails when the qubits to which the gate is applied have preexisting entanglement with other qubits. For example, consider four qubits $A_1A_2B_1B_2$ in the state

$$ |\psi_0\rangle = \frac12(|0_{A_1}0_{A_2}\rangle+|1_{A_1}1_{A_2}\rangle)\otimes(|0_{B_1}0_{B_2}\rangle+|1_{B_1}1_{B_2}\rangle).\tag1 $$

Clearly, the initial entanglement entropy between the partition $A=A_1A_2$ and $B=B_1B_2$ is zero. However, following a single SWAP gate applied to qubits $A_2$ and $B_1$, we get

$$ |\psi_1\rangle = \frac12(|0_{A_1}0_{B_1}\rangle+|1_{A_1}1_{B_1}\rangle)\otimes(|0_{A_2}0_{B_2}\rangle+|1_{A_2}1_{B_2}\rangle)\tag2 $$

with the reduced state of partition $A$

$$ \rho=\mathrm{tr}_{B}(|\psi_1\rangle\langle\psi_1|)=\frac{I_2}{2}\otimes\frac{I_2}{2}=\frac{I_4}{4}\tag3 $$

and entanglement entropy $S(\rho)=2$.

Schmidt rank

By Schmidt decomposition, a state $|\phi\rangle$ of partitions $A$ and $B$ can be written as

$$ |\phi\rangle = \sum_{i=1}^m\lambda_i|i_A\rangle|i_B\rangle\tag4 $$

where $\lambda_i>0$ are Schmidt coefficients and $|i_X\rangle$ are orthonormal states of partition $X=A,B$. The number $m$, often denoted by $\mathrm{Sch}(|\phi\rangle)$ and called the Schmidt rank of the bipartite state $|\phi\rangle$, is another important measure of entanglement.

For any $m$ positive real numbers $s_1, \dots, s_m$ summing to $1$, the Shannon entropy $H(s_1,\dots,s_m)\le\log m$. Therefore, the logarithm of the Schmidt rank provides an upper bound on von Neumann entropy

$$ S(\mathrm{tr}_B(|\psi\rangle\langle\psi|)) \le \log\mathrm{Sch}(|\psi\rangle)\tag5 $$

for any pure bipartite state $|\psi\rangle$.

Increase in log Schmidt rank due to one gate

We can derive an upper bound on the increase in log Schmidt rank due to a single two-qubit cross-partition gate. Suppose the gate $U$ has operator Schmidt rank $r$, i.e. can be written as

$$ U=\sum_{j=1}^rR_j\otimes S_j\tag6 $$

for some single-qubit operators $R_j$ and $S_j$ acting on a qubit in partition $A$ and $B$, respectively and orthogonal with respect to Hilbert-Schmidt inner product (see e.g. $6.4.2$ in Nielsen's PhD thesis or this paper for more details on operator variant of Schmidt decomposition). Then $U|\phi\rangle$ may be written as

$$ \begin{align} |\phi'\rangle=U|\phi\rangle&=\sum_{i=1}^m\sum_{j=1}^r\lambda_iR_j|i\rangle S_j|i'\rangle \\ &= \sum_{k=1}^{mr}\mu_k|k''\rangle|k'''\rangle \end{align}\tag7 $$

so$^1$ $|\phi'\rangle$ has Schmidt rank at most $mr$.

Now, $R_j$ and $S_j$ belong to the complex vector space of operators on $\mathbb{C}^2$ which is four dimensional. Therefore, for a two-qubit gate $r\le 4$. We conclude that a two qubit gate can increase the log Schmidt rank by at most two.

Linear bound on von Neumann entropy

Therefore, by $(5)$ the final von Neumann entropy $S_f$ of entanglement between the two partitions after running a circuit with $Md$ cross-partition two-qubit gates can be bounded above as

$$ S_f\le 2Md.\tag8 $$

Even though $(8)$ is not as tight as $Md$, it is still asymptotically linear.

$^1$ Every representation of a bipartite state $|\psi\rangle$ as a sum of product states has at least $\mathrm{Sch}(|\psi\rangle)$ terms. See e.g. Problem $2.2$ on page $117$ in Nielsen & Chuang.
  • 1
    $\begingroup$ Thanks, as always, for a fantastic answer! :) $\endgroup$
    – BlackHat18
    Dec 20, 2021 at 10:07
  • 1
    $\begingroup$ You're welcome! Thank you for the kind words and an interesting question! Note that it may be possible to prove the tighter bound $Md$ since the input is a product state. I don't know how to do this rigorously right now, though. A special case where the above arguments imply $S_f\le Md$ occurs if the boundary qubits spend half of the time interacting with neighbors across the boundary and half the time interacting with neighbors in their home partition. $\endgroup$ Dec 20, 2021 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.