Information Processing in Complex Systems (IPCS) Session 2
Time and Date: 14:15  18:00 on 20th Sep 2016
Room: B  Berlage zaal
Chair: Rick Quax
45010  Quantum Complexity
[abstract] 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.

Vlatko Vedral 
45009  The classicalquantum divergence of complexity in the Ising spin chain
[abstract] 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.

Whei Yeap Suen, Jayne Thompson, Andrew Garner, Vlatko Vedral and Mile Gu 
45011  Occam's Quantum Strop
[abstract] 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 stateindistinguishability 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 ordera 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 costone trades off prediction for generation complexity.

John Mahoney, James Crutchfield and Cina Aghamohammadi 
45012  Classification of timesymmetry breaking in quantum walks on graphs
[abstract] 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 timereversal 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 timesymmetric. Leaving the classification problem and its implications, open. Here we provide a full classification of the Hamiltonians which enable the breaking of timereversal 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 timereversal symmetry. These results fill an important missing gap in understanding the role this omnipresent effect has in quantum information science.

Jacob Turner and Jacob Biamonte 
45008  The Ambiguity of Simplicity
[abstract] 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.

James Crutchfield, Cina Aghamohammadi and John Mahoney 
45007  Increasing excess entropy in the approach towards equilibrium in a reversible Ising dynamics model
[abstract] 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 informationtheoretic analysis of the onedimensional, infinite lattice version of the Q2R model. Its twodimensional version has been extensively used for simulation of the twodimensional 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.

Kristian Lindgren and Eckehard Olbrich 
45005  Mutual information reveals lowerlevel mechanisms, aiding higher level predictability
[abstract] 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 farfromequilibrium manyparticle system is representative of many other complex systems.

Karoline Wiesner 
45013  Unbounded memory advantage in stochastic simulation using quantum mechanics
[abstract] Abstract: Simulations using real quantities on a digital computer require a tradeoff 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.

Andrew Garner, Qing Liu, Jayne Thompson, Vlatko Vedral and Mile Gu 