On computational complexity of unitary and state design properties

We study unitary and state t-designs from a computational complexity theory perspective. First, we address the problems of computing frame potentials that characterize (approximate) t-designs. We provide a quantum algorithm for computing the frame potential and show that 1. exact computation can be achieved by a single query to a #P-oracle and is #P-hard, 2. for state vectors, it is BQP-complete to decide whether the frame potential is larger than or smaller than certain values, if the promise gap between the two values is inverse-polynomial in the number of qubits, and 3. both for state vectors and unitaries, it is PP-complete if the promise gap is exponentially small. As the frame potential is closely related to the out-of-time-ordered correlator (OTOCs), our result implies that computing the OTOCs with exponential accuracy is also hard. Second, we address promise problems to decide whether a given set is a good or bad approximation to a t design and show that this problem is in PP for any constant t and is PP-hard for t = 1, 2 and 3. Remarkably, this is the case even if a given set is promised to be either exponentially close to or worse than constant away from a 1-design. Our results illustrate the computationally hard nature of unitary and state designs.