Свежие комментарии

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

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

Однако, я тут задался вопросом — а вот если вы оказались в будущем, то что из него вести? Ну, кроме учебника истории и сборника спортивных рекордов…

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

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

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

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

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

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

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

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

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

  • v_florov

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

    • kraz

      Вот-вот, «ложка хороша к обеду». 😀

    • Iozh

      С чего бы вдруг «любых»?
      Предложите квантовый алгоритм, который решает «любые» NP-полные задачи, и Вам памятник воздвигнут нерукотворный. Ну или хотя бы докажите NP=P для квантовой машины.

      Кстати, сейчас — самое время вводит криптовалюту, имеющую в своей основе более стойкую к КК математику. 🙂

      • v_florov

        Да, Вы правы, необходимо наверное исправить на «любой значимой из уже существующих криптовалют…»

    • 2:5080/205

      О, да! Кстати, я владелей фермы на бабочках, сложность как серпом по яйцам!

  • Йож

    Вы как-то странно представляете себе квантовы компутер.
    С чего бы это умирать бинарной логике? CNOT вполне себе бинарный, как и кубит — он хоть и «ку», но таки «бит». Откуда взялась шестеричная и почему именно она? 🙂 Построение системы с чистыми состояниями не кратными двойке — это та ещё задача, а вот для кубита физических основ полнО.

    «Программное обеспечение» в любом обозримом будущем пользователя квантового компутера волновать не будет. Ибо всего более-менее применимых квантовых алгоритмов сейчас известно несколько штук, да и то — условно применимых (скажем, алгоритм квантового поиска по базе требует квантового же хранилища инфы, время когерентности которого должно, очевидно, превышать время работы алгоритма; что с позиций сегодняшней науки — ну о-очень нетривиально). В 2005-м DARPA объявила о выплате миллиона каждому, кто предложит новый квантовый алгоритм для практически применимых сейчас задач. С тех пор никто этот миллион так и не получил. 🙂
    В любом случае это программное обеспечение вовсе не подразумевает, что должен использоваться какой-то особый способ программирования, исползуется всего лишь особый способ вычислений. Но не более того.

    И что касается самого применимого квантового алгоритма (ну, нашего всеми любимого Шора), то он не позволяет «взламывать шифры». Он позволяет быстро вычислять дискретный логарифм. Это помогает взламывать конкретно RSA (и шифры ещё несколько систем, основаных на вычислительной сложности дискретного логарифма), но НИЧЕГО БОЛЕЕ.
    RSA сам по себе сейчас считается уже неприемлимо слабым для серьёзных применений при разумной (до килобита) длине ключей, а какое-нить эллиптическое кодирование на вычисление дискретного логарифма плевать хотело.

    Ну, разве что на биткойнах охолотиться. Но и там всё очень непросто будет. 🙂

    • kraz

      Бинарная логика не вымрет (как не вымерла аналоговая техника, просто сократился круг ее использования). Я писал именно о методах шифрования, сейчас ведь разрабатывают квантовые методы — они могут определить, копировали ли сообщение по пути к адресату.

      >>«Программное обеспечение» в любом обозримом будущем пользователя квантового компутера волновать не будет

      Тут вопрос что считать «обозримым будущим», потому как не успел я статью написать, так вот вижу — http://www.ixbt.com/news/hard/index.shtml?17/52/43 (это к вопросу «только RSA»).
      Но честно клянусь — статью я писал раньше!

      • Iozh

        Что-то у Вас вообще всё в кучу. Может, имеет смысл почитать что-нить по теме, прежде чем статью писать и людей просвещать? 🙂
        Квантовая криптография относится к квантовому компутеру примерно как голубиная почта к линотипу. Ну, то есть, в целом — никак.
        Разве что метод генерации спутаных пар фотонов _может_ применяться в том числе и в некоторых способах реализации квантового компа (но, скажем, в том же проце от D-wave — не применяется; там технологическая основа — переходы Джозефсона, как в сквидах).

        Ну и?
        Это совершенено неважно.
        Это как-то делает более осмысленным написанное Вами? или менее правильным написаное мной?
        Я же сказал — шифры, имеющие в своей основе сложность вычисления дискретного логарифма (то бишь, в свою очередь, операции разложения на множители). RSA просто самый практически значимый из них.
        И да, проц от D-wave — это именно очень хороший пример того, каким будет КК, для каких целей, кем и как он может использоваться. Ни о каких «сложностях программирования» тут речи для пользователя не идёт, «сложность программирования» в данном случае — часть сложности создания конкретного ускорителя. Скажем, понмянутый продукт d-wave не все считают «истинным КК» 🙂 из-за того, что им пришлось срезать несколько углов; с практической же точки зрения это КК, потому что позволяет возспользоваться преимуществами алгоритма Шора.
        КК — это не «как обычный комп, только быстрее». Там, на чипе, не выполняется никаких программ, как Вы себе это представляете, его не нуженно «программировать». Это спецускоритель для спецприменений, не более того.

        • kraz

          Самый качественный повод для спора — это такая технология, которой пока нет и неясно как оно будет работать. 😀

          >>Квантовая криптография относится к квантовому компутеру примерно как голубиная почта к линотипу

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

          >>Это как-то делает более осмысленным написанное Вами?

          Это просто возвращает вас к теме статьи, а не на поле виртуальных измышлений «как это будет».
          То, что вы написали — правильно, но к статье отношения не имеет. Именно это я и хотел сказать.
          Давайте не будем топить в ртути урановые ломы, а?

          • Iozh

            Ну, она как бы есть. Качественно, если не количественно присутствует. И даже на свободном рынке.

            Ну, шифры, основанные на решётках вполне себе пока устойчивы к КК.
            И, скажем, самый классический пример NP-полной задачи, истасканный из учебника в учебник — задача коммивояжёра, КК-алгоритмами никак не ускоряется. И, конечно, она может быть основой шифра, как и любая обратная задача, чья сложность много выше прямой. Так что шифрование ещё поживёт.

            По теме же статьи: я всё же не очень понимаю, что Вы будете делать в нашем времени с КК. Это э классический «белый слон», который принесёт пользу только в очень считанном числе очень конкретных организаций к коим Вы, думаю, отношения не имеете… Причём, в будущем эта штука тоже будет принадлежать не всем, а только тем, кому он очень нужен. Почему бы не попросить прихватить «обычный» комп? слишком банально? 🙂
            С учётом пока ещё соблюдающегося закона Мура универсальный вычислитель из будущего может принести куда больше пользы.

            Скажем, суперкомп 80-х (коих было в числе одной штуки на страну) в десятки-сотни раз слабее современной персоналки. А разница всего 30 лет.
            Учитывая инерционность массовых систем и их повальную тягу к обратной совместимости, запустить на нём современные задачи не составит проблем.

            А вот с квантовым компом, как и с любой достаточно продвинутой технологией, такие проблемы вполне могут быть. Там, где квантовые компы повсеместны, они не взламывают шифры (а программирование/перестройку КК под Ваши задачи сами Вы точно потянете?). Там, где ещё есть потребность во взломе шифров, там КК только у Очень Серьёзных Организаций под большим замкОм. Там, где КК массов, его типичная задача — вовсе не взлом шифров, а расчёт мультикульных пик-форм для хренуляции в ДНК-репликаторе и соотвествующие библиотеки для взома шифров — Ваши проблемы.
            Масштаб таких проблем легко прикинуть, если представить себя 30 лет назад с задачей приспособить Х-бокс и три сюдюка с играми к нему к задачам народного хозяйства СССР.
            Пусть даже Вы лично профи в программировании, и Вам выдан аж цельный профильный институт.

            • kraz

              >> Это э классический «белый слон», который принесёт пользу только в очень считанном числе очень конкретных организаций к коим Вы, думаю, отношения не имеете…

              А что тут не в «очень считанном случае»? Технология культивирования жемчужин — это для всех? Водокольцевые насосы для всех? Да даже арабские цифры — не для всех! Это касается всего — и прошлого и настоящего и будущего.

              >>С учётом пока ещё соблюдающегося закона Мура универсальный вычислитель из будущего может принести куда больше пользы.

              Уточните, пожалуйста, какую именно пользу они могут принести.
              Потому как в 50-е годы все вычислительным мощности АН СССР были в разы меньше, чем у китайского смартфона, но на них считали атомные бомбы и атомные подводные лодки. И ничо, хватало.

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

              Ну почему же «могут быть»? Они обязательно будут! А с какими-нибудь ализариновыми чернилами, думаете, их не будет? 😀

              • Iozh

                Так дело в том, что эти конкретные организации очень уж специфичны; однажды засветившись там и с такой штукой из неведомых далей, просто уйти оттуда не получится. Пользы от такого подарочка из будущего для «одарённого»? 🙂

                Расчёт расчёту рознь. Конструктор лодочных реакторов (профессор Макаров, мир ему), 10 лет назад за чаем рассказывал, КАК и ЧТО считали при конструировании лодочных реакторов. Одним из главных инструментов «расчётов» по НФХ были тупо критсборки, которые они ручками собирали из брусков урана и бериллия (кстати, суть рассказа была в историческом анекдоте: на совещании как именно скреплять блоки чтоб не вносить искажения в нейтронику они парились почти час, и вопрос, по байке Макарова, решила секретарша, которая предложила их просто склеивать, как потом прикинули, тонкий слой клея БФ не влиял на систему заметно).
                И вот так — брусочек к брусочку, закладывая где надо сталь и стальные ёмкости с водой, модерировали будущий реактор.
                Нужно объяснять, чем расчёты на компе лучше?

                Что касается бомбы — так неспроста ж первые бомбы в пару десятков кт весили по 5 тонн, а современные весят сотни кг на почти мегатонну. Например, куча расчётов (там, где вообще считали) велась в одномерном приближении. Откуда и «ёжик» — плутониевая сфера, утыканая взрывателями со сверхточной инициацией, «крылья лебедя» появились много позже, это не только идея, это ещё и расчёт.
                А выигрыш у двухточечной схемы не только по массогабаритам, выгоранию, килотоннам/кг, но и по простоте изготовления, технологичености.

                Это Ваши же 2 примера. А такой фарш там далее по всему мясокомбинату. Возможность даже примитивнго МД-моделирование решило бы кучу проблем авиации (а это как раз тот случай, когда математика/алгоритмы приметивны, но вычмощь нужна бешенная). Кстати, моща и сейчас для этих целей недостаточна, и КК тут не помошник, а вот классический но сверхбыстрый — мог бы ещё как помочь. Ну и если мощь была бы достаточна для моделирования плазмы, то +100 к разработке термоядерного реактора; у всех сегодняшних конструкций ноги растут из «докомпьютерной эпохи». Из-за невозможности посчитать напрямую, приходмится аппроксимировать, и математика там выходит зубодробительная.


                С ализариновыми чернилами разница в том, что тогдашний требуемый НИОКР на такие вещи — это человеко-годы. НИОКР по приспосабливанию какой-нить современной видеокарты в качестве суперкомпа 1970-х — это сотни-тысячи-десятки тысяч человеко-лет. НИОКР по приспособлению специализированного квантового компа к современным задачам Вы можете просто не потянуть. И/или овчинка просто не будет стоить выделки.

                • kraz

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

                  А однажды засветившись с мобилкой от НКВД уйти получится?
                  А однажды засветившись с гальваникой от инквизиции уйти получится?
                  А в какие времена получится?
                  Тут же такая вещь — не засветится у попаданца выйдет, только если он в горах пчел будет разводить. Хотя тоже со временем к нему зайдут…

                  >>Нужно объяснять, чем расчёты на компе лучше?

                  Ну тогда вспомните еще, какую пользу с этого всего будет иметь попаданец и через сколько лет.
                  Потому что от таких расчетов его точно отодвинут (он просто квалификации не имеет). То есть софта у него нет, а сам написать он не может.
                  Попаданец в этом случае — просто курьер, который привез комп.

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

                  То, что хорошо для цивилизации совсем не обязательно хорошо для попаданца…

                  • Iozh

                    От шанса получить бандитскую пулю никто не застрахован, если Вы — бандит, то такой шанс ЗНАЧИТЕЛЬНО выше. Если Вы взялись барыжить наркоту, то Вы выходите совсем на другое поле, переходите из категории мебели в категорию фигур, требующих особого внимания.
                    Одно дело для НКВД, если где-то как-то далеко есть человек с непонятно-чем, что очень круто помогает народному хозяйству. Это требует внимания, но не более.
                    Другое дело, если Вы приходите в эту организацию с оченно профильным для неё дивайсом, начинаете играть значимую роль на ИХ ПОЛЕ. Тут священный долг каждого Сикорского выяснить, где, кто, с кем, состоял ли, участвовал ли, и имел ли. И после этого пасти как Абалкина. Только уже с собаками, чай, не в Мире Полдня живём.
                    Если Вы сидите и тихо прогрессорствуете с гальваническими покрытиями, Вы интересны в первую очередь местным ремесленникам, а для инквизиции проходите где-то на периферии в категории «всё прочее». Если начинаете проповедовать о том, что Библия в некоторых моментах не совсем точна, Вы уже для ремесленников попадаете куда-то на край зоны внимания, зато вот инквизиции становитесь резко интересны.
                    Так люди устроены.

                    Попаданец с компом в 50-е? или сейчас?
                    Он получит большую пользу в любом случае (попаданец-программист довольно типичен, замечу), но и знания среднего технаря в программировании, думаю, всё-таки на уровне сильно выше среднего технаря 50-х. Фактически, во всех аспектах кроме математики вровень ему идут лишь несколько десятков человек, которые с вычтехникой (очень редкой тогда) имеют дело на постоянной основе. И в практическом опыте обращения с вычтехникой он становится очень ценным кадром, вопрос лишь как он этим распорядится. Шанс пригреться-прикормиться и принести большую пользу почти 100%, старт — великолепный.

                    Сейчас — ещё проще. Есть куча вычислительно ёмких задач, решаемых на договорной основе, есть почти анонимные и совсем анонимные способ конвертировать вычмощь в деньги (да хоть тот же биткойин). Вы можеет буквально продавать вычмощь, совершенно легально (если не найдёте способ заработать на этом получше).
                    Если не нравится биткойн, можете лекарства считать. За это платят; имея фору в виде нулевых вложений и минимальным расходам на энергию, Вы можете перебить самое дешевое нынешнее предложение на рынке, и всё равно остаться в огромном плюсе.

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

                    А вот насчёт отношения цивилизации и попаданца — согласен.

                    • Iozh

                      То есть, быть вовлечённым в секреты и дела аэродинамики и быть вовлечённым в секреты и дела спецслужб — это очень разные вещи с точки зрения внимания этих спецслужб и их толерантности к «шагу влево, шагу вправо и прыжку на месте».

                      С инквизицией — та же фигня.

                    • kraz

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

                      >>И Вы не можете купить его сейчас, потому что он по сути нафиг никому не нужен.

                      Интересно, а вы искали?

                    • Iozh

                      Даже просто добыча данных для расшифровки будет той ещё задачей. Подключение к банковской сети, обдирка всех слоёв шифрования… Вы знакомы с форматом данных, которыми обмениваются интересующие Вас конторы? если нет, то как взлымывать?
                      Это опять задача на много человеко-лет (по этой причине «крутые хакеры ломают банки» только в фильмах, а по жизни этим занимаются инсайдеры, что снимает им 99.9% труда), в одиночку не потянете, потребуется социальная инженерия, и всё равно риск засыпаться на любом этапе. Ладно, хорошо, КК сделает за Вас работу вычислительно сложной части, но кто будет элементарно ЛОМАТЬ шифр? В смысле — приводить физический поток данных с канала в формат тех самых чисел, которые нужно факторизовать. Даже самый примитичный случай: у Вас шифрованное письмо — Вы знаете хотя бы ЧЕМ оно шифровано? В мире сотни разных программ, реализующих пусть даже одни и те же алгоритмы, но по-разному, а для Вас чисто техническая перестановка двух байт в потоке означает полный провал и необходимость разбираться с тем, какие два байта перевёрнуты и какие ещё нужно перевернуть.

                      Вы постоянно подчёркиваете сложность решения попаданческих задач, ну так тут-то Вы — и вовсе современник, сверхсложность таких мероприятий Вам не очевидна?

                      Я уже говорил, но, видимо, нужно поставить на этом ударение: сложность современных задач (в смысле, более-менее на краю прогресса) непомерно велика для одного человека.
                      Поэтому даже «магический» для данного времени-места дивайс должен:
                      — либо сразу и без переделок занимать уже имеющуюся нишу совеременного аналога (причём, аналог у попаданца должен уже иметься и использоваться в этой нише);
                      — либо быть востребованым/легко воспринятым нынешним обществом без проблем для попаданца.

                      Иначе — чемодан без ручки.

                      Под имеющийся КК нужно создавать команду/контору просто для того чтобы его использовать. А учитывая его возможности вылезать в поле зрения людей и структур с большими возможностями и не очень озабоченных законом… ну его нафиг, ИМХО.

                    • Iozh

                      Конечно, я не искал ускоритель для взлома DES. На элементной базе 90-х он совершенно неинтересен (нынешние универсальные компы быстрее, и они достаточно быстры, чтоб сделать бессмысленной саму задачу специального ускорителя).

                  • dimav

                    ну от НКВД уйти может и не получится (точнее от него полюбому не уйти будет. даже без мобильки)
                    а вот от ФБР/ЦРУ «уйти с мобилкой» можно. а вот с квантовым компьютером да еще с тем узким применением «уйти» не получится. и выбирать придется между ЦРУ/ФБР/ФСБ и какиминибудт крутыми «цифровыми» ОПГ. так что смело ставте tag «плохая идея».

            • Тарас

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

              Наоборот. Программы для него на современных идут, а современные на нём не пойдут. И от несовместимости, и от дефицита ресурсов.

    • Тарас

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

      Не буду говорить о тривиальности, повозиться как раз придётся и не только инженерам с рабочими, но это, видимо, БД на основе голограммы.

    • Тарас

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

      Одно как раз вытекает из другого. Даже векторный компьютер программируется иначе, чем скалярный, или суперскалярный. И не только на языке ассемблера. Вот суперскалярный можно программировать также, как и скалярный. А любое кардинальное отличие в способе вычислений отражается на программе и наоборот.

    • Тарас

      >В 2005-м DARPA объявила о выплате миллиона каждому, кто предложит новый квантовый алгоритм для практически применимых сейчас задач. С тех пор никто этот миллион так и не получил.

      Вот. Именно потому, что он программируется на столько иначе, что для этого вообще нет хоть каких то специалистов.

  • Alex Besogonov

    Ой йо!

    Квантовый компьютер — не очень полезная вещь. Он сильно известен из-за того, что для него есть быстрые алгоритмы факторизации и, предположительно, дискретного логарифмирования. Однако, для ПРОИЗВОЛЬНОГО шифра они ничем серьёзным не помогут — квантовые компьютеры дают всего лишь квадратичный прирост скорости для них. Так что сложность взлома 256-битного симметричного ключа на квантовом компьютере будет равна сложности взлома 128-битного на обычном. Так что, фактически, 256-битные ключи являются невзламываемыми.

    Насчёт ДНК — её можно хоть сейчас синтезировать, 35 центов за базовую пару до 3000 пар (http://www.genewiz.com). Только смысл? В ДНК самое сложное — это протеины, которые синтезируются.

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

    Вот что надо брать из будущего и что можно сразу применить — это высокотемпературные сверхпроводники. А так же схемы практических термоядерных реакторов.

    • Iozh

      Почему «предположительнео» про дискретный логарифм?

      Что значит «квадратичный прирост для произвольного шифра»? Это как? Что это за новое слово в прикладной математике?
      Каким образом Вы связали разрядность ключа в произвольном алгоритме с o(n)?
      Почему 256-битный ключ (для какого алгоритма?!) является невзламываемым? («- Петька, приборы?! — 15!!! — Что «15»? — А что «приборы»?»(с)) Скажем, практически продемонстрирован взлом того же RSA до килобита включительно, но сложность взлома при данной длине ключа зависит от алгоритма; в том числе — конкретной его вариации.

      • Alex Besogonov

        Отвечаю по порядку:

        1) Для квантового компьютера есть эффективный алгоритм поиска в неупорядоченной базе данных, который работает за O(sqrt(N)) шагов. Причём доказано, что этот алгоритм оптимален. Классической работает за O(N), напоминаю.

        2) Brute-force взлом шифра как раз сводится к этому случаю, так что классический алгоритм, работающий в среднем 2^255 шагов (для 256-битного ключа) будет на квантовом компьютере работать примерно за sqrt(2^256) = 2^128 шагов.

        3) 256-битный ключ для стойкого алгоритма является невзламываемым из-за того, что выполнение 2^128 шагов на ЛЮБОМ компьютере потребует (как минимум) вскипятить все океаны Земли для охлаждения этого компьютера (поиск источника энергии для него — домашнее задание читателю).

        4) Если взять 256-битный брут-форс, то это уже надо энергию десятка суперновых.

        5) RSA — это очень частный случай алгоритма, для него известен эффективный квантовый алгоритм, работающий за O(N^2.5) шагов от длины ключа.

        • Iozh

          1. О, нет.
          а) Чистый перебор — это очень уж теоретически.
          б) Алгоритм Гровера хорош в теоретическом плане, но у него (в его общем виде) совершенно особые требования к железу КК, НЯП, для его использования нужно держать _все_ 2^n записей базы данных (ну или полное представление f(x), назовите как угодно) в памяти КК в _когерентном состоянии._
          Причём, всё время вычисления. 🙂
          Пожалуйста, попробуйте преставить себе масштабы бедствия. 🙂
          То есть, чисто математически это всё здорово, но даже с точки зрения теорфизики упирается в то же «кипячение океанов», только с другой стороны.
          Чтобы понять проблему: для оригинального алгоритма Шора (квантовая факторизация, которая ломала бы RSA), нужно иметь в когеретном состоянии количество кубитов равное длине ключа (ну, то есть, сколько-то там сотен) на время работы алгоритма. И с этим сейчас есть _большие_ проблемы по общефизическим соображениям.

          3) Под «стойким» Вы понимаете «обратная задача к которому сводится исключительноо к перебору»? А есть ли такие алгоритмы сейчас вообще?

          5) Да. Но я говорил о взломе RSA классическими вычислителями. Кстати, ASICи, заточеные на задачу факторизации, появились далеко не вчера.

          • Alex Besogonov

            1) Для поиска в БД есть возможность не держать все данные, достаточно оракула, проверяющего результат. Это не спасает ситуацию, так как всё равно бедствие из-за количества шагов.

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

            Так что польза от КК будет только во взломе RSA. Неплохо, но люди быстро переключатся на что-нибудь другое.

      • Alex Besogonov

        В Applied Cryptography есть оценка максимальной эффективности, вот тут цитата из этой книги: http://security.stackexchange.com/a/25392

    • kraz

      >>Вот что надо брать из будущего и что можно сразу применить — это высокотемпературные сверхпроводники.

      Что-то мне подсказывает, что сейчас произвести те высокотемпературные проводники будет ничуть не проще, чем ванадий-молибденовые мечи в Древнем Риме…

      >>А так же схемы практических термоядерных реакторов.

      А они точно будут? 😀

      • Alex Besogonov

        По отдельным молекулам собирать кристаллы мы пока не умеем. Но вдруг это и не надо?..

        >А они точно будут? 😀
        Хотелось бы. Буду в будущем — спрошу 🙂

        • kraz

          >>Но вдруг это и не надо?..

          Это точно надо и это точно будет сделано. Если какой глобальной катастрофы не произойдет…

          >>Буду в будущем — спрошу

          Мы все двигаемся в будущее своим ходом. Проблема в скорости! 😀

  • Lalartu

    Хм, а что бы затребовали из 2010-х жители скажем 1960-х (т. е. по их представлениям)? Скорее всего — термоядерные реакторы, летающие автомобили, планетолеты, реактивные ранцы, роботов-уборщиц и тому подобное. Это к тому что фиг его знает что там будет в будущем.

    • 2:5080/205

      Про роботов-уборщиц пальцем в ебо, ну а про остальное неплохо написано на памятнике Гагарину — «Юра, мы все просрали».

    • kraz

      Жители 60-х просто неверно оценивали скорость прогресса, «наше поколение будет жить при коммунизме».
      Все перечисленное будет, но слегка потом..

  • Dr. Jet

    Смотря какое будущее имеется в виду… Если эпоха активной внеземной колонизации а-ля Стругацкие/Шумилов — лучший вариант — притащить «киберзародыш». То есть бронекапсулу с реактором, ограниченным искином с обширной БД и кучей наноботов. Активируем её на любой заброшенной крупной свалке (ибо там всё необходимое сырьё собрано в шаговой доступности) и через недельку имеем дюжину строительно-ремонтных киберов, а через полгодика — полноценную дальнекосмическую базу — с производственными линиями, охранными системами и т.д. и т.п.

  • Сергей Александров

    Статья ни о чем. Никто не знает, что будет в будущем, и что может оказаться наиболее полезным одному человеку.
    Давайте рассмотрим вопрос с другой стороны: какой девайс может оказаться наиболее полезным в прошлом?
    Или, ближе к статье, Вы оказались в 70-х или 80-х годах прошлого века (когда там произошла компьютеризация банковской деятельности?) с самым современным компьютером, который легко ломает тогдашние шифры. Ваши действия?

  • Тарас

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

    Самая бесполезная сейчас штука — это именно квантовый компьютер. А фокус прост: для него нет ни программ, ни программистов и даже не понятно, как учить пользователей. Более того, он как раз давно создан, а учёные бьются как раз над его хоть каким то применением. И не находят. Не находят не целей применения, а способов. Ну вроде как был бы у Ньютона современный компьютер вообще без программ, даже без прошивки биоса, но с электростанцией в придачу. Смог бы он научиться им пользоваться? Нет. Потому что без программистов эта вещь мертва. Также и сейчас с квантовым. И вот этой то задачей исследователи квантовых вычислений и заняты, они учатся пользоваться квантовым компьютером. И полезен он станет не раньше, чем у них будет хоть какой то результат. А создать нечто хоть на миллион квантов как раз не проблема даже в прошлом веке. Проблема использовать эти кванты как кубиты.

  • Тарас

    >Дело в том, что математически доказано, что квантовые компьютеры будут пригодны для одной задачи — ломать современные шифры.

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

    • kraz

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

  • Тарас

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

    Она называется шетизначная, а не шестеричная. И шестиричная логика тоже чёткая. И вполне понятная. А нечёткая как раз давно разрабатывается безо всяких квантов и отлично представляется двоичными числами. Её кардинальное отличие в том, что любое логическое значение в ней — это действительное число, выражающее вероятность, значение которого классифицируется на несколько категорий вроде «не вероятно», «весьма сомнительно», «может быть», «вероятно» и «очень ожидаемо». Кстати, именно этот ряд пятизначен. Классификация вероятности по сути приводит нечёткую логику или к бинарной, или к одной из многозначных. В том числе, можно и к трёхзначной с рядом: «нет», «может быть» и «да». Но не сводит, так как сами границы категорий не имеют чётких критериев, а только задаёт некое соответствие вероятности истинности (наступления события) бинарной, или многозначной логической величине, но тоже с некоторой вероятностью. То есть логическая величина с некоторой вероятностью равна такому то пятизначному логическому значению. Или шестизначному. Или стодесятизначному. Или бинарному. На любой вкус, запах и цвет. А шестиричным бывает число.

  • Тарас

    >Но вот что точно будет — так это простенький софт для взлома текущих шифров.

    DES давно взломан классическими компьютерами, простенького софта для взлома DES в открытом доступе нет.

  • Тарас

    Нечёткая логика как раз аналовая, а не цифровая. И в цифре лишь эмулируется. А вот будет ли квантовый комп именно из будущего её эмулировать или реализует непосредственно — это вопрос отдельный. Он может как вычислять вероятность в некотором цифровом (скорее всего двоичном) представлении, так и представить её статистической частотой того, что кубит примет такое то значение, что будет альтернативной (потому что дискретной) физической реализацией нечеткой логики.

  • Gradient

    Полагаю, квантовый компьютер будет очень эффективен для машинного обучения. Не очень разбираюсь в том, как этот компьютер работает, но насколько я понял, он примерно эквивалентен ферме из огромного числа процессоров.
    Если это так, то на нём можно в очень сжатые сроки проводить алгоритмическую индукцию, которая может подобрать предсказательную модель для более-менее любых данных. А на базе неё — AIXI, который здорово похож на универсальный достигатель целей =)
    Примерная схема описана здесь:
    https://en.wikipedia.org/wiki/AIXI
    Сейчас AIXI нет в основном потому, что он требует возможности тестировать огромную кучу гипотез — проводить тот самый подбор ключа.

  • Taras

    Квантовый компьютер давно существует. А учёные с ним возятся только потому, что даже они не понимают, что с ним делать. Не как сделать сам компьютер, а что с ним делать. Никто, включая учёных, не умеет ни пользоваться, ни программировать. И именно это пытаются изучить. А разобраться с компом из будущего на много тысяч кубит будет сложней, чем с лабораторным девайсом на 69 кубит.

    • Arpanx

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

Leave a Reply to kraz Cancel reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>