Timeline for Is it possible to "calculate" the absolute value of a permanent using Boson Sampling?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 14, 2023 at 20:02 | history | edited | Mark Spinelli | CC BY-SA 4.0 |
added 7 characters in body
|
| Jun 7, 2018 at 6:55 | comment | added | DaftWullie | @user1271772 er... It is not true that every single element of $V$ is involved in evaluating $V|0\rangle$, only the first column of $V$ is relevant. That was the point that I was making: they're just the same. | |
| Jun 7, 2018 at 6:54 | history | edited | DaftWullie | CC BY-SA 4.0 |
added 1009 characters in body
|
| Jun 6, 2018 at 17:54 | comment | added | user1271772 No more free time | "If I start in some basis state $|0\rangle$ and find its product, $V|0\rangle$, then knowing that tells me very little about the outputs $V|1\rangle$ and $V|2\rangle$", but every single element of $V$ is involved in giving you $V|0\rangle$. But for boson sampling, only the first $M$ columns are involved, isn't that amazing? | |
| Jun 6, 2018 at 17:37 | comment | added | DaftWullie | @gls I agree that you cannot do it if you want an estimate of the permanent with some multiplicative error bound, which, admittedly, is the standard way of defining things (but since I carefully avoided defining anything...). If you’re willing to tolerate an additive error bound, then I believe you can do it. | |
| Jun 6, 2018 at 14:44 | comment | added | glS♦ | @DaftWullie sorry, now I'm confused. Do we agree that boson sampling does not allow to efficiently estimate permanents? (see e.g. bottom of left column at pag 6 of arxiv.org/pdf/1406.6767.pdf) | |
| Jun 6, 2018 at 14:42 | comment | added | DaftWullie | @glS No, that's very much what I'm saying. The Aaronson paper is very careful to distinguish that issue, but it makes the computational complexity statement a lot messier, which is why I didn't state it. | |
| Jun 6, 2018 at 13:14 | comment | added | glS♦ | I'm not sure whether this is what you are saying, but it is not true that solving efficiently BosonSampling allows to efficiently estimate the permanents, which would imply that quantum computers are able to solve #P-hard problems. In other words, quantum computers can efficiently simulate the output of a boson sampler, but not efficiently compute its output probability distribution | |
| Jun 6, 2018 at 12:17 | history | edited | DaftWullie | CC BY-SA 4.0 |
added 2030 characters in body
|
| Jun 6, 2018 at 5:37 | history | edited | DaftWullie | CC BY-SA 4.0 |
added 45 characters in body
|
| Jun 6, 2018 at 5:18 | history | answered | DaftWullie | CC BY-SA 4.0 |