Chaos, Entanglement and Computation

In a world governed by the laws of classical physics, there is a well-defined notion of complexity, based on deterministic chaos, which implies the inevitable loss of predictability of the evolution of a system in a classical simulation. Deterministic chaos, one of the most significant discoveries of the last century, allows us to reconcile the determinism of physical laws and the apparent chaoticity of natural phenomena, which we observe in everyday life. Quantum dynamics is instead very stable, in sharp contrast to the extreme sensitivity to initial conditions and rapid loss of memory that is the very essence of chaos. On the other hand, in the quantum world, complexity can be attributed rather to entanglement, which is the key resource in the search for quantum advantage in quantum computing. This chapter discusses the consequences of the distinct features of classical and quantum dynamics on the cost of classical and quantum computation of complex systems.