Query complexity and cutoffs in AdS/CFT

Abstract: 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 on 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 and the relevant subroutine is a translation in the space of (cutoff-sized) intervals. Query complexity then boils down to an appropriate notion of distance in the space of (cutoff-sized) 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.

HEP - theorymathematical physicsquantum physics

Audience: researchers in the topic

( video )

Purdue HET

Series comments: The recorded talks will be available on YouTube here: www.youtube.com/playlist?list=PLxU3vHZccQj64m9zsQR74D5WP1z1g4t1J