patternMinor
Can quantum computer compute the sum of $n$ natural numbers in $\Theta(\log n)$ time?
Viewed 0 times
thetacanthecomputelognumberstimecomputernaturalsum
Problem
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.
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.
Solution
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".
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".
Context
StackExchange Computer Science Q#79990, answer score: 5
Revisions (0)
No revisions yet.