Increasing complexity with quantum physics

We argue that complex systems science and the rules of quantum physics are intricately related. We discuss a range of quantum phenomena, such as cryptography, computation and quantum phases, and the rules responsible for their complexity. We identify correlations as a central concept connecting quantum information and complex systems science. We present two examples for the power of correlations: using quantum resources to simulate the correlations of a stochastic process and to implement a classically impossible computational task.     

The effect of microscopic correlations on the information geometric complexity of Gaussian statistical models

We present an analytical computation of the asymptotic temporal behavior of the information geometric complexity (IGC) of finite-dimensional Gaussian statistical manifolds in the presence of microcorrelations (correlations between microvariables). We observe a power law decay of the IGC at a rate determined by the correlation coefficient. It is found that microcorrelations lead to the emergence of an asymptotic information geometric compression of the statistical macrostates explored by the system at a faster rate than that observed in the absence of microcorrelations. This finding uncovers an important connection between (micro)correlations and (macro)complexity in Gaussian statistical dynamical systems.     

A measure of statistical complexity based on predictive information with application to finite spin systems

We propose the binding information as an information theoretic measure of complexity between multiple random variables, such as those found in the Ising or Potts models of interacting spins, and compare it with several previously proposed measures of statistical complexity, including excess entropy, Bialek et al.?s predictive information, and the multi-information. We discuss and prove some of the properties of binding information, particularly in relation to multi-information and entropy, and show that, in the case of binary random variables, the processes which maximise binding information are the ‘parity’ processes. The computation of binding information is demonstrated on Ising models of finite spin systems, showing that various upper and lower bounds are respected and also that there is a strong relationship between the introduction of high-order interactions and an increase of binding-information. Finally we discuss some of the implications this has for the use of the binding information as a measure of complexity.     

The computational complexity of generating random fractals

We examine a number of models that generate random fractals. The models are studied using the tools of computational complexity theory from the perspective of parallel computation. Diffusion-limited aggregation and several widely used algorithms for equilibrating the Ising model are shown to be highly sequential; it is unlikely they can be simulated efficiently in parallel. This is in contrast to Mandelbrot percolation, which can be simulated in constant parallel time. Our research helps shed light on the intrinsic complexity of these models relative to each other and to different growth processes that have been recently studied using complexity theory. In addition, the results may serve as a guide to simulation physics.     

Predictability: a way to characterize complexity

Different aspects of the predictability problem in dynamical systems are reviewed. The deep relation among Lyapunov exponents, Kolmogorov–Sinai entropy, Shannon entropy and algorithmic complexity is discussed. In particular, we emphasize how a characterization of the unpredictability of a system gives a measure of its complexity. Adopting this point of view, we review some developments in the characterization of the predictability of systems showing different kinds of complexity: from low-dimensional systems to high-dimensional ones with spatio-temporal chaos and to fully developed turbulence. A special attention is devoted to finite-time and finite-resolution effects on predictability, which can be accounted with suitable generalization of the standard indicators. The problems involved in systems with intrinsic randomness is discussed, with emphasis on the important problems of distinguishing chaos from noise and of modeling the system. The characterization of irregular behavior in systems with discrete phase space is also considered.     

模糊熵算法在混沌序列复杂度分析中的应用

为了准确分析混沌序列的复杂性, 采用模糊熵算法(FuzzyEn) 对典型离散混沌系统和连续混沌系统的复杂度进行分析. 与近似熵(ApEn)、 样本熵(SampEn) 和强度统计复杂度算法相比, FuzzyEn算法是一种更有效的混沌复杂度测度算法, 且对相空间维数(m)、 相似容限度(r) 和序列长度(N) 的敏感性、 依赖性更低, 鲁棒性和测度值的连续性更好. 对混沌系统的复杂性分析表明, 连续混沌系统的复杂度远小于离散混沌系统, 但是如果利用高复杂度的离散混沌伪随机序列或经典 m序列对连续混沌系统产生的伪随机序列进行扰动, 则能大大提高混沌序列的复杂性. 为混沌序列在密码学和混沌保密通信中的应用提供了理论依据.     

Natural computation measured as a reduction of complexity

We argue that the deeper nature of computation is to reduce the statistical obstruction against prediction. From this, we derive an explicit measure of computation for general, artificial as well as natural, systems (electronic circuits, neurons, mechanical devices, etc.). The applicability and usefulness of this concept is demonstrated using well-studied families of dynamical systems, as well as experimental time series from cortical neurons.     

A complexity measure approach based on forbidden patterns and correlation degree

Based on forbidden patterns in symbolic dynamics, symbolic subsequences are classified and relations between forbidden patterns, correlation dimensions and complexity measures are studied. A complexity measure approach is proposed in order to separate deterministic (usually chaotic) series from random ones and measure the complexities of different dynamic systems. The complexity is related to the correlation dimensions, and the algorithm is simple and suitable for time series with noise. In the paper, the complexity measure method is used to study dynamic systems of the Logistic map and the H\'enon map with multi-parameters.     

基于强度统计算法的混沌序列复杂度分析

为了分析混沌序列的复杂度,文中采用强度统计复杂度算法分别对离散混沌系统(TD-ERCS)和连续混沌系统(简化Lorenz系统)进行复杂度分析,计算了混沌序列随参数变化的复杂度,分析了连续混沌系统产生的伪随机序列分别进行m序列和混沌伪随机序列扰动后的复杂度.研究表明,强度统计复杂度算法是一种有效的复杂度分析方法,离散混沌序列复杂度大于连续混沌序列复杂度,但对连续混沌系统的伪随机序列进行m序列和混沌伪随机序列扰动后可大大增加复杂度,为混沌序列在信息加密中的应用提供了理论依据. 关键词： 强度统计复杂度算法 TD-ERCS系统 简化Lorenz系统 序列扰动     

Asymptotically optimal quantum circuits for d-level systems

Scalability of a quantum computation requires that the information be processed on multiple subsystems. However, it is unclear how the complexity of a quantum algorithm, quantified by the number of entangling gates, depends on the subsystem size. We examine the quantum circuit complexity for exactly universal computation on many d-level systems (qudits). Both a lower bound and a constructive upper bound on the number of two-qudit gates result, proving a sharp asymptotic of theta(d(2n)) gates. This closes the complexity question for all d-level systems (d finite). The optimal asymptotic applies to systems with locality constraints, e.g., nearest neighbor interactions.     

Multistability and the control of complexity

We show how multistability arises in nonlinear dynamics and discuss the properties of such a behavior. In particular, we show that most attractors are periodic in multistable systems, meaning that chaotic attractors are rare in such systems. After arguing that multistable systems have the general traits expected from a complex system, we pass to control them. Our controlling complexity ideas allow for both the stabilization and destabilization of any one of the coexisting states. The control of complexity differs from the standard control of chaos approach, an approach that makes use of the unstable periodic orbits embedded in an extended chaotic attractor. (c) 1997 American Institute of Physics.     

Space-time complexity in Hamiltonian dynamics

New notions of the complexity function C(epsilon;t,s) and entropy function S(epsilon;t,s) are introduced to describe systems with nonzero or zero Lyapunov exponents or systems that exhibit strong intermittent behavior with "flights," trappings, weak mixing, etc. The important part of the new notions is the first appearance of epsilon-separation of initially close trajectories. The complexity function is similar to the propagator p(t(0),x(0);t,x) with a replacement of x by the natural lengths s of trajectories, and its introduction does not assume of the space-time independence in the process of evolution of the system. A special stress is done on the choice of variables and the replacement t-->eta=ln t, s-->xi=ln s makes it possible to consider time-algebraic and space-algebraic complexity and some mixed cases. It is shown that for typical cases the entropy function S(epsilon;xi,eta) possesses invariants (alpha,beta) that describe the fractal dimensions of the space-time structures of trajectories. The invariants (alpha,beta) can be linked to the transport properties of the system, from one side, and to the Riemann invariants for simple waves, from the other side. This analog provides a new meaning for the transport exponent mu that can be considered as the speed of a Riemann wave in the log-phase space of the log-space-time variables. Some other applications of new notions are considered and numerical examples are presented.     

Scaling and universality of the complexity of analog computation

We apply a probabilistic approach to study the computational complexity of analog computers which solve linear programming problems. We numerically analyze various ensembles of linear programming problems and obtain, for each of these ensembles, the probability distribution functions of certain quantities which measure the computational complexity, known as the convergence rate, the barrier and the computation time. We find that in the limit of very large problems these probability distributions are universal scaling functions. In other words, the probability distribution function for each of these three quantities becomes, in the limit of large problem size, a function of a single scaling variable, which is a certain composition of the quantity in question and the size of the system. Moreover, various ensembles studied seem to lead essentially to the same scaling functions, which depend only on the variance of the ensemble. These results extend analytical and numerical results obtained recently for the Gaussian ensemble, and support the conjecture that these scaling functions are universal.     

Changing dynamical complexity with time delay in coupled fiber laser oscillators

We investigate the complexity of the dynamics of two mutually coupled systems with internal delays and vary the coupling delay over 4 orders of magnitude. Karhunen-Loève decomposition of spatiotemporal representations of fiber laser intensity data is performed to examine the eigenvalue spectrum and significant orthogonal modes. We compute the Shannon information from the eigenvalue spectra to quantify the dynamical complexity. A reduction in complexity occurs for short coupling delays while a logarithmic growth is observed as the coupling delay is increased.     

"Metric" complexity for weakly chaotic systems

We consider the number of Bowen sets necessary to cover a large measure subset of the phase space. This introduces some complexity indicator characterizing different kinds of (weakly) chaotic dynamics. Since in many systems its value is given by a sort of local entropy, this indicator is quite simple to calculate. We give some examples of calculations in nontrivial systems (e.g., interval exchanges and piecewise isometries) and a formula similar to that of Ruelle-Pesin, relating the complexity indicator to some initial condition sensitivity indicators playing the role of positive Lyapunov exponents.     

Permutation entropy: a natural complexity measure for time series

We introduce complexity parameters for time series based on comparison of neighboring values. The definition directly applies to arbitrary real-world data. For some well-known chaotic dynamical systems it is shown that our complexity behaves similar to Lyapunov exponents, and is particularly useful in the presence of dynamical or observational noise. The advantages of our method are its simplicity, extremely fast calculation, robustness, and invariance with respect to nonlinear monotonous transformations.     

The reflection phenomenon and complexity engine as statistical physics tools for the advanced evolution phenomenon

We intend to uncover generative principles for complex, biological systems, looking the reflections as well as the analogs of decision making property in quantum physics: measurement, self-interaction of the electron, Berry phase and quantum anomalies. We assume that classical analogs of the mentioned phenomena could be related to the evolvability, growing of complexity and decision making in biological systems. The reflection is a map (coarse graining) from microscopic motions to a macroscopic scale that relates with a free-energy cost and is often accompanied by the emergence of order-parameters. In this context we identify the self-reflection phenomenon, which is exemplified by cognition, information transfer near the error threshold, and tightly related evolution-ecology phenomena. We propose that complex systems that have similar reflection structure are to be described by similar mathematical tools including stochastic (information) thermodynamics and the large deviation theory. We introduce the concept of complexity engine: the group of two (or more) autonomous features of complex systems that are in a partial conflict with each other. Analogues of this are wave-particle duality in quantum mechanics and data-program duality in digital life. We formulate a fundamental problem: does the three-dimensional space provide a complexity engine for the emergence of life?