Information and Complexity Theory

Umesh V. Vazirani

Bheku Khumalo

This paper seeks to discuss why information theory is so important. What is information, knowledge is interaction of human mind and information, but there is a difference between information theory and knowledge theory. Look into information and particle theory and see how information must have its roots in particle theory. This leads to the concept of spatial dimensions, information density, complexity, particle density, can there be particle complexity, and re-looking at the double slit experiment and quantum tunneling. Information functions/ relations are discussed.

Eduardo Jose Bayro-Corrochano

Jack D. Hidary

Noboru Watanabe

In several complicated systems, it is important to study (1) the dynamics of state change and (2) the complexity of states of systems. Information Dynamics (ID) introduced by Ohya is a general idea constructing a theory by synthesizing the research schemes of (1) and (2) under a frame of the ID. In ID, there are two types of complexities, that is, (a) a complexity of state describing system itself and (b) a transmitted complexity between two systems. Entropies of classical and quantum information theory are the example of the complexities of (a) and (b). In quantum information theory, Ohya introduced a compound state and defined Ohya mutual entropy based on quantum relative entropy of Umegaki in 1983, he extended it to general quantum systems by using the relative entropy of Araki and Uhlmann. One can discuss the coding theorems by means of the mean entropy and the mean mutual entropy defined by the dynamical entropy. In this paper, we will discuss about complexity of quantum communication processes including quantum correlations.

Ciarán M. Lee, Matty J. Hoban

What kind of object is a quantum state? Is it an object that encodes an exponentially growing amount of information (in the size of the system) or more akin to a probability distribution? It turns out that these questions are sensitive to what we do with the information. For example, Holevo's bound tells us that n qubits only encode n bits of classical information but for certain communication complexity tasks there is an exponential separation between quantum and classical resources. Instead of just contrasting quantum and classical physics, we can place both within a broad landscape of physical theories and ask how non-quantum (and non-classical) theories are different from, or more powerful than quantum theory. For example, in communication complexity, certain (non-quantum) theories can trivialise all communication complexity tasks. In recent work [C. M. Lee and M. J. Hoban, Proc. Royal Soc. A 472 (2190), 2016], we showed that the immense power of the information content of states in general (non-quantum) physical theories is not limited to communication complexity. We showed that, in general physical theories, states can be taken as "advice" for computers in these theories and this advice allows the computers to easily solve any decision problem. Aaronson has highlighted the close connection between quantum communication complexity and quantum computations that take quantum advice, and our work gives further indications that this is a very general connection. In this work, we review the results in our previous work and discuss the intricate relationship between communication complexity and computers taking advice for general theories.