It seems to be commonly believed that a quantum computer cannot efficiently solve NP-hard problems. What about problems that are challenging in the average-case, such as Planted Clique and Random 3-SAT?

  • $\begingroup$ No, there is no known efficient quantum algorithm for these problems. $\endgroup$ Jun 24, 2023 at 20:30


Your Answer

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