# Tag Info

3

In the framing of the question (which I believe to be asked in good faith), there seems to be at least two objections. Sampling from a set of strings is not clearly a function, and Sampling is a physical process, outside of computation. Initially, with regard to the first objection, I assert that sampling is a function, as a search problem. For example, ...

3

The Church-Turing thesis is not in and of itself a rigorous concept, but rather a judgment on rigorous concepts of computability. As such, it's negotiable. The language in Rosser's 1939 expository paper about provability and computability is biased towards deterministic algorithms. There is an important simplifying theorem here: If you only care about ...

2

I will address the first two parts based on what I understood so far. The extended Church–Turing thesis or (classical) complexity-theoretic Church–Turing thesis states that "A probabilistic Turing machine can efficiently simulate any realistic model of computation.", whereas the quantum extended Church–Turing thesis or quantum complexity-theoretic Church–...

2

Yes, it can because quantum computing is a generalization of classical computing. So the procedure you ask for exists. We can take a universal classical logic gate such as NOR gate, generalize to a reversible quantum version of that NOR gate. Thus a procedure can be as follows: Design classical circuit Rewrite classical circuit using only the chosen ...

2

Taking the questions head on. I'm not sure that original references are very much the point, although there are some. It's not a hard question. The statement is that realistic polynomial time equals what a quantum computer (if you want to be rigorous, say a QTM) can do in polynomial time. The question has been answered many times in QCSE that a quantum ...

1

Regarding the "quantum (non-extended) Church-Turing Thesis," I think this asserts that there is no physical process, like a quasar or some other astronomical woo, that we know could produce a steady supply of qubits all in the same state $\alpha|0\rangle+\beta|1\rangle$, with the property that $\beta^2=\Omega_C$, that is, Chaitin's halting probability. We ...

Only top voted, non community-wiki answers of a minimum length are eligible