# 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

You are right, photonic systems are described by an infinite (separable) Hilbert space---the bosonic Fock space---and their formalism makes extensive use of infinite values, both countable and uncountable. The quantum computing paradigm based on this Hilbert space is called continuous-variable (CV) quantum computing, and a lot of different protocols and ...

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, a classical computer can simulate a quantum computer in terms of computational efficiency but it would be limited up to 23 qubits till 2005-2006 using IBM Bluegene supercomputer cluster at Forschungszentrum Juelich in Germany. However, the latest update as per 2017 is a world record of 46 qubits. World Record: Quantum Computer with 46 Qubits simulated ...

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