Timeline for Why is Google's quantum supremacy experiment impressive?
Current License: CC BY-SA 4.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 20, 2021 at 22:52 | history | edited | knzhou | CC BY-SA 4.0 |
added 5 characters in body
|
| May 3, 2020 at 18:24 | comment | added | RBarryYoung | @VolkerSiegel Sorry, I missed this before... But, NP-Complete does not necessarily mean "worse than exponential" There are some NP-complete problems, such as the Change-Making problem that can definitely be solved in exponential-only time. However, all NP-complete problems are at least O(n^k * 2^n) where k is some constant value (including zero). | |
| Nov 1, 2019 at 22:11 | comment | added | Volker Siegel | @tparker Oh, thanks for clarifying it - it was explicitly not a good place for not being exact. | |
| Nov 1, 2019 at 22:02 | comment | added | tparker | @VolkerSiegel Your correction is not quite right either - specifcally, your claim that "The number of steps required is known, and mathematically proven." The minimum number of time steps to solve Traveling Salesman is not known, and in fact even just a proof that it's greater than polynomial would prove that $\textbf{P} \neq \textbf{NP}$, which most definitely has not been proven. | |
| Nov 1, 2019 at 15:57 | comment | added | JimmyJames | @William You are missing the important part: will it have a delicious skin on it? | |
| Nov 1, 2019 at 2:23 | comment | added | user182521 | @PasserBy Yes, you can, your question didn't ask whether you would die or not. | |
| Oct 31, 2019 at 22:13 | comment | added | Chris♦ | @StianYttervik No, it cannot. The traveling salesman problem isn't even known to be in BQP- under the best known algorithm it still can't be done in polynomial time even on a quantum computer. See this answer, for instance. The quantum speedup for NP-complete problems is only quadratic- it turns $2^N$ steps to $2^{N\over 2}$, basically. So problems that take exponential time still take exponential time. | |
| Oct 31, 2019 at 21:50 | comment | added | Stian | @chris and volker Mea culpa, i had a brain fart about the unable part, the point was that for a quantum computer it can be done with 1 step, trivially if you manage to arrange the system - compared to classical computer where the problem explodes in complexity. So certainly there are very exciting things in contemporary work, especially in how to program for the clusters | |
| Oct 31, 2019 at 20:22 | comment | added | Volker Siegel | @StianYttervik That's very wrong: The traveling salesman problem is solvable by any classical computer. It can be solved in a finite number of steps and finite time. The number of steps required is known, and mathematically proven. It just takes long because it's many steps. Same for any other NP complete problem. Very important is that all we are talking about is done in finite numbers of steps. (There are other things that are not, and my brain hurts even thinking of that) | |
| Oct 31, 2019 at 20:15 | comment | added | Volker Siegel | @RBarryYoung What you mean is "worse than exponential", exponential would be "just fine", almost... The traveling salesman needs exponential multiplied by the square of n. | |
| Oct 31, 2019 at 18:19 | comment | added | RBarryYoung | The issue with NP-complete problems is not that they are "not solvable", but rather that they are not tractable. That is, that trivial increases in the size of the problem's inputs result in literally exponential (or worse) increases in the run-time to calculate a solution. | |
| Oct 31, 2019 at 16:54 | comment | added | Jeffrey | Add reproduceability. They could spill their pudding over and over again and get the same result (up to the sampling precision). In real world pudding spill, you'd get different spill every time | |
| Oct 31, 2019 at 16:18 | comment | added | Chris♦ | @StianYttervik That is not true. The traveling salesman problem is an NP-complete problem, and as such is certainly solvable by a classical computer. And the best known algorithm for NP-complete problems on a quantum computer are barely faster than on a classical computer. | |
| Oct 31, 2019 at 13:49 | comment | added | Stian | But no matter how well you program a classic computer, it's unable to solve a problem like the traveling salesman problem in a finite number of steps, while a quantum computer can solve it (trivially) in 1 step - if you manage how to ask it... | |
| Oct 31, 2019 at 7:19 | comment | added | Passer By | But can you eat your quantum computer? | |
| Oct 31, 2019 at 4:44 | comment | added | slebetman | @Bridgeburners They did not merely show that they can set up a 53 qbit circuit (that's like showing you can implement a for loop in your CPU). They showed that they can calculate the probability distribution of the interference pattern of laser scattering - a specific program that happens to use 53 qbit. It's like saying you've written a ray-tracing program for a parallel cluster that uses some gigabits of RAM. It was not just a random program they were running | |
| Oct 30, 2019 at 18:36 | history | edited | knzhou | CC BY-SA 4.0 |
added 32 characters in body
|
| S Oct 30, 2019 at 18:26 | history | edited | knzhou | CC BY-SA 4.0 |
FPGA stands for Field Programmable Gate Array, and they are Programmable. Changing this to a calculator chip, which isn't, corrects the analogy.
|
| S Oct 30, 2019 at 18:26 | history | suggested | CommunityBot | CC BY-SA 4.0 |
FPGA stands for Field Programmable Gate Array, and they are Programmable. Changing this to a calculator chip, which isn't, corrects the analogy.
|
| Oct 30, 2019 at 18:02 | comment | added | d_b | It's impressive that there is any problem that we can solve easily on a quantum computer but not on a classical computer. To quote Scott Aaronson in the NY Times: "The calculation doesn’t need to be useful: much like the Wright Flyer in 1903, or Enrico Fermi’s nuclear chain reaction in 1942, it only needs to prove a point." | |
| Oct 30, 2019 at 17:59 | review | Suggested edits | |||
| S Oct 30, 2019 at 18:26 | |||||
| Oct 30, 2019 at 17:31 | comment | added | Bridgeburners | Would it be accurate to say, then, that this is impressive as an engineering feat? Specifically, they showed that they can set up a 53-bit quantum circuit, and sample it quickly. But in order to extrapolate that we can do impressive calculations, we have to trust that there exist theoretical 53-qubit algorithms that can do important calculations that classical computers can't do efficiently. Is that the right way to interpret it? | |
| Oct 30, 2019 at 17:17 | history | answered | knzhou | CC BY-SA 4.0 |