4 ms·
Well I might add the quantum complexity-theory version of the Church–Turing thesis. I believe that quantum computation is a richer more powerful theory. In ess
by foxes 5y ago
Well I might add the quantum complexity-theory version of the Church–Turing thesis.
I believe that quantum computation is a richer more powerful theory. In essence BQP is a superset of BPP in your link.
I think this happens with all sorts of mathematical objects. Non commutative algebra is much richer than commutative algebra. There are also more interesting non commutative things than just deformations of classical objects. Its the classical commutative case that is the weird limit.
- chriswarbo 5y agoYeah, there are all sorts of layers we can add, especially regarding complexity (i.e. resource usage limits, rather than simple yes/no questions of decidability). It's interesting to consider P = NP as a physical law, although that's certainly more tenuous than the Church-Turing thesis, etc.