Esta pergunta surge de uma resposta que Joe Fitzsimons deu a uma pergunta diferente . A maioria das classes de complexidade natural possui uma "descrição intuitiva" de uma linha que ajuda a caracterizar os principais problemas dessa classe. NP é "verificação eficiente", #P é "enumerar soluções", PSPACE é "jogo" e assim por diante.
Em geral, eu entendi MA como BP (NP), onde a etapa M fornece o adivinhador de NP, e a etapa A é a parte da BP, e, portanto, as perguntas sobre a relação entre MA e NP são realmente questões de des randomização. Então, minha pergunta é:
Existe alguma maneira natural de entender o que o QMA captura?
fonte
A maioria das classes quânticas estudadas (como QMA, BQP, QIP e exóticas como QMIP e QRG) tem uma contrapartida clássica e você obtém a classe quântica pensando quantumly e alterando sua definição de "computação eficiente" para "tempo polinomial em um computador quântico ".
A maneira mais fácil de obter uma classe quântica da maioria das classes clássicas naturais é alterar a noção de "computação eficiente" de P ou BPP para BQP e alterar a noção de troca de informações de bits para qubits. Assim, por exemplo, QIP é o mesmo que IP quando o verificador BPP é feito BQP e a comunicação permite qubits em vez de bits.
fonte