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.

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

1 Answer 1


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".

  • $\begingroup$ Did you mean: $NP \subseteq BQP$? $\endgroup$ Commented Aug 13, 2017 at 22:19
  • 1
    $\begingroup$ @ErezZrihen Yeah. Fixed. $\endgroup$ Commented Aug 13, 2017 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.