Skip to main content
added a summary
Source Link

Theorem 6 here https://arxiv.org/pdf/quant-ph/0005018.pdf is one relationship between QC and the von Neumann entropy (S) https://arxiv.org/abs/0712.4377 is another good reference. My very rough intuition for why the link between S and QC is not as strong as that between Shannon entropy (H) and Kolmogorov Complexity (K) is: If bit-strings, $x$, are drawn according to some distribution $p$ then $H(p)$ is the expected value of $K(x)$. So, both $K$ and $H$ measure, in some sense, the complexity. Now let $\mu$ and $\rho$ be a density matrices with the same eigenvalues but with different eigenvectors. Suppose the eigenvectors of $\mu$ are more complex (in the sense of $QC$) than those of $\rho$. I.e., $QC(\rho)<QC(\mu)$. Now, $S(\rho)=S(\mu)$ as S only depends on the eigenvalues, not on the eigenvectors. So, by being blind to the complexity of the eigenvectors, S becomes unrelated to the QC.

There are infinite qubitstrings whose initial segments have high QC (asymptotically) but zero von-Neumann entropy. For example, take a 1-random real and construct an infinite qubitstring, $\rho$ from it (see https://arxiv.org/abs/1709.08422). Although the initial segments of $\rho$ have high QC (by theorem 4.4 in https://arxiv.org/abs/1709.08422), they have zero von Neumann entropy as they are pure states. This essentially works due to the simple fact that while pure states can have high QC, all pure states have zero von Neumann entropy.

https://arxiv.org/abs/2008.03584 contains some results in section 5 on the von-Neumann entropy of infinite sequences.

In summary, the von Neumann entropy of a density matrix measures the entropy of the distribution given by its eigenvalues and ignores the algorithmic complexity of its eigenvectors.

Theorem 6 here https://arxiv.org/pdf/quant-ph/0005018.pdf is one relationship between QC and the von Neumann entropy (S) https://arxiv.org/abs/0712.4377 is another good reference. My very rough intuition for why the link between S and QC is not as strong as that between Shannon entropy (H) and Kolmogorov Complexity (K) is: If bit-strings, $x$, are drawn according to some distribution $p$ then $H(p)$ is the expected value of $K(x)$. So, both $K$ and $H$ measure, in some sense, the complexity. Now let $\mu$ and $\rho$ be a density matrices with the same eigenvalues but with different eigenvectors. Suppose the eigenvectors of $\mu$ are more complex (in the sense of $QC$) than those of $\rho$. I.e., $QC(\rho)<QC(\mu)$. Now, $S(\rho)=S(\mu)$ as S only depends on the eigenvalues, not on the eigenvectors. So, by being blind to the complexity of the eigenvectors, S becomes unrelated to the QC.

There are infinite qubitstrings whose initial segments have high QC (asymptotically) but zero von-Neumann entropy. For example, take a 1-random real and construct an infinite qubitstring, $\rho$ from it (see https://arxiv.org/abs/1709.08422). Although the initial segments of $\rho$ have high QC (by theorem 4.4 in https://arxiv.org/abs/1709.08422), they have zero von Neumann entropy as they are pure states. This essentially works due to the simple fact that while pure states can have high QC, all pure states have zero von Neumann entropy.

https://arxiv.org/abs/2008.03584 contains some results in section 5 on the von-Neumann entropy of infinite sequences.

Theorem 6 here https://arxiv.org/pdf/quant-ph/0005018.pdf is one relationship between QC and the von Neumann entropy (S) https://arxiv.org/abs/0712.4377 is another good reference. My very rough intuition for why the link between S and QC is not as strong as that between Shannon entropy (H) and Kolmogorov Complexity (K) is: If bit-strings, $x$, are drawn according to some distribution $p$ then $H(p)$ is the expected value of $K(x)$. So, both $K$ and $H$ measure, in some sense, the complexity. Now let $\mu$ and $\rho$ be a density matrices with the same eigenvalues but with different eigenvectors. Suppose the eigenvectors of $\mu$ are more complex (in the sense of $QC$) than those of $\rho$. I.e., $QC(\rho)<QC(\mu)$. Now, $S(\rho)=S(\mu)$ as S only depends on the eigenvalues, not on the eigenvectors. So, by being blind to the complexity of the eigenvectors, S becomes unrelated to the QC.

There are infinite qubitstrings whose initial segments have high QC (asymptotically) but zero von-Neumann entropy. For example, take a 1-random real and construct an infinite qubitstring, $\rho$ from it (see https://arxiv.org/abs/1709.08422). Although the initial segments of $\rho$ have high QC (by theorem 4.4 in https://arxiv.org/abs/1709.08422), they have zero von Neumann entropy as they are pure states. This essentially works due to the simple fact that while pure states can have high QC, all pure states have zero von Neumann entropy.

https://arxiv.org/abs/2008.03584 contains some results in section 5 on the von-Neumann entropy of infinite sequences.

In summary, the von Neumann entropy of a density matrix measures the entropy of the distribution given by its eigenvalues and ignores the algorithmic complexity of its eigenvectors.

added examples and references dealing with the entropy and QC of infinite qubitstrings.
Source Link

Theorem 6 here https://arxiv.org/pdf/quant-ph/0005018.pdf is one relationship between QC and the von Neumann entropy (S).https://arxiv.org/abs/0712.4377 https://arxiv.org/abs/0712.4377 is another good reference. My very rough intuition for why the link between S and QC is not as strong as that between Shannon entropy (H) and Kolmogorov Complexity (K) is: If bit-strings, $x$, are drawn according to some distribution $p$ then $H(p)$ is the expected value of $K(x)$. So, both $K$ and $H$ measure, in some sense, the complexity. Now let $\mu$ and $\rho$ be a density matrices with the same eigenvalues but with different eigenvectors. Suppose the eigenvectors of $\mu$ are more complex (in the sense of $QC$) than those of $\rho$. I.e., $QC(\rho)<QC(\mu)$. Now, $S(\rho)=S(\mu)$ as S only depends on the eigenvalues, not on the eigenvectors. So, by being blind to the complexity of the eigenvectors, S becomes unrelated to the QC.

There are infinite qubitstrings whose initial segments have high QC (asymptotically) but zero von-Neumann entropy. For example, take a 1-random real and construct an infinite qubitstring, $\rho$ from it (see https://arxiv.org/abs/1709.08422). Although the initial segments of $\rho$ have high QC (by theorem 4.4 in https://arxiv.org/abs/1709.08422), they have zero von Neumann entropy as they are pure states. This essentially works due to the simple fact that while pure states can have high QC, all pure states have zero von Neumann entropy.

https://arxiv.org/abs/2008.03584 contains some results in section 5 on the von-Neumann entropy of infinite sequences.

Theorem 6 here https://arxiv.org/pdf/quant-ph/0005018.pdf is one relationship between QC and the von Neumann entropy (S).https://arxiv.org/abs/0712.4377 is another good reference. My very rough intuition for why the link between S and QC is not as strong as that between Shannon entropy (H) and Kolmogorov Complexity (K) is: If bit-strings, $x$, are drawn according to some distribution $p$ then $H(p)$ is the expected value of $K(x)$. So, both $K$ and $H$ measure, in some sense, the complexity. Now let $\mu$ and $\rho$ be a density matrices with the same eigenvalues but with different eigenvectors. Suppose the eigenvectors of $\mu$ are more complex (in the sense of $QC$) than those of $\rho$. I.e., $QC(\rho)<QC(\mu)$. Now, $S(\rho)=S(\mu)$ as S only depends on the eigenvalues, not on the eigenvectors. So, by being blind to the complexity of the eigenvectors, S becomes unrelated to the QC.

Theorem 6 here https://arxiv.org/pdf/quant-ph/0005018.pdf is one relationship between QC and the von Neumann entropy (S) https://arxiv.org/abs/0712.4377 is another good reference. My very rough intuition for why the link between S and QC is not as strong as that between Shannon entropy (H) and Kolmogorov Complexity (K) is: If bit-strings, $x$, are drawn according to some distribution $p$ then $H(p)$ is the expected value of $K(x)$. So, both $K$ and $H$ measure, in some sense, the complexity. Now let $\mu$ and $\rho$ be a density matrices with the same eigenvalues but with different eigenvectors. Suppose the eigenvectors of $\mu$ are more complex (in the sense of $QC$) than those of $\rho$. I.e., $QC(\rho)<QC(\mu)$. Now, $S(\rho)=S(\mu)$ as S only depends on the eigenvalues, not on the eigenvectors. So, by being blind to the complexity of the eigenvectors, S becomes unrelated to the QC.

There are infinite qubitstrings whose initial segments have high QC (asymptotically) but zero von-Neumann entropy. For example, take a 1-random real and construct an infinite qubitstring, $\rho$ from it (see https://arxiv.org/abs/1709.08422). Although the initial segments of $\rho$ have high QC (by theorem 4.4 in https://arxiv.org/abs/1709.08422), they have zero von Neumann entropy as they are pure states. This essentially works due to the simple fact that while pure states can have high QC, all pure states have zero von Neumann entropy.

https://arxiv.org/abs/2008.03584 contains some results in section 5 on the von-Neumann entropy of infinite sequences.

Source Link

Theorem 6 here https://arxiv.org/pdf/quant-ph/0005018.pdf is one relationship between QC and the von Neumann entropy (S).https://arxiv.org/abs/0712.4377 is another good reference. My very rough intuition for why the link between S and QC is not as strong as that between Shannon entropy (H) and Kolmogorov Complexity (K) is: If bit-strings, $x$, are drawn according to some distribution $p$ then $H(p)$ is the expected value of $K(x)$. So, both $K$ and $H$ measure, in some sense, the complexity. Now let $\mu$ and $\rho$ be a density matrices with the same eigenvalues but with different eigenvectors. Suppose the eigenvectors of $\mu$ are more complex (in the sense of $QC$) than those of $\rho$. I.e., $QC(\rho)<QC(\mu)$. Now, $S(\rho)=S(\mu)$ as S only depends on the eigenvalues, not on the eigenvectors. So, by being blind to the complexity of the eigenvectors, S becomes unrelated to the QC.