1. Is there any NP-Problem that can't be (maybe even proven) solved by quantum computers. I'm not talking about quantum NP-Problems (if that's even a thing), but about normal NP.
  2. If that NP Problem exists could you also use it for cryptography, since I don't want to buy a quantum computer just to be secure.

EDIT: I'm not talking about NP-complete, because that would have no use (I think) in cryptography and also not about symmetric key encryption.

  • $\begingroup$ Closely related question; you have wrong ideas what NP-hardness means. $\endgroup$
    – Raphael
    Commented Jan 31, 2017 at 18:11
  • $\begingroup$ Yea I did, but now I think I understood it after some more research. $\endgroup$
    – Zonko
    Commented Jan 31, 2017 at 18:18
  • 1
    $\begingroup$ What is NP problem? If it NP-complete then there is no such problem known because relation between BQP and NP is currently unknown. If it is NP-hard, then recall BQP is in PSPACE so just take any problem outside of it. If it is a problem in NP and not necessary complete, then this is even stronger then unsolvability of NP-complete problem. If I remember correctly, even $BQP \in NP$ is unknown. $\endgroup$
    – Eugene
    Commented Jan 31, 2017 at 19:50

1 Answer 1


Nobody really knows whether quantum computers can solve all NP complete problems in polynomial time or not. There is strong evidence that they cannot: Strengths and Weaknesses of Quantum Computing, but no definite proof.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.