Bounds on quantum evolution complexity via lattice cryptography

Quantum complexity has recently become of great interest within black hole physics as the holographically dual quantity to the spatial volume behind a black hole horizon. However, it is still a problem to come up with a precise notion of quantum complexity that could be independently computed in the dual quantum theory. One existing notion is the geometric one, where complexity is the length of the shortest geodesic distance between the identity operator and the time evolution operator within the group of unitaries. A so-called complexity metric takes into account the difficulty of performing "non-local" operations by assigning a cost factor to directions associated with these operators. This notion of complexity is simply formulated but numerically it quickly becomes unmanageable to compute in generic systems that do not have Hilbert spaces of very low dimensions. In our group we have avoided this difficulty by minimizing the geodesic distance over a specific infinite set of curves, hereby obtaining an upper bound on the complexity of the time evolution operator. This minimization procedure is closely related to the closest vector problem, where given a lattice, one tries to find the lattice point that is closest to the original vector. This is a problem that is usually studied in lattice-based cryptography because of the extremely high computational demand in order to find an exact solution, which is also the reason why this problem is used as encryption. Luckily, there are algorithms at hand that can approximate the solution within polynomial time and through the use of such algorithms, we have obtained our upper bound on complexity. We have applied this bound on a certain set of systems called quantum resonant systems, which are new interacting quantum-mechanical models with an infinite-dimensional Hilbert space. They arise upon quantizing classical resonant systems, which provide controlled approximations to the dynamics of interesting classes of weakly nonlinear systems, including weakly interacting fields in AdS spacetime and weakly interacting Bose-Einstein condensates in harmonic traps. Our upper bound has shown the important ability to distinguish generic chaotic resonant systems (satisfying Wigner-Dyson statistics) from generic integrable resonant systems (satisfying Poisson statistics). This is demonstrated by explicit numerical work for Hilbert spaces of dimensions up to ~10^4.