Решение «задачи коммивояжера» с помощью квантовых вычислений

Классическая алгоритмическая задача в области информатики, известная как задача коммивояжера (TSP), является ярким примером задачи комбинаторной оптимизации.

Что такое ТСП? Эта классическая математическая задача предполагает поиск кратчайшего маршрута для посещения N городов ровно один раз, прежде чем вернуться в исходный город. Однако по мере увеличения количества городов растут и возможные маршруты, и время вычислений для поиска оптимального решения. Хотя эту проблему можно решить с помощью методов аппроксимации, квантовые компьютеры могли бы предложить гораздо лучшие решения и гораздо быстрее. 

Именно об этом говорит физик-теоретик Команда профессора доктора Йенса Эйсерта продемонстрировала: что такие проблемы можно решить лучше и быстрее с помощью квантовых компьютеров.

Квантовые вычисления используют аппаратное обеспечение и алгоритмы, которые используют квантовую механику для решения сложных задач, недоступных традиционным, включая суперкомпьютеры. Несмотря на свою мощь, суперкомпьютеры — массивные классические компьютеры с тысячами ядер ЦП и ГП — ограничены из-за того, что они полагаются на транзисторные технологии 20-го века при решении задач высокой степени сложности. 

Именно здесь на помощь приходит квантовая физика. В отличие от классических компьютеров, которые кодируют информацию в двоичных битах (0 и 1), квантовые компьютеры используют квантовые биты или кубиты для запуска многомерных квантовых алгоритмов. 

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

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

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

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

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

По словам Эйсерта, который возглавляет совместную исследовательскую группу в Helmholtz-Zentrum Berlin (HZB), исследовательском центре по исследованию энергетических материалов, и государственном исследовательском университете Freie Universität Berlin:

«Об этом ходит много мифов, а иногда и некоторая болтовня и шумиха. Однако мы подошли к этому вопросу строго, используя математические методы, и добились солидных результатов по этому вопросу. Прежде всего, мы выяснили, в каком смысле вообще могут быть какие-то преимущества». 

Критическая задача коммивояжера

Задача оптимизации TSP имеет большое экономическое значение в сфере логистики и цепочек поставок. Это относится к более широкой категории задач комбинаторной оптимизации, которая также включает планирование работы, распределение ресурсов, оптимизацию портфеля и даже сворачивание белков, которые имеют решающее значение для различных секторов.

Учитывая социальную и экономическую значимость этих проблем, они стали предметом интенсивных исследований. Таким образом, поиск ответа на такие проблемы, как наиболее эффективная цепочка поставок и самый дешевый маршрут доставки, оказывает положительное влияние на нашу повседневную жизнь.

Однако оптимизация маршрутов доставки для нескольких пунктов назначения с учетом различных ограничений, таких как пробки на дорогах, растущие эксплуатационные расходы, внезапные изменения маршрутов, деловые встречи в последнюю минуту и ​​запросы клиентов, делает решение TSP еще более сложным. Несмотря на эти проблемы, решение TSP имеет решающее значение для эффективной доставки товаров, что обеспечивает жизнеспособную бизнес-модель. 

Решение этой проблемы дает множество преимуществ, включая сокращение пройденного расстояния и часов, а также экономию топлива. Минимизация пройденного расстояния может помочь значительно сократить выбросы углекислого газа, что приведет к улучшению качества воздуха, замедлению изменения климата и экономическому росту. Более того, решение TSP может помочь в своевременной доставке товаров и своевременных встречах с клиентами, что повышает качество обслуживания клиентов и бизнес-обслуживание на местах.

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

Для решения проблемы TSP можно использовать несколько методов. Одним из таких методов является подход «грубой силы», который вычисляет все возможные перестановки для поиска кратчайшего маршрута. В методе ветвей и границ задача разбивается на несколько серий подзадач, причем решение каждого этапа влияет на решение, найденное на последующих этапах.

В динамическом программировании основное внимание уделяется предотвращению избыточных вычислений. Между тем, «Ближайший сосед» — это алгоритм аппроксимации, в котором вы начинаете с начального местоположения, а затем останавливаетесь на ближайшем. Как только все города будут пройдены, вы возвращаетесь в исходную точку. Хотя этот метод практичен и относительно быстр, он не всегда обеспечивает эффективный маршрут.

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

Квантовые компьютеры также исследуются для решения этой проблемы; в конце концов, они обеспечивают значительное ускорение вычислений по сравнению с классическими компьютерами. Уже давно высказывалось предположение, что эти компьютеры действительно могут помочь улучшить приближение к этим проблемам. 

Использование методов квантовых вычислений для решения TSP

Хотя квантовые вычисления вызывают огромный интерес и дают многообещающие результаты для решения определенных задач, масштабы этого квантового преимущества остаются в значительной степени неисследованными. 

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

В последнем исследовании, проведенном Эйсертом и его коллегой Жаном-Пьером Зейфертом, использовались только аналитические методы, чтобы оценить, как квантовый компьютер с кубитами может решить проблему TSP. 

«Мы просто предполагаем, независимо от физической реализации, что кубитов достаточно, и смотрим на возможности выполнения с ними вычислительных операций», что обнаруживает сходство с распространенной проблемой в криптографии, то есть шифрованием данных, объяснил Винсент Улитч. , доктор философии. студент Берлинского технического университета. 

Затем команда использовала квантовый алгоритм Шора, чтобы найти простые множители целого числа и решить подкласс этих оптимизационных задач. При этом время вычислений больше не будет резко увеличиваться по мере увеличения числа городов. Оно будет увеличиваться только полиномиально, т. е. с увеличением Nx, где x — константа. Таким образом, полученное решение также качественно намного лучше, чем то, которое получается из приближенного решения с использованием традиционного алгоритма.

Используя криптографические концепции и теорию вычислительного обучения, исследование дает «полностью конструктивное доказательство того, что квантовые компьютеры обладают суперполиномиальным преимуществом перед классическими компьютерами при решении задач комбинаторной оптимизации». 

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

Исследование финансировалось Исследовательским отделом Эйнштейна, Берлинским центром математических исследований (кластер передового опыта MATH+), BMBF (Hybrid), BMWK (EniQmA), Мюнхенской квантовой долиной и DFG. Федеральное министерство образования и исследований Германии также оказало финансовую поддержку.

Исследование потенциала квантовых вычислений 

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

В декабре 2022 года статье предложил квантовый алгоритм для TSP, основанный на адаптивном поиске Гровера (GAS). В рамках GAS существует по крайней мере две фундаментальные трудности: решения могут быть неосуществимыми, а количество кубитов современных квантовых компьютеров очень ограничено и не может соответствовать минимальным требованиям, что ограничивает применение квантовых алгоритмов для задач комбинаторной оптимизации. 

Таким образом, в статье усовершенствован оракул обнаружения гамильтонового цикла (HCD), который может автоматически удалять непрактичные решения во время выполнения алгоритма. Они также разработали стратегию «якорного регистра» для экономии использования кубитов, полностью учитывая требования обратимости квантовых вычислений и преодолевая трудности, связанные с невозможностью просто перезаписать или освободить использованные кубиты. Это позволило исследованию потребовался всего 31 кубит, а вероятность успеха решения составила 86.71%.

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

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

Однако в 2021 году проведенное исследование Компания Johnson & Johnson, финансируемая Supply Chain Digital & Data Science, обнаружила, что квантовый отжиг может справиться только с проблемой размером 8 или меньше узлов, а его производительность не на должном уровне как с точки зрения времени, так и точности по сравнению с классическим решателем.

Использование квантовых вычислений для решения проблемы TSP продолжается уже некоторое время. Более двух десятилетий назад, в 2001 году, началось исследование поиск квантовый алгоритм для решения проблемы.

В своей статье Бакли Хоппер из Университета Алабамы рассмотрел алгоритмы квантового компьютера Гровера и Шора. Он отметил, что алгоритм Гровера обеспечивает улучшение только на квадратный корень, а это означает, что он не может решить классически неразрешимую задачу на квантовом компьютере. Что касается алгоритма Шора, Хоппер заметил, что, хотя он может преобразовать предположительно неразрешимую задачу с простыми факторами в решаемую на квантовой машине, он подходит только для очень специфического типа задач. 

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

Через несколько лет после этого Институт инженеров по электротехнике и электронике (IEEE) представлены новый алгоритм решения проблемы, вдохновленный как генетическими алгоритмами, так и квантовыми вычислениями. IEEE обнаружил, что результаты применения предложенного алгоритма в некоторых случаях задачи коммивояжера значительно лучше, чем результаты, полученные стандартными генетическими алгоритмами.

Нажмите здесь, чтобы узнать о текущем состоянии квантовых вычислений.

Компании, работающие с квантовыми вычислениями 

Теперь давайте взглянем на пару имен, которые занимаются исследованиями и разработками в области квантовых вычислений:

# 1. IBM

Корпорация International Business Machines работает в широком спектре секторов, включая искусственный интеллект, облачные услуги, ИТ, клиентское и коммерческое финансирование. Технический гигант также участвует в квантовых вычислениях через свою IBM Quantum Platform, которая предоставляет общедоступный и премиальный доступ к его облачным сервисам квантовых вычислений. В их число входит набор прототипов квантовых процессоров IBM, учебные пособия по квантовым вычислениям и интерактивный учебник.

Совсем недавно ученые IBM заявил что они являются еще одним шагом ближе к преодолению препятствия, которое раскрывает революционный потенциал квантовых компьютеров. Для этого они представили новый квантовый код исправления ошибок, который, по их словам, примерно в десять раз эффективнее предыдущих методов. 

В конце прошлого года компания также выпустила квантовый компьютер под названием «Кондор» с 1,121 сверхпроводящим кубитом, расположенным в виде сот. IBM также представила IBM Quantum System Two, свой первый модульный квантовый компьютер и квантовоцентрическую суперкомпьютерную архитектуру, которая является масштабируемой и, следовательно, может быть модернизирована с помощью чипов, которые будут выпущены в ближайшие пять лет.

При рыночной капитализации в $175 млрд акции IBM торгуются на уровне $190.86, что на 16.66% выше с начала года (с начала года). IBM сообщила о выручке (TTM) в размере $61.86 млрд при показателях EPS (TTM) 8.03, P/E (TTM) 23.76 и ROE (TTM) 33.36%. Компания выплачивает дивидендную доходность в размере 3.48%.

# 2. D-Wave Systems

Эта компания, занимающаяся квантовыми вычислениями, разрабатывает и поставляет сопутствующие системы, программное обеспечение и услуги. В число продуктов компании входят The Leap и The Advantage, а также она предоставляет квантовые приложения для планирования, логистики, разработки лекарств, производственных процессов и многого другого. 

Ранее в этом месяце компания D-Wave заявила, что квантовые машины теперь могут решать проблемы реальных приложений быстрее, чем любой обычный компьютер. Ранее в этом году компания анонсировала квантовый компьютер с 1,200 кубитами, 10,000 20 соединителями и в XNUMX раз более быстрым временем решения сложных задач оптимизации.

Акции компании в настоящее время торгуются на уровне $1.86, что на 138.6% выше с начала года (с начала года), при рыночной капитализации $267 млн. Компания сообщила о продажах в размере $8.247 млн ​​(TTM), -0.66 EPS (TTM) и -3.19 P/E (TTM), а также объявила о росте продаж более чем на 20% как по результатам четвертого квартала, так и по итогам 4 года, в то время как количество заказов увеличилось на 2023% и 34% соответственно. 

Интересно, что генеральный директор компании д-р Алан Барац заявил об успехе фирмы, сославшись на многолетнее стратегическое партнерство компании с Zapata AI, внедрение прототипа Advantage1,200 с 2+ кубитами, совместные предприятия с NEC Australia и Deloitte Canada, а также назначение бывшего министра внутренней безопасности Кирстьен Нильсен в совет директоров.

Заключение

Ожидается, что рынок квантовых вычислений достичь 6.5 млрд. долларов в 2028 году, и его потенциал решения проблемы коммивояжера (TSP) имеет последствия для нескольких отраслей, таких как производство, логистика, управление цепочками поставок, электронная коммерция, транспорт и исследования. В конце концов, это может привести к существенным выгодам, в частности к повышению производительности, сокращению расходов и стимулированию инноваций в различных секторах.

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