Timeline for Does having multiple quantum computers in parallel speed up Shor's Algorithm?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 7, 2017 at 0:10 | comment | added | Norbert Schuch | It might make sense to explain this in your answer. | |
| Nov 6, 2017 at 1:21 | comment | added | Craig Gidney | @NorbertSchuch It's just about running gates in parallel. | |
| Nov 6, 2017 at 0:34 | comment | added | Norbert Schuch | But then how is this different from just having a single larger quantum computer? And if it isn't, wouldn't it be faster to just run Shor on this machine? Or do you claim you have found a new way to speed up Shor's algorithm? Or is this all only about being able to execute gates in parallel (i.e., counting gates by depth)? | |
| Nov 6, 2017 at 0:18 | comment | added | Craig Gidney | @NorbertSchuch Yes. You have to get the intermediate products back into one place to combine them, and they have to stay coherent or the later uncomputation will fail. | |
| Nov 5, 2017 at 23:16 | comment | added | Norbert Schuch | I think my question can be summarized as follows: Is it required to pass quantum states from one quantum computer to another? | |
| Nov 5, 2017 at 22:43 | comment | added | Craig Gidney | @NorbertSchuch I don't understand what you mean by classical-vs-quantum parallelization. To factor an N-bit number, the naive circuit for Shor's algorithm performs N controlled modular multiplications. Those controlled multiplications are commutative and associative. This allows you to group them, do the groups in parallel, then merge the groups. Because we need reversibility there is the additional step of uncomputing the intermediate groups. | |
| Nov 5, 2017 at 21:54 | comment | added | Norbert Schuch | But is it any smarter than just to try them in parallel classically? (I mean, in factoring one has to do mod. exp. w/ different exponents, and these can be parallelized, because the algorithm just tries one after the other. but that's not particularly quantum. I guess you refer to sth. else? To be honest, I don't understand your answer. What is N? And if your answer does parallelize in a quantum way, I'd first like to know what model you consider, and how this even differs from just having a larger quantum computer.) | |
| Nov 5, 2017 at 20:53 | comment | added | Craig Gidney | @NorbertSchuch Given the lay phrasing of the question, I don't want to split hairs about what's "really" using multiple computers. Suffice it to say that some of the work can be done in parallel. | |
| Nov 5, 2017 at 20:12 | comment | added | Norbert Schuch | Are your parallel quantum computers talking to each other? If yes, why not make them a big computer? | |
| Nov 5, 2017 at 3:09 | history | answered | Craig Gidney | CC BY-SA 3.0 |
