The interaction of information and control has been a topic of interest to system theorists that can be traced back at least to the 1950's when the fields of communications, control, and information theory were new but developing rapidly.Recent advances in our understanding of this interplay have emerged from work on the dynamical effect of state quantization together with results connecting communication channel data rates and system stability.Although this work has generated considerable interest, it has been centrally concerned with the relationship between control system performance and feedback information processing rates while ignoring the complexity (i.e. the cost of information processing).The concepts of communication and computation complexity of a controlled dynamical system based on digitized information lie in what is largely an uncharted area.In our recent work an attempt was made to explore this area by introducing a new measure of communication complexity for a two-player distributed control system.This complexity is named control communication complexity (CCC).It is based on the communication complexity concept defined in distributed computing and seeks to connect the complexity of information exchange over finite bandwidth channels with the control system dynamics.The purpose of the present paper is to extend the study of control communication complexity to an interesting class of continuous-time control systems that have appeared in the recent literature dealing with quantum communication and control systems.An interesting aspect of this extension is that it brings together heretofore independent research themes that have been prominent in the research career of Roger Brockett.
The interaction of information and control has been a topic of interest to system theorists that can be traced back at least to the 1950's when the fields of communications, control, and information theory were new but developing rapidly.Recent advances in our understanding of this interplay have emerged from work on the dynamical effect of state quantization together with results connecting communication channel data rates and system stability.Although this work has generated considerable interest, it has been centrally concerned with the relationship between control system performance and feedback information processing rates while ignoring the complexity (i.e. the cost of information processing).The concepts of communication and computation complexity of a controlled dynamical system based on digitized information lie in what is largely an uncharted area.In our recent work an attempt was made to explore this area by introducing a new measure of communication complexity for a two-player distributed control system.This complexity is named control communication complexity (CCC).It is based on the communication complexity concept defined in distributed computing and seeks to connect the complexity of information exchange over finite bandwidth channels with the control system dynamics.The purpose of the present paper is to extend the study of control communication complexity to an interesting class of continuous-time control systems that have appeared in the recent literature dealing with quantum communication and control systems.An interesting aspect of this extension is that it brings together heretofore independent research themes that have been prominent in the research career of Roger Brockett.
Recent papers have treated control communication complexity in the context of information-based, multiple agent control systems including nonlinear systems of the type that have been studied in connection with quantum information processing. The present paper continues this line of investigation into a class of two-agent distributed control systems in which the agents cooperate in order to realize common goals that are determined via independent actions undertaken individually by the agents. A basic assumption is that the actions taken are unknown in advance to the other agent. These goals can be conveniently summarized in the form of a target matrix, whose entries are computed by the control system responding to the choices of inputs made by the two agents. We show how to realize such target matrices for a broad class of systems that possess an input-output mapping that is bilinear. One can classify control-communication strategies, known as control protocols, according to the amount of information sharing occurring between the two agents. Protocols that assume no information sharing on the inputs that each agent selects and protocols that allow sufficient information sharing for identifying the common goals are the two extreme cases. Control protocols will also be evaluated and compared in terms of cost functionals given by integrated quadratic functions of the control inputs. The minimal control cost of the two classes of control protocols are analyzed and compared. The difference in the control costs between the two classes reflects an inherent trade-off between communication complexity and control cost.
Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles such as the superposition principle, entanglement, and interference. Until recently the common notion of computing was based on classical mechanics and did not take into account all the possibilities that physically realizable computing devices offer in principle. The field gained momentum after Shor developed an efficient algorithm for factoring numbers, demonstrating the potential computing powers that quantum computing devices can unleash. In this review the information counterpart of computing is studied. It was realized early on by Holevo that quantum bits, the quantum mechanical counterpart of classical bits, cannot be used for efficient transformation of information in the sense that arbitrary k-bit messages cannot be compressed into messages of $k\ensuremath{-}1$ qubits. The abstract form of the distributed computing setting is called communication complexity. It studies the amount of information, in terms of bits or in our case qubits, that two spatially separated computing devices need to exchange in order to perform some computational task. Surprisingly, quantum mechanics can be used to obtain dramatic advantages for such tasks. The area of quantum communication complexity is reviewed and it is shown how it connects the foundational physics questions regarding nonlocality with those of communication complexity studied in theoretical computer science. The first examples exhibiting the advantage of the use of qubits in distributed information-processing tasks were based on nonlocality tests. However, by now the field has produced strong and interesting quantum protocols and algorithms of its own that demonstrate that entanglement, although it cannot be used to replace communication, can be used to reduce the communication exponentially. In turn, these new advances yield a new outlook on the foundations of physics and could even yield new proposals for experiments that test the foundations of physics.
Information complexity is the extension of classical information theory to the interactive setting, where instead of one-way transmission we are interested in back-and-forth communication. This approach has been very influential in communication complexity, where it enables us to prove powerful lower bounds by quantifying the amount of information the participants in the computation must reveal about their inputs. In this paper we study information complexity in the classical broadcast model: k parties with private inputs wish to compute some function of their inputs, and they communicate by sending messages (one at a time) over a broadcast channel. We measure how much information the players reveal about their inputs to an external observer. This is called external information cost.
In 1989, Ohya propose a new concept, so-called Information Dynamics (ID), to investigate complex systems according to two kinds of view points.One is the dynamics of state change and another is measure of complexity.In ID, two complexities C S and T S are introduced.C S is a measure for complexity of system itself, and T S is a measure for dynamical change of states, which is called a transmitted complexity.An example of these complexities of ID is entropy for information transmission processes.The study of complexity is strongly related to the study of entropy theory for classical and quantum systems.The quantum entropy was introduced by von Neumann around 1932, which describes the amount of information of the quantum state itself.It was extended by Ohya for C*-systems before CNT entropy.The quantum relative entropy was first defined by Umegaki for σ-finite von Neumann algebras, which was extended by Araki and Uhlmann for general von Neumann algebras and *-algebras, respectively.By introducing a new notion, the so-called compound state, in 1983 Ohya succeeded to formulate the mutual entropy in a complete quantum mechanical system (i.e., input state, output state and channel are all quantum mechanical) describing the amount of information correctly transmitted through the quantum channel.In this paper, we briefly review the entropic complexities for classical and quantum systems.We introduce some complexities by means of entropy functionals in order to treat the transmission processes consistently.We apply the general frames of quantum communication to the Gaussian communication processes.Finally, we discuss about a construction of compound states including quantum correlations.
Quantum information science has blossomed into a major research field over the past decade or so. In doing so, it has established links with several other areas of physics, computer science, and engineering. One of these areas is quantum control – the extension of control theory to physical systems whose dynamics are governed by quantum mechanics. Quantum control, like quantum information, is a fairly young field with remarkable technological consequences, and this cross-pollination is proving to be stimulating. In this thesis we explore some of the connections between quantum information and quantum control. In particular, (i) we examine quantum error correction from a quantum feedback control perspective, and demonstrate new continuous time implementations of quantum error correcting codes; (ii) we consider performing quantum feedback control experiments on a solid-state quantum computing architecture – circuit QED – and propose new measurement schemes that would enable such experiments; and (iii) we consider the problem of optimally estimating quantum processes, and in particular, analyze in detail the problem of optimally estimating a one-parameter quantum process.
Abstract. Quantum information processing is at the crossroads of physics, mathematics and computer science. It is concerned with that we can and cannot do with quantum information that goes beyond the abilities of classical information processing devices. Communication complexity is an area of classical computer science that aims at quantifying the amount of communication necessary to solve distributed computational problems. Quantum communication complexity uses quantum mechanics to reduce the amount of communication that would be classically required. Pseudo-telepathy is a surprising application of quantum information processing to communication complexity. Thanks to entanglement, perhaps the most nonclassical manifestation of quantum mechanics, two or more quantum players can accomplish a distributed task with no need for communication whatsoever, which would be an impossible feat for classical players. After a detailed overview of the principle and purpose of pseudo-telepathy, we present a survey of recent and no-so-recent work on the subject. In particular, we describe and analyse all the pseudo-telepathy games currently known to the authors. 1.