Timeline for Can Shor's Algorithm be modified to run efficiently on a classical computer?
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 27, 2015 at 1:04 | comment | added | Craig Feinstein | It seems to me that the problem here is precisely the negative weights. My proposed Monte Carlo simulation doesn't solve the problem. | |
| 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 26, 2015 at 18:23 | comment | added | Hari Krovi | You might want to look at these papers. arxiv.org/abs/quant-ph/0611156 and arxiv.org/abs/quant-ph/0611241 | |
| Apr 26, 2015 at 16:29 | comment | added | Craig Feinstein | @CarloBeenakker thank you, I'll check that paper out. | |
| Apr 26, 2015 at 15:39 | answer | added | Will Sawin | timeline score: 17 | |
| Apr 26, 2015 at 15:38 | comment | added | Carlo Beenakker | the problem you are running into with the negative weight in your Monte Carlo algorithm is the infamous "negative sign problem"; it is believed to be NP-hard --- arxiv.org/abs/cond-mat/0408370 | |
| Apr 26, 2015 at 15:34 | history | edited | Craig Feinstein | CC BY-SA 3.0 |
added word "fundamentally"
|
| Apr 26, 2015 at 15:25 | history | edited | Craig Feinstein | CC BY-SA 3.0 |
added comment about zeb's comment
|
| Apr 26, 2015 at 15:18 | comment | added | Craig Feinstein | @Zeb, in general yes. But when looking at Shor's original paper arxiv.org/abs/quant-ph/9508027, the quantum gates that he uses for the Fourier transform are simple enough that perhaps normalizing the columns in the new matrices will not mess things up too badly. | |
| Apr 26, 2015 at 10:09 | comment | added | zeb | Wait - "normalize the columns of the new matrix"? Doesn't this step completely mess up the algorithm? | |
| Apr 26, 2015 at 9:24 | comment | added | user9072 |
It can be easier to typeset matrices using the command that exists to that end $\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$ $\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$
|
|
| Apr 26, 2015 at 9:23 | history | edited | user9072 | CC BY-SA 3.0 |
fixed broken MJ
|
| Apr 26, 2015 at 7:25 | history | edited | Ricardo Andrade | CC BY-SA 3.0 |
replaced new tag with existing ones; added relevant tags
|
| Apr 26, 2015 at 7:18 | history | edited | Ricardo Andrade | CC BY-SA 3.0 |
replaced new tag with existing ones; added relevant tags
|
| Apr 26, 2015 at 6:42 | comment | added | Geoffrey Irving | Any boolean circuit can be turned into a Bayesian network, so if MCMC always works then P = NP. | |
| Apr 26, 2015 at 5:12 | history | asked | Craig Feinstein | CC BY-SA 3.0 |