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

N+1Наука

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

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

Егор Конюхов

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

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

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

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

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

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

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

Сатурн выбросил комету за пределы Солнечной системы Сатурн выбросил комету за пределы Солнечной системы

Комета A117uUD встретилась с Сатурном и теперь улетает из Солнечной системы

ТехИнсайдер
Как убрать живот мужчине в домашних условиях: 5 упражнений от тренера Как убрать живот мужчине в домашних условиях: 5 упражнений от тренера

Почему растет живот у мужчин и как от него быстро избавиться?

РБК
Иоганн Вольфганг фон Гёте: место Иоганн Вольфганг фон Гёте: место

Гёте — классик, романтик, гений эпохи романтизма

Знание – сила
5 точек красоты: как делать массаж лица шиацу правильно 5 точек красоты: как делать массаж лица шиацу правильно

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

Psychologies
«Докторская» колбаса и зеленка: вещи, придуманные в СССР, которыми мы пользуемся до сих пор «Докторская» колбаса и зеленка: вещи, придуманные в СССР, которыми мы пользуемся до сих пор

Наработки из СССР, над которыми время оказалось не властно

ТехИнсайдер
«Болячки прикладывали прямо к экрану»: псевдоцелители и «натуропаты» в новейшей истории России «Болячки прикладывали прямо к экрану»: псевдоцелители и «натуропаты» в новейшей истории России

«Целители», которые обещали людям из СССР лекарство от всех болезней

Правила жизни
Андрей Себрант: «В карьере нет заранее известной конечной точки» Андрей Себрант: «В карьере нет заранее известной конечной точки»

Как технологии повлияли на карьерное развитие в IT и где искать предсказуемость

РБК
Смышленый и не малый. Тест-драйв нового Haval F7 Смышленый и не малый. Тест-драйв нового Haval F7

Чем удивил на тест-драйве новый Haval F7 и сколько он стоит

РБК
Что заставляет нас заводить отношения: 3 ложных мотива Что заставляет нас заводить отношения: 3 ложных мотива

Какие мотивы вступить в отношения можно назвать истинными, а какие ложными?

Psychologies
Нужно ли рассказывать всю правду о себе партнеру: 3 истории Нужно ли рассказывать всю правду о себе партнеру: 3 истории

Три истории, которые доказывают: иногда не стоит раскрывать всю правду партнеру

Psychologies
Роботы и инвесторы Роботы и инвесторы

Минпромторг предлагает новый вид специальных инвестиционных контрактов

Монокль
Ярчайшая Ярчайшая

О самой яркой звезде ночного неба — Сириусе

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

Как связаны менструации и депрессии, гормоны и психика?

Psychologies
Топ-6 мифов о яхтинге в России Топ-6 мифов о яхтинге в России

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

Maxim
Трезвые разговоры в баре: Екатерина Манойло и Михаил Турбин Трезвые разговоры в баре: Екатерина Манойло и Михаил Турбин

Что обсуждают писатели, когда встречаются в баре рано утром?

СНОБ
Чувствовал себя лишним: Джинён из GOT7 едва не покинул группу на пике ее популярности Чувствовал себя лишним: Джинён из GOT7 едва не покинул группу на пике ее популярности

Пак Чинён, или Джинён, всерьез рассматривал вариант покинуть k-pop сцену

VOICE
Легендарная вещь времен СССР: почему у граненого стакана было именно 16 граней Легендарная вещь времен СССР: почему у граненого стакана было именно 16 граней

Как и когда в СССР появился граненый стакан

ТехИнсайдер
«Стихи Живаго и есть то, что нужно было сказать» «Стихи Живаго и есть то, что нужно было сказать»

Константин Поливанов о том, зачем Пастернаку понадобился доктор Живаго

Weekend
Что вытворяют тарантулы во время стресса и какой вид смертельно опасен для человека: 50 шокирующих фактов о пауках Что вытворяют тарантулы во время стресса и какой вид смертельно опасен для человека: 50 шокирующих фактов о пауках

Пауки не только устрашающе выглядят, но и полны загадок

ТехИнсайдер
«Смерч 2»: блокбастер о девушке-метеорологе, которая бросила вызов торнадо «Смерч 2»: блокбастер о девушке-метеорологе, которая бросила вызов торнадо

«Смерч 2»: больше, чем захватывающий фильм-катастрофа

Forbes
Как преодолеть финансовые конфликты в семье: практическое руководство Как преодолеть финансовые конфликты в семье: практическое руководство

Как разрешить финансовые трудности в семье и при этом укрепить свои отношения?

VOICE
Желание превыше всего: 5 лучших эротических драм Желание превыше всего: 5 лучших эротических драм

Фильмы, которые изучают запретную любовь с точки зрения женщины

Psychologies
Дофамин и его предшественник леводопа усилили деградацию бета-амилоида в префронтальной коре мышей Дофамин и его предшественник леводопа усилили деградацию бета-амилоида в префронтальной коре мышей

Дофамин и леводопа индуцируют деградацию бета-амилоида в мозге мышей

N+1
Поворот в сторону профессионалов: обучение в колледжах вновь востребовано Поворот в сторону профессионалов: обучение в колледжах вновь востребовано

Как будет развиваться среднее профессиональное образование в России

ФедералПресс
Россия по-итальянски Россия по-итальянски

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

2Xplore
Томас Гунциг «Рокки, последний берег». Жить после апокалипсиса Томас Гунциг «Рокки, последний берег». Жить после апокалипсиса

«Рокки, последний берег»: герметичный роман-размышление о постапокалипсисе

СНОБ
Дорогие и грязные: почему в Москве-реке, Ганге и Темзе нельзя купаться Дорогие и грязные: почему в Москве-реке, Ганге и Темзе нельзя купаться

В каком состоянии находятся главные водные артерии мира?

Forbes
Приписываемые епископу Теодомиро останки действительно принадлежали средневековому мужчине Приписываемые епископу Теодомиро останки действительно принадлежали средневековому мужчине

Ученые исследовали останки, которые могли принадлежать епископу Теодомиро

N+1
Выходные на озере. ТОП-10 водоемов для летнего отдыха на берегу Выходные на озере. ТОП-10 водоемов для летнего отдыха на берегу

Если тебе претят морские пляжи, озера – лучшая альтернатива из имеющихся

2Xplore
Гжель: сине-бело-голубые Гжель: сине-бело-голубые

Особенности производства гжельской посуды

КАНТРИ Русская азбука
Открыть в приложении