# Can quantum computer compute the sum of $n$ natural numbers in $\Theta(\log n)$ time?

Classical computer always requires no matter what $\Theta(n)$ time to compute the sum of $n$ natural numbers, but can quantum computer do that in $\Theta(\log n)$ time?

Given that $a$ is an infinite sequence of natural numbers defined either iteratively or recursively by some math formula and $a_i$ is an arbitrary natural number, an element of the infinite sequence $a$, for any arbitrary index $i \in \mathbb{N}.$

Then to compute the sum of the first $n$ natural numbers of the infinite sequence $a$ or in other words to compute $\displaystyle \sum_{i=1}^{n} a_i$

Classical computer always requires $\Theta(n)$ time to do that, but what about quantum computer? How much time does quantum computer requires? Can quantum computer do this computation in $\Theta(\log n)$ time?

Please assume that computation of $a_i$ for any index $i \in \mathbb{N}$ requires no longer than $\Theta(1)$ time.

• I'm not an expert, but an exponential speed up is unlikely. Grover's algorithm only gives a square root speed up. – Yuval Filmus Aug 12 '17 at 18:18
• If it is known if $\mathsf{QLOGTIME \subsetneq L}$, the answer is negative. – rus9384 Aug 12 '17 at 19:48
• But there is no answer to the question: "Is $QLOGTIME \subsetneq L?$" , this question is still unknown and open. Am I right? – Farewell Stack Exchange Aug 12 '17 at 19:55

No, a quantum computer can't sum $n$ outputs from a black box function in $O(\lg n)$ queries.

For example, you could use magic summing power to easily do asymptotically better than Grover's algorithm at searching for solutions to a predicate. Except Grover's algorithm is proven to be asymptotically optimal. Contradiction.

Also, magic summing would trivially prove that $NP \subseteq BQP$. To determine if problem X has a solution or not, you'd simply sum up the outputs of the black box "if input is a solution for problem X then output 1 else output 0".

• Did you mean: $NP \subseteq BQP$? – Farewell Stack Exchange Aug 13 '17 at 22:19
• @ErezZrihen Yeah. Fixed. – Craig Gidney Aug 13 '17 at 23:11