Skip to main content
added 6 characters in body
Source Link
Craig Gidney
  • 5.9k
  • 23
  • 48

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 \in BQP$$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".

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

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

Source Link
Craig Gidney
  • 5.9k
  • 23
  • 48

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