Квантовые компьютеры

Квантовый компьютер — одна из самых модных тем в науке последних лет и обязательная часть ожидаемого будущего.
Квантовые компьютеры

Задача рюкзака и идеальный маршрут

Представьте: у вас выдался выходной и вы можете переделать все дела, которые откладывали из-за работы. Вечером в пятницу вы пишете план: купить продукты, поплавать в бассейне, отдать пальто в химчистку, забрать с почты посылку, забежать в книжный, постричься и, наконец, пообедать в новом ресторане. Дел много, поэтому вы хотите спланировать день так, чтобы посетить все нужные места за минимальное время и не ходить лишнего. Казалось бы, ничего сложного, но если вы всерьез решите составить идеальный маршрут, у вас пропадут не только выходные, но еще и пара лет рабочего времени.

Описанная выше задача — оптимизировать перемещение по нескольким местам — в математике известна как задача коммивояжера, и ее невозможно решить за разумное время. Если мест назначения немного, скажем пять, вычислить кратчайшую траекторию несложно. Число вариантов для 15 точек составит уже 43 589 145 600. Если на оценку каждого тратить одну секунду, для перебора всех возможностей придется просидеть за столом 138 лет. Для 66 точек время решения превысит несколько миллиардов лет — при условии, что вы используете компьютер и он тратит на оценку одного варианта доли секунды.

Задача коммивояжера — не единственная, которую нельзя решить «в лоб» даже при помощи гигантских суперкомпьютеров. Подобные проблемы, не решаемые за разумное время, называются NP-полными, и они играют важную роль в обычной жизни. Именно благодаря их сложности вы, например, можете безопасно оплачивать покупки карточкой. К вашей карте помимо пина привязано очень большое число, которое делится на пин без остатка. Когда вы вводите пин, оплачивая покупку, банкомат делит большое число на то, что ввели вы, и проверяет ответ. Если злоумышленник захочет подобрать правильное число, которое при делении давало бы нужный результат, он закончит работу тогда, когда во Вселенной не останется ни вашей карточки, ни планеты Земля.

С еще одной NP-полной задачей вы сталкиваетесь, пытаясь выбрать, что ценного привезти из командировки, учитывая, что вес багажа ограничен. Если каждый раз вы не можете определиться, не расстраивайтесь: понять, как уложить в чемодан покупки на максимальную сумму и при этом не выйти за лимит по весу, невозможно за время человеческой жизни. Задача о рюкзаке — так эта проблема именуется в математике — определяет огромное количество решений в жизни: от выбора стратегии оптимального капиталовложения до схемы, как разместить товары на складе ограниченного объема.

Помочь в решении NP-полных задач не может ни одно классическое вычислительное устройство в мире. Классическое — то есть основанное на привычных алгоритмах и решающее в единицу времени только одну задачу (многозадачность современных операционных систем искусственная, а базовые процессы по-прежнему происходят по очереди). Все, на что они способны, — слегка уменьшить время решения. Но существуют машины, которые справляются с NP-полными задачами за считанные секунды. Это квантовые компьютеры, и впервые их существование предрек выдающийся физик Ричард Фейнман.

Комментарии
Комментарии