Rather than empirical evidence, by what formal principles have we proved that quantum computing will be faster than traditional/classical computing?
Is there a formal proof that quantum computing is or will be faster than classical computing?
quantum computing
This is a question that is a little bit difficult to unpack if you are not familiar with computational complexity. Like most of the field of computational complexity, the main results are widely believed but conjectural.The complexity classes typically associated with efficient classical computation are $\mathsf{P}$ (for deterministic algorithms) and $\mathsf{BPP}$ (for randomized). The quantum counterpart of these classes is $\mathsf{BQP}$. All three classes are subsets of $\mathsf{PSPACE}$ (a very powerful class). However, our current methods of proof are not strong enough to definitively show that $\mathsf{P}$ is not the same thing as $\mathsf{PSPACE}$. Thus, we do not know how to formally separate $\mathsf{P}$ from $\mathsf{BQP}$ either — since $\mathsf{P \subseteq BQP \subseteq PSPACE}$, separating those two classes is harder than the already formidable task of separating $\mathsf{P}$ from $\mathsf{PSPACE}$. (If we could prove $\mathsf{P \ne BQP}$, we would immediately obtain a proof that $\mathsf{P \ne PSPACE}$, so proving $\mathsf{P \ne BQP}$ has to be at least as hard as the already-very-hard problem of proving $\mathsf{P \ne PSPACE}$).  For this reason, within the current state of the art, it is difficult to obtain a rigorous mathematical proof showing that quantum computing will be faster than classical computing.Thus, we usually rely on circumstantial evidence for complexity class separations. Our strongest and most famous evidence is Shor's algorithm that it allows us to factor in $\mathsf{BQP}$.  In contrast, we do not know of any algorithm that can factor in $\mathsf{BPP}$ — and most people believe one doesn't exist; that is part of the reason why we use RSA for encryption, for instance.  Roughly speaking, this implies that it is possible for a quantum computer to factor efficiently, but suggests that it may not be possible for a classical computer to factor efficiently.  For these reasons, Shor's result has suggested to many that $\mathsf{BQP}$ is strictly more powerful than $\mathsf{BPP}$ (and thus also more powerful than $\mathsf{P}$).I don't know of any serious arguments that $\mathsf{BQP = P}$, except from those people that believe in much bigger complexity class collapses (which are a minority of the community). The most serious arguments I have heard against quantum computing come from stances closer to the physics and argue that $\mathsf{BQP}$ does not correctly capture the nature of quantum computing. These arguments typically say that macroscopic coherent states are impossible to maintain and control (e.g., because there is some yet-unknown fundamental physical roadblock), and thus the operators that $\mathsf{BQP}$ relies on cannot be realized (even in principle) in our world.If we start to move to other models of computation, then a particularly easy model to work with is quantum query complexity (the classical version that corresponds to it is decision tree complexity). In this model, for total functions we can prove that (for some problems) quantum algorithms can achieve a quadratic speedup, although we can also show that for total functions we cannot do better than a power-6 speed up and believe that quadratic is the best possible. For partial functions, it is a totally different story, and we can prove that exponential speed ups are achievable. Again, these arguments rely on a belief that we have a decent understanding of quantum mechanics and there isn't some magical unknown theoretical barrier to stopping macroscopic quantum states from being controlled.