QMA 완료 문제가 약속 문제인 이유는 무엇입니까? 완성 문제가 명백한

양자 복잡성 이론에 관한 논문에 대한 Watrous의 훌륭한 설문지를 읽고 있습니다. 그는 QMA 완성 문제가 명백한 약속 (즉, 언어)을 가지고있는 것으로 밝혀지면 놀라운 일이라고 말합니다. 왜 그렇습니까?

k-local Hamiltonian 문제가 약속 문제라는 사실과 관련이 있습니까?

또한 이것은 관련 질문으로 이어집니다. 본질적으로 “양자”가 아닌 QMA 완료 문제가 있습니까?

답변

두 번째 질문 : http://arxiv.org/abs/0905.4755v2 는 전형적인 QMA 완전 고유 값 문제 관련 Markov 체인을 제공합니다.

답변