Mengapa QMA menyelesaikan masalah menjadi masalah janji?

10

Saya membaca makalah survei Watrous yang sangat bagus di atas kertas tentang teori kompleksitas kuantum. Di dalamnya ia menyatakan bahwa akan mengejutkan jika masalah lengkap QMA ditemukan memiliki janji yang kosong (Ie Be a language). Kenapa begitu?

Apakah itu ada hubungannya dengan fakta bahwa masalah Hamiltonian k-local adalah masalah yang menjanjikan?

Juga, ini membawa saya ke pertanyaan terkait: apakah ada masalah lengkap QMA yang secara inheren tidak "kuantum"?

cc.complexity-theory quantum-computing Henry Yuen
sumber
3
Saya kira itu akan menjadi hal yang menarik karena QMA didefinisikan sebagai kelas semantik, masalah yang lengkap akan memberikan karakterisasi sintaksis. Periksa pertanyaan terkait tentang kelas kompleksitas sintaksis / semantik di cstheory / Mathoverflow.
Kaveh
3
Selain itu, fenomena ini tidak spesifik untuk QMA pada khususnya. Kelas-kelas lain yang didefinisikan secara semantik seperti MA adalah BPP juga tidak diketahui memiliki bahasa lengkap.
Robin Kothari
1
Saya bertanya-tanya apa kondisi yang diperlukan dan cukup dalam praktik untuk masalah menjadi "tidak kuantum". Saya kira bahwa setiap masalah yang melibatkan peta yang benar-benar positif ( misalnya apakah peta CP yang diberikan tidak dapat dibalik, atau jauh dari yang tidak dapat dibalik?) Atau struktur produk tensor ( misalnya apakah operator semidefinit positif, yang diberikan dalam presentasi k-local, memiliki nilai eigen kurang dari delta, atau semuanya jauh lebih besar daripada delta?) akan menjadi contoh masalah kuantum yang mencurigakan, apakah mereka disajikan dalam hal saluran kuantum / evolusi atau ruang keadaan sistem agregat ...
Niel de Beaudrap

Jawaban: