1
$\begingroup$

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

$\endgroup$

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.