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$ – Yuval Filmus Aug 12 '17 at 18:18
  • 1
    $\begingroup$ If it is known if $\mathsf{QLOGTIME \subsetneq L}$, the answer is negative. $\endgroup$ – rus9384 Aug 12 '17 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$ – 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".

| cite | improve this answer | |
  • $\begingroup$ Did you mean: $NP \subseteq BQP$? $\endgroup$ – Farewell Stack Exchange Aug 13 '17 at 22:19
  • 1
    $\begingroup$ @ErezZrihen Yeah. Fixed. $\endgroup$ – Craig Gidney Aug 13 '17 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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