patternModerate
References on comparison between quantum computers and Turing machines
Viewed 0 times
comparisoncomputersbetweenmachinesandturingreferencesquantum
Problem
I was told that quantum computers are not computationally more powerful than Turing machines.
Could someone kindly help in giving some literature references explaining that fact?
Could someone kindly help in giving some literature references explaining that fact?
Solution
What is actually the case is that anything a quantum computer can compute, a Turing machine can also compute. (This is without commenting at all on how long it takes the Turing machine to compute the function compared to a quantum computer.)
This is actually not difficult to see, provided you understand quantum computation. For a quantum circuit over a typical gate set, for example, the outcome is governed by a probability distribution, which is determined by the coefficients of a unitary matrix. That unitary matrix is just a matrix product of those of the gates, and can be computed — if you're patient enough — by a classical computer. So for sheer computability (as opposed to efficiency), there is no advantage to using quantum computers.
The whole challenge arising from quantum mechanics is to determine whether such coefficients can be computed efficiently, which is a more demanding problem than whether they can be computed at all.
This is actually not difficult to see, provided you understand quantum computation. For a quantum circuit over a typical gate set, for example, the outcome is governed by a probability distribution, which is determined by the coefficients of a unitary matrix. That unitary matrix is just a matrix product of those of the gates, and can be computed — if you're patient enough — by a classical computer. So for sheer computability (as opposed to efficiency), there is no advantage to using quantum computers.
The whole challenge arising from quantum mechanics is to determine whether such coefficients can be computed efficiently, which is a more demanding problem than whether they can be computed at all.
Context
StackExchange Computer Science Q#6296, answer score: 10
Revisions (0)
No revisions yet.