Is there a unit of measure for computational complexity; through quantum computers?

51 Views Asked by At

I'm concerned with trying to determine whether the same computational processes on a Turing computable algorithm can be ascertained for a quantum computer in some form of actual 'metric' for how many resources are utilized by the computer?

Is this possible to translate the same complexity to the lowest common denominator of a traditional computer, but instead, for a quantum computer and then be able to determine a universal metric for computability?

1

There are 1 best solutions below

1
On

The short answer: gate number. What I mean by that is that is the number of physical gates used in the quantum algorithm is what is counted for complexity classes. Source: this is what I study and that is what we count for complexity purposes.

If you want a little more information, you could try googling BQP. This is the set of problems which can be solved on a quantum computer in polynomial time (I'm skipping some minor details on what solved means here). An outstanding problem in my field is whether BQP=P. If so, then quantum computers are actually not any better than classical computers (at least as far as 'fast' vs 'slow algorithms are concerned). However, this is probably not true as integer factorization is in BQP and most people believe it is not in P.