Ученые оптимизировали маршрут между городами с помощью одного кубита

N+1Наука

Задачу коммивояжера решили одним кубитом

Пока только для шести городов

Егор Конюхов

f2e8bae82b8dd7ab7bd111d2ba6f1867.jpg
N + 1; Peter Schmelcher et al. / arXiv, 2024

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

Задача коммивояжера — известная NP-трудная проблема. Ее суть состоит в том, чтобы построить кратчайший маршрут, который проходит через каждый город один раз. Классические компьютеры для этого либо требуют огромных затрат по времени вычислений, либо позволяют найти решение, но оно не всегда оказывается оптимальным (так называемые эвристические алгоритмы). То есть маршрут будет одним из самых коротких, но только с некоторой вероятностью оптимальным. Часто оптимальность решения исследователям трудно проверить именно из-за NP-сложности задачи.

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

Авторизуйтесь, чтобы продолжить чтение. Это быстро и бесплатно.

Регистрируясь, я принимаю условия использования

Рекомендуемые статьи

Медиатор: кто это и чем занимается Медиатор: кто это и чем занимается

В каких ситуациях медиатор незаменим и чем он отличается от психолога?

Psychologies
«Неизвестное» плато «Неизвестное» плато

«Глаз», «Ступа», «Ромашка» и секреты Вилюйского плато

Наука и жизнь
Жаркая погода может убить вас: как этого избежать Жаркая погода может убить вас: как этого избежать

Перегрев может вызвать серьезные проблемы со здоровьем: как его избежать?

ТехИнсайдер
Крафтсмены Крафтсмены

Рыцари невидимого фронта, которые помогают делать рестораны особенными

Bones
«Тренд – опасное слово» «Тренд – опасное слово»

Дизайнер Наталья Белоногова — о том, как превратить ресторан в театральную сцену

Правила жизни
Как и чем убрать царапины на машине своими руками Как и чем убрать царапины на машине своими руками

Какие виды царапин бывают на автомобиле и как их убрать

РБК
«У меня лучше!»: почему некоторые люди так любят хвастаться? «У меня лучше!»: почему некоторые люди так любят хвастаться?

Почему люди любят хвастаться? Это норма или патология?

Psychologies
Как работает автопилот и чем он отличается от круиз-контроля Как работает автопилот и чем он отличается от круиз-контроля

Насколько различаются возможности автопилота и круиз-контроля в автомобиле

Maxim
«Быт разрушает наши отношения»: что делать в таком случае — 9 советов психолога «Быт разрушает наши отношения»: что делать в таком случае — 9 советов психолога

Быт в отношениях — страшный зверь, которого можно приручить

Psychologies
Правильный гардероб: писательница Вера Богданова — о стиле Бритни Спирс, фраке Мармеладова и своей любви к «леопарду» Правильный гардероб: писательница Вера Богданова — о стиле Бритни Спирс, фраке Мармеладова и своей любви к «леопарду»

Писательница Вера Богданова — о любви к казакам и пижамам

Правила жизни
Как растет взаимодействие с Китаем Как растет взаимодействие с Китаем

Китай и Россия на фоне западных санкций стали друг для друга выгодными

РБК
Делай как я: создательница кафе Eggsellent о первых деньгах и покупке «куска пустыни» Делай как я: создательница кафе Eggsellent о первых деньгах и покупке «куска пустыни»

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

Forbes
Марат Калайджян: «Людям нужна простота» Марат Калайджян: «Людям нужна простота»

Марат Калайджян — вкус во плоти, учит всех нас правильному отношению к продуктам

Bones
Мыловарение: мoем-мoем трубочиста... Мыловарение: мoем-мoем трубочиста...

Натуральное ароматное и красивое мыло несложно сделать в домашних условиях

КАНТРИ Русская азбука
Евгений Добаев: «Наш искусственный интеллект будет сильнее хакерского» Евгений Добаев: «Наш искусственный интеллект будет сильнее хакерского»

Уровень киберзащищенности организаций растет, но не так быстро, как хотелось бы

РБК
Идеальный секс проходит 7 стадий — а у вас нигде нет сбоя? Идеальный секс проходит 7 стадий — а у вас нигде нет сбоя?

Почему может произойти сбой на том или ином из этапов сексуального цикла?

Maxim
Лето в активе Лето в активе

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

Лиза
Да, анальный секс без проникновения существует — и вот как им заняться! Да, анальный секс без проникновения существует — и вот как им заняться!

Как насчет того, чтобы поэкспериментировать с концепцией анального секса?

VOICE
6 фаз отношений с нарциссом 6 фаз отношений с нарциссом

Какого сценария придерживаются в отношениях люди-нарциссы?

Psychologies
Точно в срок: 7 советов любителям опозданий Точно в срок: 7 советов любителям опозданий

Вы изо всех сил стараетесь приходить вовремя, но постоянно опаздываете?

Psychologies
Вперед и вверх: как начать заниматься скалолазанием и куда пойти Вперед и вверх: как начать заниматься скалолазанием и куда пойти

Быстрый гид по скалолазанию для начинающих

Правила жизни
«Еда – сердце ресторана, а музыка – его душа» «Еда – сердце ресторана, а музыка – его душа»

Звезда мировой гастрономической сферы Гагган Ананд – о дизайне впечатлений

Правила жизни
Рынок жилья охлаждается, но неохотно Рынок жилья охлаждается, но неохотно

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

Монокль
Любовь и деньги: на чем зарабатывают девушки самых высокооплачиваемых теннисистов Любовь и деньги: на чем зарабатывают девушки самых высокооплачиваемых теннисистов

Сколько спонсорских контрактов заключают девушки профессиональных теннисистов

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

Проверенные стратегии для укрощения «драконов» — вредных ментальных привычек

Forbes
Набрать, сбросить, повторить: как актеры вынуждены менять свою внешность ради карьеры Набрать, сбросить, повторить: как актеры вынуждены менять свою внешность ради карьеры

Как актерам приходится издеваться над собственным телом под давлением продюсеров

Forbes
Каир: город святости, богатства и нищеты Каир: город святости, богатства и нищеты

Каир – памятники ушедших эпох и современные люди, живущие в нем

Зеркало Мира
Уильям Гершель и музыка небесных сфер Уильям Гершель и музыка небесных сфер

Уильям Гершель, великий астроном, раздвинувший для нас границы Солнечной системы

Наука и техника
Сколько зарабатывает дальнобойщик и как им стать Сколько зарабатывает дальнобойщик и как им стать

Как стать дальнобойщиком и сколько он зарабатывает, выяснил Autonews.ru

РБК
Какой «Сталкер» самый лучший и интересный: сравним все вышедшие части Какой «Сталкер» самый лучший и интересный: сравним все вышедшие части

Какая часть «Сталкера» самая лучшая и интересная: атмосфера, геймплей и графика

CHIP
Открыть в приложении