Dlaczego pełne problemy QMA muszą być problemami obiecującymi?

10

Czytam doskonały papier ankietowy Watrous na papierze na temat teorii złożoności kwantowej. Stwierdza w nim, że byłoby zaskakujące, gdyby okazało się, że problem z QMA miałby pustą obietnicę (tj. Być językiem). Dlaczego tak jest?

Czy ma to związek z faktem, że k-lokalny problem hamiltonowski jest problemem obiecującym?

Prowadzi mnie to również do pytania pokrewnego: czy istnieją problemy związane z QMA, które nie są z natury „kwantowe”?

cc.complexity-theory quantum-computing Henry Yuen
źródło
3
Myślę, że byłoby to interesujące, ponieważ QMA jest zdefiniowana jako klasa semantyczna, taki kompletny problem dałby charakterystykę składniową. Sprawdź powiązane pytania dotyczące klas złożoności składniowej / semantycznej w cstheory / Mathoverflow.
Kaveh
3
Co więcej, zjawisko to nie dotyczy w szczególności QMA. Inne semantycznie zdefiniowane klasy, takie jak MA to BPP, również nie są znane z posiadania pełnych języków.
Robin Kothari
1
Zastanawiam się, jakie są niezbędne i wystarczające warunki w praktyce, aby problem nie był „kwantowy”. Przypuszczam, że jakikolwiek problem, który wywołuje całkowicie pozytywną mapę ( np. Czy dana mapa CP jest odwracalna, czy daleka od odwracalnej?) Lub struktura produktu tensorowego ( np. Czy dodatni operator pół-skończony, podany w prezentacji k-lokalnej, ma wartości własne mniejsze niż delta, czy wszystkie są znacznie większe niż delta?) byłyby przykładami podejrzanych problemów kwantowych, niezależnie od tego, czy są przedstawione w kategoriach kanałów kwantowych / ewolucji, czy przestrzeni stanu układu agregatów ...
Niel de Beaudrap

Odpowiedzi: