Information Processing in Complex Systems  (IPCS) Session 2

Abstract: I intend to review several notions of classical complexity and discuss how they might be quantized. The standard technique from quantum information is to measure a given quantum system whose complexity we want to know and then apply the classical measures to the resulting classical statistics. In order to obtain the quantum complexity we finally optimize (minimize or maximize) over all classically obtained results. However, it might be more appropriate to measure quantum complexity directly, i.e. not going via classical statistics. How might that be done? I also discuss complexity from the perspective of how difficult it is to make entangled states. This will lead me introduce the concept of quantum macroscopicity. Close

Abstract: Most interesting systems in nature are often complex, lying in the region between order and randomness. Even though the idea of complexity is understood intuitively, it lacks a formal mathematical description. The statistical complexity, defined by Crutchfield as the minimum information required by a classical model to statistically simulate a process, serves to quantify complexity. Here, we show that the same idea of complexity behaves differently in the quantum information regime. We introduce the quantum statistical complexity as the minimum information required by a quantum model to statistically simulate a process, and show that it exhibits drastically different qualitative behavior when applied to the same system - the 1D Ising spin chain. Thus, we illustrate that the notion of what is complex depends on the information theory used to describe it. Close

Abstract: A stochastic process's statistical complexity stands out as a fundamental property: the minimum information required to synchronize one process generatorto another. How much information is required, though, when synchronizing over aquantum channel? Recent work demonstrated that representing causal similarity as quantum state-indistinguishability provides a quantum advantage. We generalize this to synchronization and offer a sequence of constructions that exploit extended causal structures, finding substantial increase of the quantum advantage. We demonstrate that maximum compression is determined by the process's cryptic order---a classical, topological property closely allied to Markov order, itself a measure of historical dependence. We introduce an efficient algorithm that computes the quantum advantage and close noting that the advantage comes at a cost---one trades off prediction for generation complexity. Close

Abstract: Most interesting systems in nature are often complex, lying in the region between order and randomness. Even though the idea of complexity is understood intuitively, it lacks a formal mathematical description. The statistical complexity, defined by Crutchfield as the minimum information required by a classical model to statistically simulate a process, serves to quantify complexity. Here, we show that the same idea of complexity behaves differently in the quantum information regime. We introduce the quantum statistical complexity as the minimum information required by a quantum model to statistically simulate a process, and show that it exhibits drastically different qualitative behavior when applied to the same system - the 1D Ising spin chain. Thus, we illustrate that the notion of what is complex depends on the information theory used to describe it. Quantum walks on graphs represent an established model capturing essential physics behind a host of natural and synthetic phenomena. Quantum walks have further been proven to provide a universal model of quantum computation and have been shown to capture the core underlying physics of several biological processes in which quantum effects play a central role. A 'single particle quantum walker' moves on a graph, with dynamics governed by Schrödinger's equation and quantum theory predicts the probability of a walker to transition between the graphs' nodes. Any quantum process in finite dimensions can be viewed as a single particle quantum walk. Until recently, quantum walks implicitly modeled only probability transition rates between nodes which were symmetric under time inversion. Breaking this time-reversal symmetry provides a new arena to consider applications of this symmetry breaking and to better understand its foundations. The main application discovered so far is that this symmetry breaking can be utilized as a passive means to control and direct quantum transport. A subtle interplay between the assignment of complex Hamiltonian edge weights and the geometry of the underlying network has emerged in a sequence of studies. This interplay has been central to several works, but in the absence of definitive statements, past work has only produced criteria for a process on a graph to be time-symmetric. Leaving the classification problem and its implications, open. Here we provide a full classification of the Hamiltonians which enable the breaking of time-reversal symmetry in their induced transition probabilities. Our results are furthermore proven in terms of the geometry of the corresponding Hamiltonian support graph. We found that the effect can only be present if the underlying support graph is not bipartite whereas certain bipartite graphs give rise to transition probability suppression, but not broken time-reversal symmetry. These results fill an important missing gap in understanding the role this omnipresent effect has in quantum information science. Close

Abstract: A system’s apparent simplicity depends on whether it is represented classically or quantally. This is not so surprising, as classical and quantum physics are descriptive frameworks built on different assumptions that capture, emphasize, and express different properties and mechanisms. What is surprising is that, as we demonstrate, simplicity is ambiguous: the relative simplicity between two systems can change sign when moving between classical and quantum descriptions. Thus, notions of absolute physical simplicity—minimal structure or memory—at best form a partial, not a total, order. This suggests that appeals to principles of physical simplicity, via Ockham’s Razor or to the “elegance” of competing theories, may be fundamentally subjective, perhaps even beyond the purview of physics itself. It also presents a challenge to using quantum computers for statistical inference. Fortunately, experiments are now beginning to probe measures of simplicity, creating the potential to directly test for ambiguity. Close

Abstract: Dynamic models of spin systems, based on microscopic reversibility and conserved energy, have been used for simulation of the Ising model and the approach towards equilibrium. The equilibrium is here determined by the set of distributions, over configurations of finite blocks of spins, with increasing sizes, that with the given energy constraint maximises the entropy density. Since also the entropy density is conserved in such a dynamics, a natural question is whether the full equilibrium is really reached and how? We investigate this question in detail by making an information-theoretic analysis of the one-dimensional, infinite lattice version of the Q2R model. Its two-dimensional version has been extensively used for simulation of the two-dimensional Ising model. Starting from a low entropy state, with appropriate statistics, it is shown that despite the conserved entropy, if entropy is estimated only from finite size block statistics, entropy appears to be increasing and the equilibrium state for the given energy is approached. By showing how the excess entropy increases during this process, it is clarified how local order is transformed into correlation information over increasing distances, explaining the apparent entropy increase and the approach towards equilibrium. The findings are discussed in the broader context of reversible microscopic dynamics, macroscopic irreversibility, and the second law of thermodynamics. Close

Abstract: I will present some recent work on Shannon information theory applied to natural complex systems. As part of this we have developed a new correlation length function based on mutual information. I will discuss how it aids predictability of complex systems by detecting underlying mechanisms of change. One example I will present is a glass former, and I will discuss how this far-from-equilibrium many-particle system is representative of many other complex systems. Close

Abstract: Simulations using real quantities on a digital computer require a trade-off between the precision to which these quantities are stored, and the memory required to store them. The limit of the simulation's precision is hence limited by the internal memory available to the simulator. In this presentation, I shall demonstrate using tools from statistical complexity theory and its quantum extensions that quantum information processing allows the simulation of stochastic processes to arbitrarily high precision at a finite memory cost. This demonstrates the unbounded memory advantage that a quantum computer can exhibit over its best possible classical counterpart when used for stochastic simulations. Close