Квантовые вычисления - Стин Э.
Скачать (прямая ссылка):
направлении d (влево или вправо). Таким образом, внутренняя структура
машины может определяться конечным списком установленных правил вида (s,
G -> s', G', d). Особым внутренним состоянием является состояние
"останов"; перейдя в него машина прекращает работу. Исходная "программа"
с ленты преобразуется машиной в выходные данные, которые отображаются на
данной ленте
а число шагов, необходимых машине U для имитации каждого шага машины Т,
является полиномиальной (а не экспоненциальной) функцией от длины
(количества знаков) d[T}. Другими словами, если лента входных данных
машины U содержит как описание машины Т, так и входные значения х, то
машина U сможет вычислить без экспоненциального увеличения времени
обработки значения функции таким же образом, что и машина Т (какова бы ни
была сама машина Г).
В заключение можно показать, что другие модели вычислений (например,
сетевая модель) являются эквивалентными по вычислениям машине Тьюринга:
они позволят работать с теми же функциями, с той же производительностью
вычислений (см. следующий раздел). Таким образом, в концепции
универсальной машины показано, что определенная конечная степень
сложности устройства достаточна для обеспечения самой общей обработки
информации. Это положение является фундаментальным выводом в информатике.
Действительно, мощность ма-
40
Глава 3
шины Тьюринга и ей подобных машин настолько велика, что Church (1936) и
Turing (1936) определили "тезис Чёрча-Тьюринга", который гласит, что:
Любая функция, к которой подходит определение "вычислимая", может быть
обработана на универсальной машине Тьюринга.
Этот тезис не доказан. Однако он уже выдержал несколько попыток найти
пример, его опровергающий, что само по себе имеет большое значение.
Благодаря этому тезису современный компьютер общего назначения решает
самые разносторонние задачи - поскольку "вычислимые функции" включают в
себя такие задачи, как обработка слов, контроль на производстве и т. д.
Квантовый компьютер, о котором говорится в разделе 6, позволяет по-новому
взглянуть на этот основной тезис.
3.2. Сложность вычисления
Описав идеи универсального компьютера, можно классифицировать задачи,
связанные с вычислениями по их сложности, следующим образом: считается,
что данный алгоритм должен быть направлен на решение не частной задачи
(например, вычислить квадрат числа 237), а на решение класса задач
(например, при данном х вычислить его квадрат); количество информации,
передаваемой компьютеру для определения задачи, равно log ж, т. е. равно
количеству битов, необходимых для хранения значения х. Сложность
вычислений для какой-либо задачи определяется как число шагов s, которые
необходимы машине Тьюринга для завершения какого бы то ни было алгоритма
по решению данной задачи. Для сетевой модели сложность вычисления
определяется числом требуемых логических гейтов. Если существует
алгоритм, для которого число шагов s полиномиально зависит от объема
информации L (например, s ос. L3 + L), то считается, что соответствующая
этому алгоритму задача поддается обработке и ее относят к классу
сложности "Р". Если же число шагов s возрастает экспоненциально по мере
увеличения информации L (например, sa2i= ж), то задача считается сложной
и она будет относиться к другому классу сложности. Очень часто бывает
проще проверить решение, т. е. узнать, является ли оно верным, чем искать
его. Класс сложности "ЛГР" включает в себя
3.2. Сложность вычисления
41
множество задач, решение которых может быть проверено за полиномиальное
время. Очевидно, что Р € NP, однако существуют задачи, входящие в класс
NP, но не входящие в класс Р (т. е. NP / Р). Удивительным является то,
что последнее утверждение никогда не было доказано, поскольку сложно
исключить возможность существования алгоритмов, которые еще не найдены.
Однако важно отметить, что частичное совпадение этих классов не зависит
от модели вычисления, т. е. от тех или иных физических принципов, на
которых построен компьютер, поскольку машина Тьюринга способна
имитировать любой другой компьютер не с экспоненциальным, а с
полиномиальным замедлением.
Важным примером не поддающейся решению задачи является задача о
разложении числа на множители: задавшись сложным (т. е. не являющимся
простым) числом ж, необходимо определить один из его множителей. Если ж
является четным либо кратным какому-либо небольшому числу, то его
множитель найти легко. Важно отметить ситуацию, когда простые множители
числа ж являются большими числами. В этом случае простой метод решения
задачи не известен. Наиболее известен метод "решета числового поля"
(Menezes et. al. 1997). Он реализуется за число шагов s порядка s ~
exp(2L1/3(logL)2/3), где L = In ж. При использовании существующих на
сегодняшний день вычислительных сетей определение множителей числа,
состоящего из 130 десятичных знаков (Crandall, 1977), т.е. L ~ 300,
потребует число шагов s ~ 1018, эта задача решаема, но само решение
