0
$\begingroup$

As far as I know, quantum computers are able to solve only some of the NP-Problems in polynomial time, using the Grovers algorithm. I read that if one manages to create a reduction of Grovers algorithm on one of the NP-Complete algorithms, for example 3SAT, then it will be a huge milestone, since we could solve all other NP-Complete problems. I also read that current quantum computers lack error-correcting qubits to create a reduction of Grovers algorithm on 3SAT. What would be a sufficient amount of qubits to solve such problem and what amount do we currently have?

$\endgroup$
5
  • 1
    $\begingroup$ This has been asked before. But better to be asked quantum.se. Grover just produces quadratic speed, nothing more. Is there any specific reason that you have been asked here instead of quantumcomputing.se? $\endgroup$
    – kelalaka
    Mar 14, 2021 at 14:53
  • 3
    $\begingroup$ I’m voting to close this question because this question is realted to solving NP related problems with QC. Is not a specific problem related to cryptography. Therefore either to be asked in CS.SE, quantumcomputing.se or should concentrate a specific problem in Cryptography. $\endgroup$
    – kelalaka
    Mar 14, 2021 at 14:59
  • 1
    $\begingroup$ Is this your question on quantumcomputing Can quantum computers solve NP-complete problems?, asked two hours ago. Could you delete this copy? $\endgroup$
    – kelalaka
    Mar 14, 2021 at 17:42
  • $\begingroup$ short answer, though: no, not as far as we know. Grover changes nothing to that since it only provides a quadratic speedup. No NP complete problem is known to be solvable using a quantum computer, only specific problems outside of P, and inside NP (intersect) co-NP, such as factoring and discrete log, are known to be solved in polynomial time with a quantum computer. $\endgroup$ Mar 14, 2021 at 20:55

0

Your Answer

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