Fidelity

Quantum mechanics

Function (biology)

Algorithm

Computational complexity theory

Biology

Theoretical computer science

Time complexity

Telecommunications

Computer science

Worst-case complexity

Mathematical optimization

Hamiltonian (control theory)

Statistical physics

Electronic circuit

Evolutionary biology

Physics

Mathematics

Circuit complexity

Time evolution

Journal of High Energy Physics

A bstract In this work, we propose a testing procedure to distinguish between the different approaches for computing complexity. Our test does not require a direct comparison between the approaches and thus avoids the issue of choice of gates, basis, etc. The proposed testing procedure employs the information-theoretic measures Loschmidt echo and Fidelity; the idea is to investigate the sensitivity of the complexity (derived from the different approaches) to the evolution of states. We discover that only circuit complexity obtained directly from the wave function is sensitive to time evolution, leaving us to claim that it surpasses the other approaches. We also demonstrate that circuit complexity displays a universal behaviour — the complexity is proportional to the number of distinct Hamiltonian evolutions that act on a reference state. Due to this fact, for a given number of Hamiltonians, we can always find the combination of states that provides the maximum complexity; consequently, other combinations involving a smaller number of evolutions will have less than maximum complexity and, hence, will have resources. Finally, we explore the evolution of complexity in non-local theories; we demonstrate the growth of complexity is sustained over a longer period of time as compared to a local theory.

Time evolution of complexity: a critique of three methods