Por que os problemas completos do QMA devem ser promissores?

10

Estou lendo o excelente artigo de Watrous sobre a teoria da complexidade quântica. Nele, ele afirma que seria surpreendente se um problema completo de QMA tivesse uma promessa vazia (ou seja, um idioma). Porque isto é assim?

Isso tem a ver com o fato de que o problema hamiltoniano k-local é um problema promissor?

Além disso, isso me leva a uma pergunta relacionada: existem problemas completos no QMA que não são inerentemente "quânticos" por natureza?

cc.complexity-theory quantum-computing Henry Yuen
fonte
3
Eu acho que isso seria interessante porque o QMA é definido como uma classe semântica, um problema tão completo daria uma caracterização sintática. Verifique as perguntas relacionadas sobre as classes de complexidade sintática / semântica no cstheory / Mathoverflow.
precisa
3
Além disso, esse fenômeno não é específico ao QMA em particular. Outras classes semanticamente definidas como MA são BPP também não são conhecidas por terem linguagens completas.
Robin Kothari
11
Eu me pergunto quais são as condições necessárias e suficientes na prática para que um problema "não seja quântico". Suponho que qualquer problema que invoque um mapa completamente positivo ( por exemplo, um determinado mapa de CP seja invertível ou longe de ser invertível?) Ou estrutura de produto tensorial ( por exemplo , um operador semidefinido positivo, apresentado em uma apresentação k-local, tenha valores próprios inferiores a delta, ou todos são substancialmente maiores que delta?) seriam exemplos de problemas quânticos suspeitos, apresentados ou não em termos de canais / evolução quânticos ou no espaço de estados de um sistema agregado ...
Niel de Beaudrap

Respostas: