Um algoritmo quântico para casos não abelianos de HSP

Abstract

Resumo: O problema do subgrupo oculto, denominado HSP (de Hidden Subgroup Problem), é um problema candidato à classe de problemas NP-intermediários. A versão de decisão de HSP, denominada dHSP (de decision Hidden Subgroup Problem), é o problema de promessa de decidir se o subgrupo oculto é o subgrupo trivial ou não. Apresentamos uma análise de um algoritmo quântico de multiplicação de coclasses para dHSP, exibindo casos de grupos não abelianos que geram um estado próximo do estado maximamente misto, quando o subgrupo oculto não é o subgrupo trivial, e, por outro lado, geram um estado puro quando o subgrupo oculto é o subgrupo trivial. Adicionalmente, investigamos a relação de dHSP com classes de complexidade de conhecimento zero, apresentando casos particulares deste problema que estão em NIPZK1, a classe de problemas que admitem provas não-interativas de conhecimento zero perfeito com completude perfeita.

Abstract: The Hidden Subgroup Problem (HSP) is a well-known candidate for NP-intermediate status. The decision version of HSP, called dHSP (short for Decision Hidden Subgroup Problem), is the promise problem of deciding whether the hidden subgroup is the trivial subgroup or not. We present an analysis of a coset multiplication quantum algorithm for dHSP, showing cases of non-abelian groups that the algorithm generate a state close to the maximally mixed state when the hidden subgroup is not the trivial subgroup, and, on the other hand, generate a pure state when the hidden subgroup is the trivial subgroup. Additionally, we investigate the relationship between dHSP and complexity classes of zero knowledge, presenting particular cases of this problem that are in NIPZK1, the class of problems that admit non-interactive perfect zero-knowledge proofs with perfect completeness.