We extend algorithmic information theory to quantum mechanics, taking a universal semicomputable density matrix (`universal probability') as a starting point, and define complexity (an operator) as its negative logarithm. A number of properties of Kolmogorov complexity extend naturally to the new domain. Approximately, a quantum state is simple if it is within a small distance from a low-dimensional subspace of low Kolmogorov complexity. The von Neumann entropy of a computable density matrix is within an additive constant from the average complexity. Some of the theory of randomness translates to the new domain. We explore the relations of the new quantity to the quantum Kolmogorov complexity defined by Vitányi (we show that the latter is sometimes as large as 2 n − 2 log n ) and the qubit complexity defined by Berthiaume, Dam and Laplante. The `cloning' properties of our complexity measure are similar to those of qubit complexity.
Extends algorithmic information theory to quantum mechanics, taking a universal semi-computable density matrix ("universal probability") as a starting point, and defines complexity (an operator) as its negative logarithm. A number of properties of Kolmogorov complexity extend naturally to the new domain. Approximately, a quantum state is simple if it is within a small distance from a low-dimensional subspace of low Kolmogorov complexity. The von-Neumann entropy of a computable density matrix is within an additive constant from the average complexity. Some of the theory of randomness translates to the new domain. We explore the relations of the new quantity to the quantum Kolmogorov complexity defined by P.M.B. Vita/spl acute/nyi (1999) (we show that the latter is sometimes as large as 2n-2 log n) and the qubit complexity defined by A. Berthiaume et al. (2000). The "cloning" properties of our complexity measure are similar to those of qubit complexity.
Completely positive trace-preserving maps
S, also known as quantum channels, arise in quantum physics as a description of how the density operator
ρ of a system changes in a given time interval, allowing not only for unitary evolution but arbitrary operations including measurements or other interaction with an environment. It is known that if the Hilbert space
H that
ρ acts on is finite-dimensional, then every
S must have a fixed point, i.e., a density operator
ρ0 with
S(ρ0)=ρ0. In infinite dimension,
S need not have a fixed point in general. However, we prove here the existence of a fixed point under a certain additional assumption which is, roughly speaking, that
S leaves invariant a certain set of density operators with bounded ``cost'' of preparation. The proof is an application of the Schauder-Tychonoff fixed point theorem. Our motivation for this question comes from a proposal of Deutsch for how to define quantum theory in a space-time with closed timelike curves; our result supports the viability of Deutsch's proposal.
We consider the task of implementing non-energy preserving gates (NEPG) on a finite-dimensional system S via an energy-preserving interaction with an external battery B. We prove that the entropic coherence of the battery (an instance of the relative entropy of resource) is a necessary resource for this task, and find a lower bound on its minimum amount that has to be present in the battery to be able to implement NEPGs with a fixed desired precision. An immediate corollary is that any finite-dimensional battery is doomed to a certain minimal error in the gate implementation task. Moreover, under assumptions on the density of energy levels in the battery Hamiltonian, our main results imply additional lower bounds on the minimal amount of energy and quantum Fisher information required to implement any gate. We show that these bounds can be stronger than the universal bounds previously established in the literature.