Nakata, YoshifumiYoshifumiNakataTakeuch, YukiYukiTakeuchKliesch, MartinMartinKlieschDarmawan, AndrewAndrewDarmawan2024-11-052024-11-052024-10-30arXiv:2410.23353 (2024)https://hdl.handle.net/11420/49965We 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.enhttps://creativecommons.org/licenses/by/4.0/quant-phcond-mat.stat-mechhep-thmath-phmath.MPNatural Sciences and Mathematics::510: MathematicsComputer Science, Information and General Works::004: Computer SciencesPreprinthttps://doi.org/10.15480/882.1382310.48550/arXiv.2410.2335310.15480/882.138232410.23353Preprint