¿Por qué los problemas completos de QMA deben ser problemas de promesa?

10

Estoy leyendo la excelente encuesta de Watrous sobre la teoría de la complejidad cuántica. En él, afirma que sería sorprendente si se descubriera que un problema completo de QMA tiene una promesa vacía (es decir, ser un lenguaje). ¿Por qué esto es tan?

¿Tiene que ver con el hecho de que el problema hamiltoniano k-local es un problema prometedor?

Además, esto me lleva a una pregunta relacionada: ¿existen problemas completos de QMA que no son inherentemente de naturaleza "cuántica"?

cc.complexity-theory quantum-computing Henry Yuen
fuente
3
Supongo que sería algo interesante porque QMA se define como una clase semántica, un problema tan completo daría una caracterización sintáctica. Consulte las preguntas relacionadas sobre las clases de complejidad sintáctica / semántica en cstheory / Mathoverflow.
Kaveh
3
Además, este fenómeno no es específico de QMA en particular. Tampoco se sabe que otras clases definidas semánticamente como MA son BPP tengan idiomas completos.
Robin Kothari
1
Me pregunto cuáles son las condiciones necesarias y suficientes en la práctica para que un problema sea "no cuántico". Supongo que cualquier problema que invoque un mapa completamente positivo ( por ejemplo, ¿un mapa CP dado es invertible, o está lejos de ser invertible?) O la estructura del producto tensorial ( por ejemplo, ¿un operador semidefinito positivo, dado en una presentación k-local, tiene valores propios inferiores a delta, o son todos sustancialmente mayores que delta?) serían ejemplos de problemas cuánticos sospechosos, se presenten o no en términos de canales cuánticos / evolución o el espacio de estado de un sistema agregado ...
Niel de Beaudrap

Respuestas: