Quantum computing means breaking Bounded Quantum Polynomial, not NP. Integer fac... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		lolcraft on June 29, 2013 \| parent \| context \| favorite \| on: Large-scale quantum chip validated Quantum computing means breaking Bounded Quantum Polynomial, not NP. Integer factorization is in NP, and also in BQP; but some problems can just as well be in NP and not in BQP. And NP-complete is not a subset of BQP, as far as anyone knows.

dllthomas on June 29, 2013 [–]

Strictly, we don't actually know BQP is more powerful than P, right?

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact