PIRSA: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. https://pirsa.org/22110119

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

          @misc{ pirsa_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},
            year = {2022},
            month = {nov},
            note = {PIRSA:22110119 see, \url{https://pirsa.org}}
          }

Alexander Meiburg University of California System

DOI 10.48660/22110119
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