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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.