Timeline for CS conjecture that Quantum Computer cannot solve NP-complete problems, but Boson Samplers do a #P-hard problem. How is it?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 27, 2021 at 10:31 | comment | added | Norbert Schuch | @user777 You are aware that for two sets, there's possibilities which lie beyond one being inside the other - like they intersect? | |
| Jan 27, 2021 at 4:10 | comment | added | user777 | If this suggests that BQP is not inside PH, then this imply that NP-complete problems lies in BQP since all NP problems lies in PH. Then, why people conjectures (very likely) that quantum computer cannot solve NP-complete problems efficiently? | |
| Jan 27, 2021 at 4:06 | vote | accept | user777 | ||
| Jan 26, 2021 at 13:22 | comment | added | Norbert Schuch | This only suggests that BQP is not inside PH. | |
| Jan 26, 2021 at 10:53 | comment | added | user777 | 1. Some years ago, there was a result that shows an oracle separation between BQP and PH, they show that there exists a problem in BQP but not in PH relative to some oracle. Doesn't tell that BQP should be greater than class PH? 2. If I compare $BPP^{NP}$ with NP-complete, then which is harder? | |
| Jan 22, 2021 at 16:38 | history | edited | Norbert Schuch | CC BY-SA 4.0 |
added 311 characters in body
|
| Jan 22, 2021 at 16:32 | history | answered | Norbert Schuch | CC BY-SA 4.0 |