Сложность вычислений

Loading...

Из курса от партнера Saint Petersburg State University

Квантовые вычисления (Quantum computing)

20 оценки

Saint Petersburg State University

Квантовые вычисления (Quantum computing)

20 оценки

О квантовых вычислениях много пишут и говорят, особенно в последнее время. Причины такого интереса вполне очевидны - потребность в новом поколении вычислительных устройств назрела уже давно, и квантовый компьютер - первый кандидат на то, чтобы стать этим новым поколением. Для работы с новыми, только возникающими технологиями требуются специалисты, разбирающиеся в основах этих технологий - инженеры, физики, математики, алгоритмисты... Это - те люди, которые, возможно, станут у истоков новой эры и смогут поучаствовать в осуществлении очередного грандиозного шага в развитии человечества. Затронуть все аспекты темы квантовых вычислений в рамках одного MOOC не представляется возможным, поэтому данный курс охватывает только одну их область - анализ и проектирование квантовых алгоритмов. Прослушав курс, вы: 1. Разберетесь с моделью квантовых вычислений и поймете, что такое квантовый компьютер с точки зрения алгоритмиста и математика. 2. Познакомитесь с простыми (и не очень простыми) квантовыми алгоритмами и получите начальные навыки их проектирования. 3. Просто получите удовольствие, всегда сопровождающее познание чего-то нового. Команда курса желает вам успехов в освоении материала. Мы будем искренне рады, если знания, полученные вами здесь, помогут вам в достижении новых теоретических и практических результатов.

Из урока

Введение

Почему будущее вычислений за квантовыми компьютерами? Какое отношение физика (тем более квантовая) имеет к информатике?

Информация и вычисления8:49

Характеристики вычислительных систем5:34

Вычислимость и алгоритм7:56

Сложность вычислений6:34

Познакомьтесь с преподавателями

Сысоев Сергей Сергеевич
кандидат физико-математических наук
Кафедра системного программирования

[МУЗЫКА]

[МУЗЫКА] Однако

и с вычислительными функциями все не так хорошо и гладко.

Оказалось, что разные функции имеют разную вычислительную сложность.

При этом парадоксально, вычислительная сложность может быть определена не для

функции, а для алгоритма.

Мы могли бы попробовать определить вычислительную сложность функции как

сложность наилучшего алгоритма, реализующего эту функцию.

Но вы помните, что множество алгоритмов у нас бесконечно,

и здесь у нас могут быть две проблемы.

Первая — наилучшего алгоритма может просто не существовать.

Например, может существовать бесконечная последовательность алгоритмов каждый

из которых лучше, чем предыдущий.

Или наилучший алгоритм может быть нам неизвестен,

а проблема его поиска — неразрешима.

В этом случае мы можем определить сложность функции например как

сложность наилучшего алгоритма, реализующего эту функцию.

Мы не будем определять формально сложность вычисления класса сложности,

поскольку это тема отдельного курса.

Неформально сложность алгоритма это характер роста какого-то ресурса

(например, времени), необходимого для его выполнения в зависимости от размера задач.

Например, для сложения чисел в столбик нам нужно столько элементарных

табличных операций сложения сколько цифр в складываемых числах.

Например, если цифр n, нам требуется, учитывая переносы, 2n сложений.

Что соответствует сложности O(n).

При сортировке массива из n элементов методом «пузырька» нам

требуется O большое от n квадрат операций сравнения.

Вообще говоря, сортировка массива — очень хорошая функция.

Для нее нам известен теоретический предел сложности.

И алгоритмы, реализующие этот предел.

Таким образом, сортировка массива — это задача, у которой есть сложность.

Задачи такого рода, для которых сложность алгоритма оценивается

каким-то полиномом от размера входных данных, считаются «хорошими» и

составляют класс P — бесконечный класс задач,

для которых существуют полиномиальные алгоритмы.

Есть еще класс «условно хороших» задач,

для которых полиномиальные алгоритмы существуют для проверки решения.

К таким задачам относятся, например, поиск Гамильтонова пути в графе,

разложение чисел на множители и, например, сложение в столбик.

Если у нас есть полиномиальный алгоритм для решения задачи,

то мы его можем использовать как процедуру проверки решения.

Таким образом получается что класс P входит в класс NP (задач,

для которых существуют полиномиальные алгоритмы проверки решения).

Обратное включение — один из самых сложных

нерешенных вопросов современной теории вычислений.

В настоящий момент существуют задачи из класса P,

для которых неизвестен полиномиальный алгоритм.

Важные задачи.

Например, разложение числа на множители.

Предположим N состоит у нас из двух больших простых множителей.

Если числа p и q нам даны,

то мы можем легко полиномиально их перемножить и получить число N.

Однако если числа p и q неизвестны,

то в настоящий момент не существует эффективной процедуры их получения.

Представим, что вы придумали,

нашли два каких-то очень больших простых числа, тысяч по десять знаков.

Это можно сделать.

Перемножили их, получили число N.

Опубликовали его, а дальше забыли или потеряли числа p и q.

Теперь даже видя N, даже за время жизни

Вселенной существующими алгоритмами невозможно найти p и q.

Даже если искать будет компьютер размером со всю Вселенную.

Если гипотеза «P не равно NP» верна,

то класс NP на картинке будет выглядеть как-то так.

[БЕЗ_ЗВУКА] Задача

разложения на множители будет, вероятно, где-то здесь.

В 1994 году американский

математик Питер Шор предложил полиномиальный

алгоритм разложения чисел на множители для квантового компьютера.

Таким образом невыполнимая для классических вычислений задача

стала легко выполнима для квантовых вычислений.

Нарисуем на нашей картинке класс NP «трудных» задач.

[БЕЗ_ЗВУКА] Это такие задачи,

к которым полиномиально сводятся любая задача из NP.

Иными словами, если у нас есть волшебный ящик,

умеющий решать какую-то задачу из этого класса, из NP hard, то с помощью этого

волшебного ящика мы сможем эффективно решать любую задачу из NP.

В 1972 году Стивен Кук показал,

что пересечение класса NP hard NP не пусто.

Это пересечение называется «задача NP полная»,

или NP complete, или кратко NPC.

Для всех задач из класса NP в настоящий момент квантовые вычисления

дают лучший результат чем известные классические алгоритмы.

К сожалению этого нельзя сказать про класс NP трудных задач.

На последней неделе курса мы рассмотрим одну задачу из этого класса для которой мы

докажем, что квантовые вычисления дают не лучший результат, чем классические.

[БЕЗ_ЗВУКА]

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play