44

Yes, a quantum computer could be simulated by a Turing machine, though this shouldn't be taken to imply that real-world quantum computers couldn't enjoy quantum advantage, i.e. a significant implementation advantage over real-world classical computers. As a rule-of-thumb, if a human could manually describe or imagine how something ought to operate, that ...


7

If we have a QTM with state set $Q$ and a tape alphabet $\Sigma = \{0,1\}$, we cannot say that the qubit being scanned by the tape head "holds" a vector $a|0\rangle + b|1\rangle$ or that the (internal) state is a vector with basis states corresponding to $Q$. The qubits on the tape can be correlated with one another and with the internal state, as well as ...


7

To simulate the collapse of the wave function you'd need a source of randomness. So you'd need a probabilistic Turing machine.


6

Sort of, quite possibly, if by degrees This is a speculative, but plausible, answer First of all, how do qubits interact and states evolve with time? The description of how individual qubits evolve (i.e. a single qubit gate operation) is given by some Hamiltonian1. Multiple, non-interacting qubits (that are exactly the same) therefore evolve using ...


4

We don't yet know if quantum computers are actually better than classical computers, as @heather mentions here. As for now there are just some theoretical algorithms which we know of, specifically for quantum-computers, which have much better time complexities than equivalent classical algorithms. For example - prime factorization and discrete logarithms. ...


4

To complete what others have said: as far as we know a (classical) Turing machine cannot truly simulate quantum correlations. This is explicitly claimed in section Properties of the universal quantum computer by the seminal paper by David Deutsch Quantum theory, the Church-Turing principle and the universal quantum computer (Proceedings of the Royal Society ...


4

The quantum Turing machine can move into a superposition of moving left and right. This is different from the classical Turing machine which can only move either left or right.


4

There are two notions of Zeno topics related to quantum computation. The first, which is controversial is usually called hypercomputation, which deals with the possibility of surpassing the limitations of the Church-Turing thesis by means of quantum computation. It is related to the Zeno effect through the fact that if it could be realized, it may solve the ...


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

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