Query complexity and cutoffs in AdS3/CFT2

          @misc{ pirsa_PIRSA:20110029,
            doi = {10.48660/20110029},
            url = {https://pirsa.org/20110029},
            author = {Czech, Bartek},
            keywords = {Quantum Fields and Strings},
            language = {en},
            title = {Query complexity and cutoffs in AdS3/CFT2},
            publisher = {Perimeter Institute},
            year = {2020},
            month = {nov},
            note = {PIRSA:20110029 see, \url{https://pirsa.org}}
          }
          

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 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.