Quantum Computational Complexity and Symmetry

Abstract

Testing the symmetries of quantum states and channels provides a way to assess their usefulness for different physical, computational, and communication tasks. Here, we establish several complexity-theoretic results that classify the difficulty of symmetry-testing problems involving a unitary representation of a group and a state or a channel that is being tested. In particular, we prove that various such symmetry-testing problems are complete for BQP, QMA, QSZK, QIP(2), QIP_EB(2), and QIP, thus spanning the prominent classes of the quantum interactive proof hierarchy and forging a non-trivial connection between symmetry and quantum computational complexity. Finally, we prove the inclusion of two Hamiltonian symmetry-testing problems in QMA and QAM, while leaving it as an intriguing open question to determine whether these problems are complete for these classes.

28 pages, 10 figures, 1 table, submission to the journal special issue honoring A. Ravi P. Rau

References in corpus (30)

• Quantifying Coherence
• Quantum Coherence as a Resource
• Quantum Resource Theories
• General Entanglement Breaking Channels
• Toward the first quantum simulation with quantum speedup
• A complete family of separability criteria
• Distinguishing separable and entangled states
• The theory of manipulations of pure state asymmetry: basic tools and equivalence classes of states under symmetric operations
• Exploiting symmetry in variational quantum machine learning
• The SWAP test and the Hong-Ou-Mandel effect are equivalent
• Group-Invariant Quantum Machine Learning
• Modes of asymmetry: the application of harmonic analysis to symmetric quantum dynamics and quantum reference frames
• The power of symmetric extensions for entanglement detection
• Machine-learning hidden symmetries
• Revisiting the simulation of quantum Turing machines by quantum circuits
• Quantum Proofs
• Extendibility limits the performance of quantum processors
• Testing product states, quantum Merlin-Arthur games and tensor optimisation
• Estimating distinguishability measures on quantum computers
• Extremal covariant POVM's
• Optimal Measurements for Symmetric Quantum States with Applications to Optical Communication
• Detection of Multiparticle Entanglement: Quantifying the Search for Symmetric Extensions
• Quantum interactive proofs and the complexity of separability testing
• Testing symmetry on quantum computers
• Hierarchy of efficiently computable and faithful lower bounds to quantum discord
• Exponential speedup in measuring out-of-time-ordered correlators with a single bit of quantum information
• Cycle Index Polynomials and Generalized Quantum Separability Tests
• Symmetric extendibility of quantum states
• Schrödinger as a Quantum Programmer: Estimating Entanglement via Steering
• Efficient quantum algorithms for testing symmetries of open quantum systems

Cited by in corpus (1)

• The abelian state hidden subgroup problem: Learning stabilizer groups and beyond