2
$\begingroup$
  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.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Closely related question; you have wrong ideas what NP-hardness means. $\endgroup$ – Raphael♦ Jan 31 '17 at 18:11
  • $\begingroup$ Yea I did, but now I think I understood it after some more research. $\endgroup$ – Zonko Jan 31 '17 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 Jan 31 '17 at 19:50
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

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