PIRSA:22110119

Video URL

https://pirsa.org/22110119

Quantum Constraint Problems can be complete for BQP, QCMA, and BPP

Meiburg, A. (2022). Quantum Constraint Problems can be complete for BQP, QCMA, and BPP. Perimeter Institute for Theoretical Physics. https://pirsa.org/22110119

Meiburg, Alexander. Quantum Constraint Problems can be complete for BQP, QCMA, and BPP. Perimeter Institute for Theoretical Physics, Nov. 30, 2022, https://pirsa.org/22110119 

          @misc{ scivideos_PIRSA:22110119,
            doi = {10.48660/22110119},
            url = {https://pirsa.org/22110119},
            author = {Meiburg, Alexander},
            keywords = {Quantum Information},
            language = {en},
            title = {Quantum Constraint Problems can be complete for BQP, QCMA, and BPP},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2022},
            month = {nov},
            note = {PIRSA:22110119 see, \url{https://scivideos.org/pirsa/22110119}}
          }

Alexander Meiburg University of California System

Talk numberPIRSA:22110119
DOI10.48660/22110119
Source RepositoryPIRSA
Collection
Talk Type Scientific Series
Subject

Abstract

Constraint satisfaction problems are known to always be "easy" or "hard", in the sense of being either solvable in P or being NP-complete, with no intermediate difficulty levels. The quantum analog of constraint problems, frustration-free Hamiltonians, are known to exhibit at least two more levels of complexity: QMA (for arbitrary local Hamiltonians) and MA (for stoquastic Hamiltonians). Wondering if other complexity classes can occur, we answer in the affirmative: there are interactions which can be freely arranged on qubits in any arrangement, such that the resulting frustration problem is BQP-complete, and captures exactly the difficulty of quantum computation. Simple modifications of this construction show that quantum constraint problems can be complete for QCMA and BPP as well. Based on https://arxiv.org/abs/2101.08381