Сколько поле не квантуй
По наводке наткнулся на прелестный хайп про "квантовые компьютеры":
"Можно подумать, что квантовый компьютер — это просто ускорение. Однако наш обычный компьютер не так далеко отстоит от счет, которыми считали несколько тысяч лет назад, как квантовый от настоящего. Там используется совершенно другая логика», — объяснил эксперт.
Он подчеркнул, что эта разработка даст человечеству решать задачи, с которыми сегодня мы справиться не можем. В качестве примеров Юнусов привел ситуации, когда необходимо упаковать сто разных коробок или развезти много посылок по разным точкам. Современные системы не могут подобрать оптимальное решение, потому что объем необходимых для анализа данных очень быстро растет и необходимо подобрать ключ к каждому элементу отдельно."
https://xn--80aapampemcchfmo7a3c9ehj.xn--p1ai/news/zemnye-khroniki-chego-boyatsya-sovremennye-uchenye
Фактически Юнусов говорит обо всём классе NP-hard задач, где число возможных решений, которые можно перебрать, растёт астрономически с числом переменных - обычно суперекспоненциально, как факториал или похоже.
С первой из этих задач - "упаковать сто разных коробок" - только намного сложнее, до нескольких тысяч коробок, и с кучей дополнительных ограничений и оптимизационных критериев, я знаком не по наслышке. Я реализовал (с моей командой) практическое решение этой задачи которое является, вероятно, лучшим в мире на сегодняшний день (именно в практическом смысле, "чистая" математика меня в этом мало интересует). И, кстати, все академические работы на эту тему, которые доводилось видеть, имели примерно нулевую пользу в процессе решения. Равно как и модные подходы типа "машинного обучения".
Второй задачей - "развести много посылок по разным точкам", travelling salesmen problem - я, в более узком смысле, занимаюсь сейчас, с маршрутизацией группы мобильных роботов.
Что я хочу сказать - для этого не надо квантовых компьютеров. Ну то есть, в некоем сферическом прекрасном будущем можно представить квантовый компьютер который сможет перебрать стопятьсот миллиардов квинтильёнов вариантов и найти абсолютный оптимум. Моё решение, которое перебирает, скажем, миллиарды вариантов, но очень направленно - кое-где с фантастически настроенной комбинаторикой, с тонкой эвристикой, кое-где с помощью говна и палок - найдёт решение которое на 0.2% хуже абсолюта. Но лучше и не надо, эта разница - сущая мелочь по сравнению с другими неэффективностями во всей системе. И так в подавляющем большинстве подобных задач. Я не думаю чтобы в сколько-нибудь обозримом будущем какой-нибудь квантовый компьютер справлялся бы с подобными сложными задачами лучше чем специализированные умные алгоритмы. Но, впрочем, вбухивать деньги в "квантовые компьютеры" проще чем воспитывать специалистов, которые могли бы делать такие алгоритмы.
"Можно подумать, что квантовый компьютер — это просто ускорение. Однако наш обычный компьютер не так далеко отстоит от счет, которыми считали несколько тысяч лет назад, как квантовый от настоящего. Там используется совершенно другая логика», — объяснил эксперт.
Он подчеркнул, что эта разработка даст человечеству решать задачи, с которыми сегодня мы справиться не можем. В качестве примеров Юнусов привел ситуации, когда необходимо упаковать сто разных коробок или развезти много посылок по разным точкам. Современные системы не могут подобрать оптимальное решение, потому что объем необходимых для анализа данных очень быстро растет и необходимо подобрать ключ к каждому элементу отдельно."
https://xn--80aapampemcchfmo7a3c9ehj.xn--p1ai/news/zemnye-khroniki-chego-boyatsya-sovremennye-uchenye
Фактически Юнусов говорит обо всём классе NP-hard задач, где число возможных решений, которые можно перебрать, растёт астрономически с числом переменных - обычно суперекспоненциально, как факториал или похоже.
С первой из этих задач - "упаковать сто разных коробок" - только намного сложнее, до нескольких тысяч коробок, и с кучей дополнительных ограничений и оптимизационных критериев, я знаком не по наслышке. Я реализовал (с моей командой) практическое решение этой задачи которое является, вероятно, лучшим в мире на сегодняшний день (именно в практическом смысле, "чистая" математика меня в этом мало интересует). И, кстати, все академические работы на эту тему, которые доводилось видеть, имели примерно нулевую пользу в процессе решения. Равно как и модные подходы типа "машинного обучения".
Второй задачей - "развести много посылок по разным точкам", travelling salesmen problem - я, в более узком смысле, занимаюсь сейчас, с маршрутизацией группы мобильных роботов.
Что я хочу сказать - для этого не надо квантовых компьютеров. Ну то есть, в некоем сферическом прекрасном будущем можно представить квантовый компьютер который сможет перебрать стопятьсот миллиардов квинтильёнов вариантов и найти абсолютный оптимум. Моё решение, которое перебирает, скажем, миллиарды вариантов, но очень направленно - кое-где с фантастически настроенной комбинаторикой, с тонкой эвристикой, кое-где с помощью говна и палок - найдёт решение которое на 0.2% хуже абсолюта. Но лучше и не надо, эта разница - сущая мелочь по сравнению с другими неэффективностями во всей системе. И так в подавляющем большинстве подобных задач. Я не думаю чтобы в сколько-нибудь обозримом будущем какой-нибудь квантовый компьютер справлялся бы с подобными сложными задачами лучше чем специализированные умные алгоритмы. Но, впрочем, вбухивать деньги в "квантовые компьютеры" проще чем воспитывать специалистов, которые могли бы делать такие алгоритмы.