  The recent Google's claim on breakthrough in quantum computing is a gong
signal for further analysis of foundational roots of (possible) superiority of
some quantum algorithms over the corresponding classical algorithms. This note
is a step in this direction. We start with critical analysis of rather common
reference to entanglement and quantum nonlocality as the basic sources of
quantum superiority. We elevate the role of the Bohr's {\it principle of
complementarity}\footnote{} (PCOM) by interpreting the Bell-experiments as
statistical tests of this principle. (Our analysis also includes comparison of
classical vs genuine quantum entanglements.) After a brief presentation of PCOM
and endowing it with the information interpretation, we analyze its
computational counterpart. The main implication of PCOM is that by using the
quantum representation of probability, one need not compute the joint
probability distribution (jpd) for observables involved in the process of
computation. Jpd's calculation is exponentially time consuming. Consequently,
classical probabilistic algorithms involving calculation of jpd for $n$ random
variables can be over-performed by quantum algorithms (for big values of $n).$
Quantum algorithms are based on quantum probability calculus. It is crucial
that the latter modifies the classical formula of total probability (FTP).
Probability inference based on the quantum version of FTP leads to constructive
interference of probabilities increasing probabilities of some events. We also
stress the role the basic feature of the genuine quantum superposition
comparing with the classical wave superposition: generation of discrete events
in measurements on superposition states. Finally, the problem of superiority of
quantum computations is coupled with the quantum measurement problem and
linearity of dynamics of the quantum state update.
