On Computational Complexity of Unitary and State Design Properties

Abstract

We investigate unitary and state $t$-designs from a computational complexity perspective. First, we address the problems of computing frame potentials that characterize (approximate) $t$-designs. We present a quantum algorithm for computing frame potentials and establish the following: (1) exact computation can be achieved by a single query to a $\#\text{P}$-oracle and is $\#\text{P}$-hard; (2) for state vectors, deciding whether the frame potential is larger than or smaller than certain values is $\text{BQP}$-complete, provided the promise gap between the two values is inverse-polynomial in the number of qubits; and (3) for both state vectors and unitaries, this promise problem is $\text{PP}$-complete if the promise gap is exponentially small. Second, we address the promise problem of deciding whether or not a given set is a good approximation to a design. Given a certain promise gap that could be constant, we show that this problem is $\text{PP}$-hard, highlighting the inherent computational difficulty of determining properties of unitary and state designs. We further identify the implications of our results across diverse areas, including variational methods for constructing designs, diagnosing quantum chaos through out-of-time-ordered correlators (OTOCs), and exploring emergent designs in Hamiltonian systems.

Ver 1. 22 pages, 1 figure, and 1 table. Ver 2. 27 pages, 1 figure, and 1 table. Results are updated and implications are added. Ver 3. 33 pages, 2 figures, and 1 table. An error in a previous proof is fixed. Ver 4. published version

References in corpus (64)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A bound on chaos
• Improved Simulation of Stabilizer Circuits
• Black holes as mirrors: quantum information in random subsystems
• Characterizing Quantum Supremacy in Near-Term Devices
• Fast Scramblers
• The foundations of statistical mechanics from entanglement: Individual states vs. averages
• Randomized Benchmarking of Quantum Gates
• Robust randomized benchmarking of quantum processes
• Quantum mechanical evolution towards thermal equilibrium
• On the quantum, classical and total amount of correlations in a quantum state
• Quantum information can be negative
• Scalable Noise Estimation with Random Unitary Operators
• A Theory of Trotter Error
• Characterizing Quantum Gates via Randomized Benchmarking
• Chaos and complexity by design
• Towards the fast scrambling conjecture
• Evenly distributed unitaries: on the structure of unitary designs
• Randomizing quantum states: Constructions and applications
• The computational complexity of PEPS
• Local random quantum circuits are approximate polynomial-designs
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Quantum state merging and negative information
• The mother of all protocols: Restructuring quantum information's family tree
• Optimal quantum control using randomized benchmarking
• Preparing random states and benchmarking with many-body quantum chaos
• Characterizing errors on qubit operations via iterative randomized benchmarking
• One-shot decoupling
• A general framework for randomized benchmarking
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Relating quantum privacy and quantum coherence: an operational approach
• Exact emergent quantum state designs from quantum chaotic dynamics
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Random bosonic states for robust quantum metrology
• Dynamical purification and the emergence of quantum state designs from the projected ensemble
• Efficient unitary designs with nearly time-independent Hamiltonian dynamics
• Quantum commitments and signatures without one-way functions
• Solvable model of deep thermalization with distinct design times
• Decoupling with unitary approximate two-designs
• Mixing properties of stochastic quantum Hamiltonians
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Quantum Cryptography in Algorithmica
• A Maximum Entropy Principle in Deep Thermalization and in Hilbert-Space Ergodicity
• Quantum circuits for exact unitary $t$-designs and applications to higher-order randomized benchmarking
• Randomized benchmarking for individual quantum gates
• Characterizing complexity of many-body quantum dynamics by higher-order eigenstate thermalization
• Benchmarking Quantum Simulators using Ergodic Quantum Dynamics
• Efficient Quantum Tensor Product Expanders and k-designs
• Relative Thermalization
• Complete Hilbert-Space Ergodicity in Quantum Dynamics of Generalized Fibonacci Drives
• Phase-random states: ensembles of states with fixed amplitudes and uniformly distributed phases in a fixed basis
• Experimental implementation of non-Clifford interleaved randomized benchmarking with a controlled-S gate
• Deep thermalization in constrained quantum systems
• Basic trigonometric power sums with applications
• Black holes as clouded mirrors: the Hayden-Preskill protocol with symmetry
• One-shot quantum error correction of classical and quantum information
• Efficient Unitary T-designs from Random Sums
• Efficient unitary designs and pseudorandom unitaries from permutations
• Phase Retrieval Using Unitary 2-Designs
• Hilbert-Space Ergodicity in Driven Quantum Systems: Obstructions and Designs
• Optimal Conversion from Classical to Quantum Randomness via Quantum Chaos
• One-Shot Triple-Resource Trade-Off in Quantum Channel Coding
• Decoding general error correcting codes and the role of complementarity

Cited by in corpus (2)

• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• Non-Clifford Cost of Random Unitaries