Results 11 to 20 of about 30,531 (141)
Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity [PDF]
IEEE Transactions on Information Theory, 2008 18 pages, 1 figure. The operation R is now really a quantum operation (it was not before); corrected some typos, III.B more readable, Conjecture 3.15 is now a ...
Markus P. Mueller
openaire +4 more sources
THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY [PDF]
Modern Physics Letters B, 2008 The Kolmogorov complexity of a physical state is the minimal physical resources required to reproduce that state. We define a second quantized quantum Turing machine and use it to define second quantized Kolmogorov complexity. There are two advantages to our approach — our measure of the second quantized Kolmogorov complexity is closer to physical ...
Rogers, C, Vedral, V
openaire +4 more sources
Lower bounds for randomized and quantum query complexity using Kolmogorov arguments [PDF]
Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004., 2004 We prove a very general lower bound technique for quantum and randomized query complexity, that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted, unweighted methods of Ambainis, and the spectral method of Barnum, Saks and Szegedy.
Laplante, Sophie, Magniez, Frederic
openaire +4 more sources
Quantum Kolmogorov Complexity and the Quantum Turing Machine
, 2007 The purpose of this thesis is to give a formal definition of quantum Kolmogorov complexity and rigorous mathematical proofs of its basic properties. Classical Kolmogorov complexity is a well-known and useful measure of randomness for binary strings. In recent years, several different quantum generalizations of Kolmogorov complexity have been proposed ...
Markus P. Mueller
semanticscholar +5 more sources
ON THE QUANTUM KOLMOGOROV COMPLEXITY OF CLASSICAL STRINGS
International Journal of Quantum Information, 2009 We show that classical and quantum Kolmogorov complexity of binary strings agree up to an additive constant. Both complexities are defined as the minimal length of any (classical resp. quantum) computer program that outputs the corresponding string. It follows that quantum complexity is an extension of classical complexity to the domain of quantum ...
Markus P. Mueller
openaire +4 more sources
Kolmogorov's algorithmic complexity and its probability interpretation in quantum gravity [PDF]
Classical and Quantum Gravity, 1998 The quantum gravity has great difficulties with application of the probability notion. In given article this problem is analyzed according to algorithmic viewpoint. According to A.N. Kolmogorov, the probability notion can be connected with algorithmic complexity of given object.
V. Dzhunushaliev
openaire +5 more sources
Topological Kolmogorov complexity and the Berezinskii-Kosterlitz-Thouless mechanism. [PDF]
Physical Review E, 2023 Topology plays a fundamental role in our understanding of many-body physics, from vortices and solitons in classical field theory to phases and excitations in quantum matter.
Vittorio Vitale +3 more
semanticscholar +1 more source
Kolmogorov complexity as intrinsic entropy of a pure state: Perspective from entanglement in free fermion systems [PDF]
Physical review B, 2022 We consider free fermion systems in arbitrary dimensions and represent the occupation pattern of each eigenstate as a classical binary string.
K. Ma, Kun Yang
semanticscholar +1 more source
Second quantised information distance
IET Quantum Communication, 2023 The Kolmogorov complexity of a string is the minimum length of a programme that can produce that string. Information distance between two strings based on Kolmogorov complexity is defined as the minimum length of a programme that can transform either ...
Songsong Dai
doaj +1 more source
Entanglement Dynamics and Classical Complexity
Entropy, 2023 We study the dynamical generation of entanglement for a two-body interacting system, starting from a separable coherent state. We show analytically that in the quasiclassical regime the entanglement growth rate can be simply computed by means of the ...
Jiaozi Wang +3 more
doaj +1 more source