Scheduling of Random Processes and Quantum Information

Trustees Of Boston University, Boston

Investigators

Abstract

The research addresses problems in two topics: scheduling of random processes and quantum information theory. Scheduling problems arise in many areas of computer science. The investigator studies the possibility of scheduling two random sequences of activities in a way that prevents certain conflicts between them. The methods applied also advance the state of the art in percolation theory (a fundamental area of probability theory and statistical physics). Quantum information theory extends the questions concerning conditions and methods for reliable transmission of information to the setting of quantum mechanics. It has applications in cryptography, and also relates to the promising area of quantum computing. The theory of description complexity has been useful in clarifying concepts of classical information theory. The research extends description complexity theory in order to help study the much more complex questions of quantum information theory. In the scheduling problem, given are the sample paths of two or more random processes (like queues) and some condition telling when these processes ``collide''. The task is to introduce delays into each of the processes in a way that avoids collisions. Reformulation introduces a dependent percolation model with novel convergence properties that aroused much interest. The principal tool of the solution is renormalization, greatly refined. The achieved results are qualitative, leaving much quantitative work to be done. In the application of description complexity to quantum information theory, a universal semicomputable density matrix (``universal probability'') is taken as a starting point, and complexity (an operator) is defined as its negative logarithm. A number of properties of Kolmogorov complexity and von Neumann entropy extend naturally to the new domain, and the quantity reflects appropriately some of the peculiarities of quantum information (no cloning). The approach taken unifies other approaches made by several researchers in this direction.