Karl--Georg Schlesinger
A Plausibility Argument for \#P$\neq $P from Physics
Preprint series: ESI preprints

MSC:

68Q15 Complexity classes, See also {03D15}

81P99 None of the above but in this section

Abstract: Quantum computers have been shown to be capable to deal with problems like
the factoring of numbers into primes in polynomial time, i.e. they might
differ from classical Turing machines with respect to computational
complexity, provided \textbf{\#P}$\neq $\textbf{P}. We reverse this
conclusion by giving a plausibility argument for \textbf{\#P}$\neq $\textbf{P}
by arguing that - as a consequence of the basic rules of quantum mechanics
- classical Turing machines should not be able to emulate quantum computers
even if a polynomial time delay for the classical Turing machine is allowed.
A generalization of the argument holds also for the case of replacing
\textbf{\#P} by \textbf{NP}
Keywords: quantum computing, factoring, complexity classes