Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?
I've written the following to talk about the connections between quantum computation and the (extended) Church-Turing thesis. Your question appears to have several other questions, which I don't address due to space (and time to write down this answer).


A statement that reads, &quot;There exists no &quot;reasonable&quot; computational model capable of recognizing languages that a Turing Machine cannot&quot;

This is essentially what the Church-Turing thesis states. It is not the extended Church-Turing thesis, which roughly takes the form:

All &quot;reasonable&quot; computational models can simulate each other with polynomial overhead

Of course, what &quot;reasonable&quot; means must itself be pinned down. For example, if you let $\mathsf{Halt}$ be an oracle to the halting problem, then the computational model $\mathsf{TM}^{\mathsf{Halt}}$ of Turing Machines equipped with halting oracles can compute strictly more than that than that of simply Turing machines.
So if $\mathsf{TM}^{\mathsf{Halt}}$ is viewed as &quot;reasonable&quot;, then the CT thesis is already false.
For this reason, &quot;reasonable&quot; is usually phrased as &quot;hypothetically realizable in the real world&quot;. As there is no proposed mechanism to create a universal $\mathsf{TM}^{\mathsf{Halt}}$ machine in the real world, this computational model would not be considered &quot;reasonable&quot;.
What does this mean for the extended CT thesis, and quantum computation? The complexity class $\mathsf{BQP}$ is the class of problems solvable (with bounded error) by a quantum computer efficiently. You should view it as a quantum analogue of $\mathsf{P}$ (more properly of $\mathsf{BPP}$, or &quot;two-sided error, randomized $\mathsf{P}$&quot;, but still).
If quantum computers (which can compute arbitrary problems in $\mathsf{BQP}$) are physically realizable, the extended Church-Turing thesis posits that they can only get a polynomial speedup over &quot;traditional&quot; models of computation. If this is the case, the extended Church-Turing thesis still holds, and quantum computing is in a certain sense &quot;more boring&quot;.
Preliminary evidence suggests that this is not the case though. There are a variety of problems which are known to have exponential speedups on quantum computers, famously factorization and the discrete logarithm problem via Shor's algorithm.
While these are large &quot;practical&quot; reasons for investigating quantum computation, they are actually not the theoretically most compelling reason.
Both factorization and discrete log are in $\mathsf{NP}\cap\mathsf{coNP}$, and therefore unlikely to be $\mathsf{NP}$-hard unless the polynomial hierarchy collapses.
This means that &quot;Shor's algorithm leads to an exponential speedup for factoring and discrete log&quot; isn't super interesting from a complexity theory point of view, as it's entirely consistent with current thoughts that both of these problems are actually in $\mathsf{P}$ (or $\mathsf{BPP}$).
There are problems which are more interesting to consider though.
In particular, the Boson sampling line of work posits a particular problem which is $\#\mathsf{P}$-hard, but is in $\mathsf{BQP}$.
This means that this particular problem is highly unlikely to be in $\mathsf{P}$, as this would collapse the polynomial hierarchy to the third level, which is thought to be unlikely by complexity theorists.
So the reason that people bring quantum computing up when discussing the (extended) Church-Turing thesis is that, if sufficiently &quot;physically realized&quot;, it provides exponential speedups on practically important problems (factoring and discrete logarithm), as well as an exponential speedup on a problem which is &quot;harder than $\mathsf{NP}$-complete&quot;. This would constitute a violation of the extended Church-Turing thesis.