PIRSA:22110119 Scientific Series Quantum Information

DOI10.48660/22110119

Series: Perimeter Institute Quantum Discussions

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

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

Resources

Next talk

Related Talks