Question

I am currently learning Computing Theory at university, and we were on the topic of Turing-Decidability, Recognizability, etc. Showing that a problem is undecidable with Turing machines due to reductions got me thinking about all the Quantum Computer craze.

As such my question is as follows

Does there exist some language L that is not decidable by a Turing Machine, but is decidable by a quantum computer?

My hunch is no, as from what I understand about Quantum Computers, you can simulate them (albeit slower) using a Turing Machine. However my knowledge of Quantum Computing is limited to a 1.5 hour lecture from Microsoft on YouTube, and I would assume there was a lot more in the way of recent developments that I am not knowledgeable enough to understand

Was it helpful?

Solution

No. A state of $n$ qubits can be represented with a vector of size $2^n$, and quantum gates can be implemented as linear operations for those vectors. Therefore a quantum computer can be simulated with a Turing machine, although with an exponential overhead. It is also known that the class of problems solvable by a quantum computer in polynomial time, BQP, is contained in the class of problems solvable by a classical computer in polynomial space, PSPACE.

All this information is from the Wikipedia page https://en.wikipedia.org/wiki/Quantum_computing

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top