Comments 2
Во многих задачах классического компьютера: задача факторизации и др,
наивному алгоритму, зачастую надо перебрать в цикле все значения
регистра и проверить, удовлетворяет ли значение поставленным условиям
задачи. Каким то алгоритмам требуется на это линейное время, каким то
экспоненциальное,
При переборе всех значений регистра длиной n бит нужно перебрать 2^n значений.
Т. е. задача делает экспоненциальное количество шагов от длины регистра.
Может ли существовать классический алгоритм, который переберет в цикле все эти значения за линейное время?
Тут не очень удачно выразился. "требуется на это" имеется в виду не для перебора всех значений, а для решения задачи.
И далее перечисляю, что наивному алгоритму надо перебрать все значения для решения задачи. Другим алгоритмам может потребоваться для решения задачи линейное и т.д.
Если речь о так называемом наивном алгоритме, то да, надо перебрать все значения, чтобы решить задачу. Далее я имел в виду, что многие алгоритмы, не требуют перебора всех значений. Например, в задаче черного ящика в примере из последней части нам было достаточно перебрать только все степени двойки для ее решения, что делает алгоритм линейным
Квантовые компьютеры. С точки зрения традиционного программиста-математика. Часть 5