Timeline for Can Shor's Algorithm be modified to run efficiently on a classical computer?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 21, 2016 at 15:17 | comment | added | Will Sawin | @DominiqueUnruh Well, one should read what I wrote in context. The reason the oracle problem is relevant here is that, if Craig Feinstein's strategy works for factoring, it necessarily works for the oracle problem as well. | |
| Dec 21, 2016 at 12:43 | comment | added | Dominique Unruh | @WillSawin True, if the function is given as an oracle, abelian hidden subgroup is provably hard. If the function is given as a circuit (or in any other white-box way), then it abelian HSG might be easy (e.g., if P=NP). If abelian HSG is given an oracle, but the oracle is required to be implemented by a poly-time algorithm -- then I don't know. So I guess your statement is right depending on the interpretation, but I still feel that it's good that we have this comment threat to point out that it's not all clear black-and-white. :) | |
| Dec 20, 2016 at 12:10 | comment | added | Will Sawin | @DominiqueUnruh It is not proven for real-world problems but it is known for oracle problemss. The abelian hidden subgroup problem is an oracle problem, which unless I am very confused has no fast classical algorithm for the reason I described. | |
| Dec 20, 2016 at 10:03 | comment | added | Dominique Unruh | "But there is no fast classical algorithm for the abelian hidden subgroup problem" -- I think you should phrase this "no fast classical algorithm is known". Although it is commonly believed that quantum computers are more powerful than classical ones, this is not proven. | |
| Apr 27, 2015 at 0:50 | vote | accept | Craig Feinstein | ||
| Apr 27, 2015 at 0:49 | vote | accept | Craig Feinstein | ||
| Apr 27, 2015 at 0:49 | |||||
| Apr 27, 2015 at 0:49 | comment | added | Craig Feinstein | I think you are correct, @willsawin. | |
| Apr 26, 2015 at 18:40 | comment | added | Will Sawin | @CraigFeinstein Yes, the classical steps of the computation are permutation matrices, which are not problematic. What I mean by "just the Fourier transform" is that the only thing we do to the sequence $x^a$ mod $n$ is compute it and then apply the Fourier transform. We don't investigate its properties using deep number theory technology. | |
| Apr 26, 2015 at 18:04 | comment | added | Craig Feinstein | I don't follow your reasoning. Shor's algorithm doesn't just take the Fourier Transform. It computes $x^a (\bmod n)$ too. But the unitary matrices associated with these computations do not appear to be problematic, as they are just permutation matrices, right? | |
| Apr 26, 2015 at 15:39 | history | answered | Will Sawin | CC BY-SA 3.0 |