It is my understanding that quantum computers have gained interest, because some interesting problems are suspected to be in the BQP-class, but not in the P-class (integer factorization, ...). Quantum computers would then be able to solve these problems efficiently, while classical computers are not.However, I'm wondering if quantum computers will also be able to out-scale classical computers at P-problems. Part of my reasoning leading to this question is the idea that quantum computers might be able to solve classical P-problems with a relatively small number of qubits. Exponential scaling of the number of qubits over time, might lead to quantum suppremacy, not only for BQP, but also for P-problems.Are quantum computers only useful to tackle specific problems, i.e. BQP-problems that are (potentially) not in the P-class? Or is it reasonable to assume that quantum computers might gain superiority for all types of problems?
Will quantum computers out-scale classical computers at P-problems?
algorithm analysis;quantum computing