Essentially, how useful is it to have multiple quantum computers in parallel if the goal is to, for example, recover a 2048 bit RSA key?
2
-
$\begingroup$ Just 2^1024 computers, and you can do it in (almost) constant time! $\endgroup$– Norbert SchuchCommented Nov 5, 2017 at 20:13
-
$\begingroup$ It is not clear at all what "in parallel" means here. What do you mean? $\endgroup$– Norbert SchuchCommented Nov 6, 2017 at 0:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
Yes, parallel computing can reduce the time it takes to perform Shor's algorithm.
For example, the meat of Shor's algorithm is a modular exponentiation. Which you could perform via N conditional multiplications one after another. Instead of that, you could do $\sqrt{N}$ groups of $\sqrt{N}$ conditional multiplications, then do $\sqrt{N}$ multiplications to combine the intermediate results together into the final product, then uncompute the intermediate states with $\sqrt{N}$ groups of $\sqrt{N}$ conditional un-multiplications. This reduces the multiplication-depth from $N$ to $3 \sqrt{N}$.
Of course that's just a simple example. There's lots of other stuff you can do. Pick your favorite classical parallel binary multiplier circuit, and derive a quantum circuit from it. Or do even more multiplications in parallel.
That being said, quantum computers already need to operate every qubit constantly in order to perform error correction. So they are going to naturally be operated in a very parallel way. There's no need to wait for a second or third computer before you start thinking about parallelization.
answered Nov 5, 2017 at 3:09
-
$\begingroup$ Are your parallel quantum computers talking to each other? If yes, why not make them a big computer? $\endgroup$ Commented Nov 5, 2017 at 20:12
-
$\begingroup$ @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. $\endgroup$ Commented Nov 5, 2017 at 20:53
-
$\begingroup$ 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.) $\endgroup$ Commented Nov 5, 2017 at 21:54
-
$\begingroup$ @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. $\endgroup$ Commented Nov 5, 2017 at 22:43
-
$\begingroup$ I think my question can be summarized as follows: Is it required to pass quantum states from one quantum computer to another? $\endgroup$ Commented Nov 5, 2017 at 23:16
