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

### APA

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

### MLA

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

### BibTex

@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

## 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