Главная » Просмотр файлов » М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация

М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 47

Файл №1156771 М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация) 47 страницаМ. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771) страница 472019-09-18СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 47)

Например, многоленточные машины Тьюринга могут решать многие задачи существенно быстрее, чем одноленточные. Эта трудность разрешается довольно грубым способом. Предположим, что на вход подается и битов (например, нам может быть нужно узнать, является ли простым данное и-битовое число). Главное различие, кзторое проводится в теории сложности, — это различие между задачами, которые можно решить с использованием ресурсов, объем которых ограничен сверху многвчленвм отп и, и задачами, для которых необходимый объем ре- 186 Глава 3. Введение в информатику сурсов растет быстрее, чем любой многочлен от и.

В последнем случае обычно говорят, что задача требует экспоненциальнмх ресурсов (злоупотребляя словом «экспоненциальный»: существуют функции, например имг", которые растут быстрее любого полинома и тем самым являются «экспоненциэльными» в нашем смысле, но при этом растут медленнее любой настоящей экспоненты). Задача считается легкоа, простой или решаемой, если для ее решения существует полииомиальный алгоритм, и гпрдоной, сложной или нерешаемой если наилучший возможный алгоритм требует экспоненциального объема ресурсов.

В качестве простого примера рассмотрим два числа с двоичными записями х1... х, и у1... у~, и предположим, что нужно найти их сумму. Общий объем входных данных равен и = п»1 + гпг. Легко видеть, что числа можно сложить, используя 9(т) элементарных операций; этот алгоритм использует полиномиальное (а именно, линейное) число операций. Напротив, считается (хотя это так и не доказано!), что задача разложения числа на простые множители является сложной и, что не существует алгоритма, с помощью которого произвольное п-битовое число можно разложить на простые множители с помощью 0(р(и)) операций, где р — некоторый фиксированный многочлен от и.

Ниже мы приведем много других примеров задач, считающихся сложными в этом смысле. Разделение задач на полиномиальные и экспоненциальные является довольно грубой классификацией. На практике алгоритм, решающий задачу за 2"7шоо операций, является, возможно, более полезным, чем тот, который использует и1ооо операций. Только при очень большом (п ю 10 ) объеме входных данных этот «эффективный» полиномиальный алгоритм будет предпочтительнее «неэффективного» экспоненциального и для многих целей разумнее будет пользоваться именно «неэффективным» алгоритмом.

Однако существует много причин, по которым имеет смысл основывать теорию сложности вычислений именно на разделении алгоритмов на полиномиапьные и экспоненциэльные. Во-первых, исторически за малым числом исключений сложилось так, что полиномиальные алгоритмы работали существенно быстрее экспоненциальных. Можно по,пумать, что причина этого в недостатке нашего воображения: разработать алгоритм, в котором число операций равно и, и~ или какому-нибудь еще многочлену маленькой степени, часто гораздо проще, чем алгоритм, требующий п'~~ операций, хотя и такие примеры существуют. Так что склонность человека к построению относительно простых алгоритмов привела к тому, что на практике полиномиальные алгоритмы работают достаточно эффективно.

Вторая и более серьезная причина того, что имеет смысл настаивать на разделении алгоритмов иа полиномиальные и экспоненциальные, связана с сильной формой тезиса Черча-Тьюринга. В рэзд. 1.1 мы уже обсуждали, что в 60-70-х гг. было замечено, что вероятностная машина Тьюринга является сильнейшей из «разумных» вычислительных моделей. Точнее говоря, различные исследователи независимо пришли к выводу, гго если можно вычислить функцию с помощью Й операций на некоторой модели, не являющейся вероятностной машиной Тьюринга, то на вероятностной машине Тьюринга ту же 3.2.

Анализ вычислительных задач 187 самую функцию можно вычислить не более чем за р(Й) операций, где р( )— некоторый многочлен. Это утверждение известно как усиленный тезис Черчуьюринга: Тезис Черча — Тьюринга (усиленная форма). Любая вмчислитлвльная модель молсет быть смодглирована на вероятностной маигинв Тьюринга с не более чем палинамиальнмм увеличением числа оаераций. Усиленный тезис Черча-Тьюринга имеет большое значение для теории сложности вычислений в том отношении, что из него вытекает, что все внимание можно сосредоточить на вероятностной машине Тьюринга.

Если задача не допускает полиномиального решения на вероятностной машине Тьюринга, то из этого тезиса следует, что нн на каком вычислительном устройстве она не имеет эффективного решения. Теория сложности вычислений принимает элегантный ввд и перестает зависеть от выбора модели, если только отождествить эффективность алгоритма с его полиномиэльностью, и именно эта элегантность подтолкнула исследователей на отождествление понятий «разрешимость с полвномиальными ресурсами» и «эффективная разрешимость». Конечно, одна из основных причин, по которым квантовые компьютеры представляют интерес, это то, что они подвергают усиленный тезис Черча-Тьюринга сомнению, так кэк позволяют эффективно решить задачи, которые считаются сложными для всех классических компъютеров, включая вероятностные машины Тьюринга! Тем не менее полезно понять и оценить ту роль, которую усиленный тезис Черча-Тьюринга сыграл в процессе построения не зависящей от модели теории сложности вычислений, Отметим в заключение, что специалисты по информатике интересуются не только разделением задач на полиномнальные и экспоненциальные.

Это лишь первый и самый грубый способ оценки трудности вычислительных задач. Тем не менее такое разделение является исключительно важным; оно иллюстрирует многие более общие вопросы, связанные с проблемой потребления ресурсов при вычислениях. В большей части этой книги при оценке эффективности алгоритма мы будем в первую очередь руководствоваться именно отличием полиномиальности от экспоненциэльности. Теперь, когда мы обьяснили, чем хорошо разделение алгоритмов на полиномигльные и экспоненциальные, еле,зует признаться, что у теории сложности вычислений имеется один крупный недостаток: по-видимому, очень трудно доказать, что существуют интересные классы задач, для котОрых нет полиномивльных алгоритмов. Совсем легко дать неконструктивное доказательство того факта, что для большинства задач требуются экспоненциэльные ресурсы (см.

упр. 3.16), и более того, существуют гипотезы, согласно которым для многих задач требуются экспоненциальные ресурсы, но строгих доказательств этих гипотез нет и представляется, что найти эти доказательства очень трудно, по крайней мере, при современном состоянии предмета. Этот недостаток теории сложности вычислений имеет важные последствия и для квантовых вычисленнй, поскольку эффективность квантовых компъютеров сравнивается с эффек- 188 Глава 3.

Введение в информатику тивностью классических вычислительных моделей. До тех пор, пока основные проблемы классической теории сложности вычислений не будут решены, об эффективности квантовых компъютеров нельзя сказать ничего определенного; нельзя даже сказать, действительно ли квантовый компьютер эффективнее классического компьютера. Упражнение 3.16 (экспоненциально вычислимые функции существуют). Покажите, что существуют булевы функции с и аргументами, для вычисления которых требуется не менее 2" / 1о8 и логических элементов.

3.2.3 Задачи разрешения и классы сложности Р и ХР Многие вычислительные задачи лучше всего формулируются как задачи разрешения, т. е. задачи, дающие ответ в виде «да» или «нетм Пример: является данное число гп простым или нет? (это задача определения простатам). Основными для теории сложности вычислений являются именно задачи разрешения по двум причинам: во-первых, при этом теория принимает наиболее простой и элегантный вид, но при этом остается возможность ее естественного обобщения на более сложные случаи и, во-вторых, исторически теория сложности вычислений возникла прежде всего из анализа задач разрешения.

Хотя большинство задач разрешения легко сформулировать на простом и знакомом языке, обсуждение общих задач разрешения сильно облегчается, если воспользоваться понятием формального лзмка. Язытм Ь в алфавите Е называется подмножество множества Е', состоящего из всех конечных строк символов алфавита. Если, например,,Е = (О, Ц, то множество двоичных записей четных чисел Ь = (О, 10, 100, 110,...) является языком в алфавите Е. Задачи разрешения можно очевидным образом переформулировать как задачи о языках. Например, задача определения простоты может быть сформулирована с помощью двоичною алфавита Е = (О, Ц. Строки из Е' можно интерпретировать как целые неотрицательные числа (например, 0010 — это число 2).

Язык А определим как состоящий из двоичных строк, соответствующих простым числам. Чтобы решить задачу определения простоты, нам нужна машина Тьюринга, которая, при подаче числа и на вход выдает какой-то эквивалент ответа «да», если число простое, и выдает «нет», если число составное. Для того, чтобы уточнить это определение, нам будет удобно слегка модифицировать наше прежнее определение машины Тьюринга (подразд. 3.1.1), заменив заключительное состояние оь на пару состояний ву и оп, представляющих ответы «да» и «нет» соответственно.

Характеристики

Тип файла
DJVU-файл
Размер
11,78 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6430
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее