Timeline for What are the strongest arguments for a genuine quantum computing advantage?
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 15, 2021 at 19:00 | answer | added | Gil Kalai | timeline score: 5 | |
| Dec 15, 2021 at 15:10 | answer | added | Ryan O'Donnell | timeline score: 8 | |
| Dec 11, 2021 at 14:57 | comment | added | user6873235 | @Chuu We already know mathematically that Shor's Algorithm breaks RSA encryption specifically, though not other types of encryption. This is still important because much of internet encryption relies on RSA for various reasons. Other types of classical encryption exist which don't seem vulnerable to Shor's Algorithm but they're often impractical, and we don't know if they're vulnerable to different (possibly undiscovered) quantum algorithms. Because of this, much research is going into post-quantum cryptography, classical schemes that can resist quantum computers. | |
| Dec 10, 2021 at 16:18 | comment | added | Chuu | @SamHopkins A novice here, but wouldn't they know if Shor's Algorithm would break existing cryptographic systems without actually having to have the hardware to implement it? | |
| Dec 10, 2021 at 15:40 | comment | added | Steve Huntsman | @SamHopkins Breaking RSA is probably not actually that useful. Folks have been considering post-quantum crypto for a long time now. "Only" older systems and encrypted documents are likely to be vulnerable to quantum attacks. Meanwhile, most proposed applications are unserious, as they require impractical amounts of quantum RAM (i.e., loading data takes much longer than solving). Besides quantum simulation, optimization, Monte Carlo techniques and their ilk are probably the lowest hanging and sweetest fruit. Topological data analysis is also something that might work well. | |
| Dec 9, 2021 at 23:08 | comment | added | polfosol | You might also be interested in this related question and the answers therein | |
| Dec 9, 2021 at 20:21 | history | edited | Carlo Beenakker |
edited tags
|
|
| Dec 9, 2021 at 17:08 | comment | added | Timothy Chow | I agree with Sam Hopkins that practical considerations dominate when it comes to funding. Suppose I have an important problem, and I know that Method A solves it. To justify spending money on implementing Method A, I don't really need powerful evidence that no other method can possibly work. I might spend some money trying to come up with Method B, but it's always a murky question how much effort to invest in something that might or might not work, vs. something that you're confident will work. It's sort of a multi-armed bandit problem. | |
| Dec 9, 2021 at 16:51 | history | became hot network question | |||
| Dec 9, 2021 at 16:43 | comment | added | Sam Hopkins | Let me put it this way: suppose someone came up with an efficient (classical!) factorization algorithm, whose correctness relied on the truth of the Riemann Hypothesis. Would that cause a redoubled effort to prove the RH? Or would it more likely lead to people trying to implementing the algorithm and break codes in practice? | |
| Dec 9, 2021 at 15:13 | answer | added | Timothy Chow | timeline score: 27 | |
| Dec 9, 2021 at 14:45 | comment | added | user6873235 | @SamHopkins True, though given all the money put into solving engineering concerns, at least some of that surely might have been put into theorists investigating if classical counterparts exist. I guess more generally I included that detail to emphasise the stakes involved in assuming the answer to an unsolved question. | |
| Dec 9, 2021 at 14:35 | comment | added | Sam Hopkins | The fact that "billions of dollars" have been "dumped into the field" is probably more a reflection of the practical advantages of a quantum computer: with Shor's algorithm they have a great hope of breaking existing cryptography systems based on integer factorization (whether or not those systems are theoretically classically secure). | |
| Dec 9, 2021 at 12:19 | answer | added | JoshuaZ | timeline score: 15 | |
| Dec 9, 2021 at 10:57 | history | edited | user6873235 | CC BY-SA 4.0 |
Added a clarification for "ideal quantum computer".
|
| Dec 9, 2021 at 9:21 | answer | added | Carlo Beenakker | timeline score: 16 | |
| Dec 9, 2021 at 8:57 | comment | added | Alex M. | There is also Grover's algorithm. | |
| S Dec 9, 2021 at 8:48 | review | First questions | |||
| Dec 9, 2021 at 8:57 | |||||
| S Dec 9, 2021 at 8:48 | history | asked | user6873235 | CC BY-SA 4.0 |