Von Neumann entropy and quantum algorithmic randomness

Quantum algorithms and complexity in the theory of computing (68Q12) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Quantum computation (81P68) Measures of information, entropy (94A17)

Review text

Intuitively, we understand that some sequences of 0s and 1s are random -- e.g., a sequence that we can obtain by continuously flipping a coin -- while other sequences are not -- e.g., a periodic sequence 0101\ldots However, until the 1960s, there was no adequate formalization of this idea. It was formalized, crudely speaking, by saying that an infinite sequence is random if it satisfies all the laws of probability. A law of probability is a computable property that is satisfied with probability 1 -- this property defines a set of probability measure 1. So a sequence is random if it belongs to all computable sets of measure 1 -- e.g., if it passes all possible randomness tests. A randomness test means that we apply some test to initial fragments of the infinite sequence -- and if a sequence is not random, we will eventually detect that.\N\NThis works very well in non-quantum applications, where the measurement results are uniquely determined by the state -- in the sense that the more accurately we measure, the more bits we learn of the sequence of bits that describes the state. Thus, we can use algorithmic randomness to define random states. The situation is more complex in quantum physics, where the measurement results are random with respect to the corresponding probability measure. So, even for a deterministic state like 00\ldots, for some measuring instruments the results will be random -- but they will be not random if we measure 0 or 1 at each step. It is therefore natural to call a quantum state \textit{random} if the measurement results are random for \textit{all} computable sequences of measurements.\N\NIn quantum mechanics, the state of \(n\) bits can be described by a density matrix \(\rho_n\). So, a natural analog of an infinite binary sequence is a sequence of density matrices for which each \(\rho_{n}\) is a projection of \(\rho_{n+1}\) onto the corresponding subspace of \(n\)-bit states.\N\NIn quantum physics, a binary (``yes-``no) measurement performed on the first \(n\) bits is a subspace of the space of all \(n\)-bit states. When a sequence \(\{\rho_n\}\) is \textit{not random}, then there is a sequence of measurements -- i.e., subspaces -- whose probabilities \(p_n\) on the set of \(n\) independent qubits in equal-probability-0-and-1 quantum states decrease with \(n\) (to be more precise, sum up to a computable number), while their probabilities \(q_n\) on the state \(\rho_n\) tend to 1. A sequence is \textit{random} if it is not ``not random in this sense.\N\NThe author proves that this randomness is related to the entropy defined as follows. A general measuring instrument can be described by an orthogonal basis and corresponding eigenvalues. As a result of the measurement, the original state \(\rho_n\) is transformed into one of the basis vectors with probability equal to the squared length of the projection of \(\rho_n\) on this vector. It is known that the Shannon entropy of the resulting probability distribution is the smallest when this basis consists of eigenvectors of the state \(\rho_n\). This smallest entropy \(H(\rho_n)\) is called \textit{von Neumann entropy}. The author proves several results relating randomness with \(H\); we will just list two: (1) when the random state \(\{\rho_n\}\) is computable, then \(H(\rho_n)/n\to 1\), and (2) a computable state \(\{\rho_n\}\) is random if and only if the family of distributions \(\rho_n\) is uniformly integrable.

Cites work

This page was built for publication: Von Neumann entropy and quantum algorithmic randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6985493)