# Is black box parallel quantum speedup ever nontrivial?

Grover's algorithm is not parallelizable, in that $$p$$ quantum processors searching over $$n$$ elements can't do better than $$O(\sqrt{n/p})$$ queries.

Are there any oracle problems where quantum computers see some polynomial speedup over classical, but where the algorithm is nontrivially parallelizable? Here's one attempt at formalizing this:

Question: Are there any oracle problems such that

1. The classical complexity is $$O(t)$$, and achieves perfect parallel speedup to $$O(t/p)$$.
2. The quantum complexity is $$O(t^\alpha)$$ for $$\alpha \in [1/4,1)$$.
3. The parallel quantum complexity is $$O(t^\alpha / p^\beta)$$, with $$\beta \in (\alpha,1]$$.

Even better, is there a problem where $$\beta = 1$$ (perfect parallel quantum speedup)?

• I don't know of such a function off the top of my head, but you may want to read this related paper of Jeffery, Magniez and de Wolf: arxiv.org/abs/1309.6116. They prove lower bounds on the parallel quantum query complexity of a number of functions beyond OR, such as element distinctness, using a parallel version of the quantum adversary method which tightly characterizes parallel quantum query complexity. Perhaps the parallel adversary method could give some insight into which functions might admit nontrivial quantum parallelization. Aug 19, 2020 at 2:09

Methinks, you do not understand the black-box magic of quantum processors.

It shall cover all n elements of a task by its cubits, otherwise, there would not be happen collapse of superposition over all input's elements and you would not even calculate anything.

For example, factorization algorithm: There shall be n + k cubits, where n - is a dimension of input, and k is support engine.

If your processor can not reach this dimension, you are not able to split input in n/p parts and feed p different processors to summarize result after, on exit...

Super-position of sum of p processors will be much lesser then super-position of one big n dimension processor. And quantum magic is exactly hidden in this dimension, means - number of cubits.

E.g. 3 CPU x 3 cubits each; This will give us such fields:

1st 2nd 3rd
000 000 000
001 001 001
010 010 010
011 011 011
100 100 100
101 101 101
110 110 110
111 111 111


This is how superposition will looks like. Three small quantum registers. And this field - is our calculation power here.

But, when you'll take One Big CPU with 9 cubits, this will give you 2^9 dimension = 512 different boolean vectors. And system will be in all of its while in super-position.

The "memory" of such quantum computer in super position will be much bigger:

000000000 000000001 000000010 000000011 000000100 000000101 000000110 000000111
000001000 000001001 000001010 000001011 000001100 000001101 000001110 000001111
000010000 000010001 000010010 000010011 000010100 000010101 000010110 000010111
000011000 000011001 000011010 000011011 000011100 000011101 000011110 000011111
000100000 000100001 000100010 000100011 000100100 000100101 000100110 000100111
000101000 000101001 000101010 000101011 000101100 000101101 000101110 000101111
000110000 000110001 000110010 000110011 000110100 000110101 000110110 000110111
000111000 000111001 000111010 000111011 000111100 000111101 000111110 000111111
001000000 001000001 001000010 001000011 001000100 001000101 001000110 001000111
001001000 001001001 001001010 001001011 001001100 001001101 001001110 001001111
001010000 001010001 001010010 001010011 001010100 001010101 001010110 001010111
001011000 001011001 001011010 001011011 001011100 001011101 001011110 001011111
001100000 001100001 001100010 001100011 001100100 001100101 001100110 001100111
001101000 001101001 001101010 001101011 001101100 001101101 001101110 001101111
001110000 001110001 001110010 001110011 001110100 001110101 001110110 001110111
001111000 001111001 001111010 001111011 001111100 001111101 001111110 001111111
010000000 010000001 010000010 010000011 010000100 010000101 010000110 010000111
010001000 010001001 010001010 010001011 010001100 010001101 010001110 010001111
010010000 010010001 010010010 010010011 010010100 010010101 010010110 010010111
010011000 010011001 010011010 010011011 010011100 010011101 010011110 010011111
010100000 010100001 010100010 010100011 010100100 010100101 010100110 010100111
010101000 010101001 010101010 010101011 010101100 010101101 010101110 010101111
010110000 010110001 010110010 010110011 010110100 010110101 010110110 010110111
010111000 010111001 010111010 010111011 010111100 010111101 010111110 010111111
011000000 011000001 011000010 011000011 011000100 011000101 011000110 011000111
011001000 011001001 011001010 011001011 011001100 011001101 011001110 011001111
011010000 011010001 011010010 011010011 011010100 011010101 011010110 011010111
011011000 011011001 011011010 011011011 011011100 011011101 011011110 011011111
011100000 011100001 011100010 011100011 011100100 011100101 011100110 011100111
011101000 011101001 011101010 011101011 011101100 011101101 011101110 011101111
011110000 011110001 011110010 011110011 011110100 011110101 011110110 011110111
011111000 011111001 011111010 011111011 011111100 011111101 011111110 011111111
100000000 100000001 100000010 100000011 100000100 100000101 100000110 100000111
100001000 100001001 100001010 100001011 100001100 100001101 100001110 100001111
100010000 100010001 100010010 100010011 100010100 100010101 100010110 100010111
100011000 100011001 100011010 100011011 100011100 100011101 100011110 100011111
100100000 100100001 100100010 100100011 100100100 100100101 100100110 100100111
100101000 100101001 100101010 100101011 100101100 100101101 100101110 100101111
100110000 100110001 100110010 100110011 100110100 100110101 100110110 100110111
100111000 100111001 100111010 100111011 100111100 100111101 100111110 100111111
101000000 101000001 101000010 101000011 101000100 101000101 101000110 101000111
101001000 101001001 101001010 101001011 101001100 101001101 101001110 101001111
101010000 101010001 101010010 101010011 101010100 101010101 101010110 101010111
101011000 101011001 101011010 101011011 101011100 101011101 101011110 101011111
101100000 101100001 101100010 101100011 101100100 101100101 101100110 101100111
101101000 101101001 101101010 101101011 101101100 101101101 101101110 101101111
101110000 101110001 101110010 101110011 101110100 101110101 101110110 101110111
101111000 101111001 101111010 101111011 101111100 101111101 101111110 101111111
110000000 110000001 110000010 110000011 110000100 110000101 110000110 110000111
110001000 110001001 110001010 110001011 110001100 110001101 110001110 110001111
110010000 110010001 110010010 110010011 110010100 110010101 110010110 110010111
110011000 110011001 110011010 110011011 110011100 110011101 110011110 110011111
110100000 110100001 110100010 110100011 110100100 110100101 110100110 110100111
110101000 110101001 110101010 110101011 110101100 110101101 110101110 110101111
110110000 110110001 110110010 110110011 110110100 110110101 110110110 110110111
110111000 110111001 110111010 110111011 110111100 110111101 110111110 110111111
111000000 111000001 111000010 111000011 111000100 111000101 111000110 111000111
111001000 111001001 111001010 111001011 111001100 111001101 111001110 111001111
111010000 111010001 111010010 111010011 111010100 111010101 111010110 111010111
111011000 111011001 111011010 111011011 111011100 111011101 111011110 111011111
111100000 111100001 111100010 111100011 111100100 111100101 111100110 111100111
111101000 111101001 111101010 111101011 111101100 111101101 111101110 111101111
111110000 111110001 111110010 111110011 111110100 111110101 111110110 111110111
111111000 111111001 111111010 111111011 111111100 111111101 111111110 111111111


You can factorize number lesser than 2^9, for example 465 on such QCPU, but you can not factorize this number on bunch of little QCPU with 3 cubits per each.

465 - it is 111 010 001. So, how do you plan to split it, to feed by parts to each little QCPU? First will factorize 111, second 010, third 001? And how to sum such result on exit? There is no way.

As you can see, 3 QCPU x 3cubits - is not the same as 1 QCPU x 9cubits. And each new cubit increase power of QCPU by multiplying its calculation field on two. x2, x2, x2, x2... so, you could fast reach the number of stars in the visible universe or even atoms, or quarks,.. photons... and even exceed it... Simply, knot more and more cubits in superposition. But you can not achieve the same, by printing more and more small quantum computers, because the effect will be linear, not exponential.