Existe uma classe complexidade qpp?

Question

A classe de complexidade PP não é considerada tratável, porque a probabilidade de sucesso pode ser arbitrariamente perto de 50% de cima, pois as instâncias de problemas são maiores, de modo que (por exemplo, se essa abordagem for exponencialmente rápida), um número inviável de repetiçõesser necessário antes de termos uma probabilidade significativa de distinguir confinando confusórios de insumos satisfatórios de não satisfatórios.No entanto, a PP é uma classe complexidade interessante para estudar por si só.

Existe uma classe complexidade de complexidade bem definida "QPP" de problemas que um computador quântico tem uma chance maior que 50% de resolver corretamente no tempo polinomial?Eu entendo que, em caso afirmativo, essa classe de problemas não seria viável em um computador quântico, mas quaisquer inclusões não triviais com as classes mais "tradicionais" complexidades comprovadas ou suspeitas?Quão "grandes" achamos que a classe QPP é?

Answer 1

yamakami mostrou em seu papel Análise de funções quânticas que o análogo quânticode pp é o mesmo que pp clássico.Isto é mencionado no Artigo de Wikipedia em pp.