Timeline for What are the strongest arguments for a genuine quantum computing advantage?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 15, 2021 at 20:42 | comment | added | Pace Nielsen | Regarding Shor's algorithm, I found the paper arxiv.org/abs/2104.11616 very interesting in this regard. Is their algorithm classical, quantum, or something else entirely? | |
| Dec 15, 2021 at 19:10 | comment | added | Gil Kalai | Timothy, my work (with Kindler) is about classical algorithms for noisy Boson Sampling. (Boson Sampling is genuinly very hard even to approximate.) | |
| Dec 11, 2021 at 16:56 | comment | added | Timothy Chow | @JoshuaZ Good point! My favorite example of a nonrelativizing separation is Vinodchandran's result that for all $k$, $\mathsf{PP} \not\subseteq \mathsf{SIZE}(n^k)$. Aaronson showed that there is an oracle $A$ such that $\mathsf{PP}^A \subseteq \mathsf{SIZE}^A(n)$. | |
| Dec 11, 2021 at 13:54 | comment | added | JoshuaZ | "since people have proved relativized versions of all kinds of things that we believe are false" Minor note- you actually have a stronger statement here. We've proven relativized versions of things we know are false. IP=PSPACE is true in the non-relativized situation, but we can give oracles where it is false. (I don't know of a natural example where A != B, but they are equal in the relativized context, but it wouldn't surprise me if we have those also.) | |
| Dec 10, 2021 at 21:58 | comment | added | Timothy Chow | I checked with Scott Aaronson to see if I missed anything. He said the only thing he would add is that chemists and physicists have been searching fruitlessly for efficient (classical) simulations of quantum behavior for nearly a century, so that provides some empirical support for $\mathsf{PromiseBPP} \ne \mathsf{PromiseBQP}$. I also want to mention that Gil Kalai, who is famously skeptical of QC, finds random circuit sampling convincing. I believe the only reason he doesn't accept that Google's experiment establishes quantum supremacy is that he suspects they made a mistake somewhere. | |
| Dec 9, 2021 at 17:26 | history | edited | Timothy Chow | CC BY-SA 4.0 |
added 619 characters in body
|
| Dec 9, 2021 at 15:13 | history | answered | Timothy Chow | CC BY-SA 4.0 |