Pergunta

I'm familiar with results of relativized separation for BPP-BQP, BQP-PH and NPC-BQP. I'm also aware that while e.g. Factoring is not believed to be in BPP, it hasn't been proven and so we're not quite near proving BQP!=BPP.

My question is, do we have any certain, theoretical, unrelativized proof that quantum computers are "superior" to classical one on any specific problem - Where here, I define superior to include any sort of runtime complexity superiority, so e.g. a quadratic improvement would qualify in this regard.

I'd expect Grover's algorithm to qualify for this criterion - But despite being supposedly "obvious", I'm not sure if it's been proven that classical computers can't solve it in sqrt(n) time as well, in a non-black-box model (i.e. unrelativized).

Nenhuma solução correta

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