HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

References on comparison between quantum computers and Turing machines

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#6296, answer score: 10

Revisions (0)

No revisions yet.