Посмотри теорему P=NP. Там идёт речь про то, сопоставима ли сложность нахождения ответа и сложность его проверки для всех вычислений. Несмотря на то, что доказать ее пока не удалось, вся криптография в мире основана на предположении, что это не так, и сложность проверки гораздо меньше сложности нахождения ответа.
Простой пример с шифрованием. У тебя есть неебически огромное число, которое равно произведению двух чуть менее огромных простых чисел. Чтобы расшифровать сообщение без ключа, тебе надо найти делители, на обычном ПК это занимает охулионы лет. Квантовые ПК за счёт своей конструкции справляются на порядки быстрее. При этом для проверки тебе нужно всего лишь перемножить два числа и сравнить с исходным, что делается легко и быстро. Вот и ответ.