Pergunta

I was wondering if there is a complexity class for problems that can be solved efficiently by a quantum computer such that it always gives the right answer? For example the Deutsch-Josza algorithm never fails. Another way of asking would be: is there a class (call it Q) such that Q is to P what BQP is to BPP?

I guess classically the question also makes sense: is there a class for problems that can be solved efficiently by a computer with access to randomness and never making an error? (I suspect this is simply equal to P?)

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top