A quantum state is a map from operators to real numbers that are their expectation values. Evaluating this map always entails using some algorithm, for example contracting a tensor network. I propose a novel way of quantifying the complexity of a quantum state in terms of "query complexity": the number of times an efficient algorithm for computing correlation functions in the given state calls a certain subroutine. I construct such an algorithm for a general "state at a cutoff" in 1+1-dimensional field theory. The algorithm scans cutoff-sized intervals for operators whose expectation values will be computed. It can be written as a Matrix Product State, with individual matrices performing translations in the space of (cutoff-sized) intervals and reading off consecutive operator inputs. If we take the queried subroutine to be a translation in the space of intervals, query complexity counts "how many" intervals the algorithm visits--a notion of distance in the space of intervals. A unique distance function is consistent with the requisite notion of translations; therefore the query complexity of a state at a cutoff is unambiguously defined. In holographic theories, the query complexity evaluates to the integral of the Ricci scalar on a spatial slice enclosed by the bulk cutoff, which in pure AdS3 agrees with the volume proposal but otherwise departs from it.


Talk Number 20110029
Speaker Profile Bartek Czech
Perimeter Institute Recorded Seminar Archive