Comments 24
Как алгоритм Гровера может ускорить поиск значения:
Я думал тут будет подробный разбор, как например в Алгоритм Гровера и поиск данных / Хабр (habr.com)
А тут как обычно, куча воды и гипотетическое скрещивание горячего с соленым.
Спасибо за ваш комментарий, он действительно важен для меня.
Я согласен, что следовало бы чуть подробнее рассказать про Алгоритм Гровера. Однако, вопрос в том, имеет ли смысл делать "подробный разбор" алгоритма, если на эту тему уже есть как минимум одна статья на хабре?
По поводу "воды" в тексте – я стремился сделать статью понятной для широкой аудитории, поэтому старался объяснять термины, о которых пишу. Если вам кажется, что какие-то части избыточны, пожалуйста, сообщите, какие именно. Я открыт к дискуссии и, вероятно, внесу изменения в текст статьи.
Конечно, описываемое мной является гипотетическим скрещиванием двух технологий, развивающихся и возможно влияющих друг на друга в будущем. Моя статья не претендует на 100% достоверность, и я не уверен, что квантовые компьютеры будут использоваться для подобных целей и что Алгоритм Гровера в этом поможет. Мне Кажется, лучшее качество интернета заключается в том, что любой может написать своё мнение, и другие люди смогут его оспорить или согласиться с ним.
Еще раз спасибо за ваше мнение, оно действительно ценно для меня. Было бы полезно, если бы вы написали более детально, что именно стоит исправить.
Алгоритм Гровера это алгоритм, который относится к методу перебора. При майнинге вычисляя очередной бесполезный хеш в результате получается почти рандомный набор данных, который либо соответствует заявленным условиям, либо нет и отбрасывается. И не понятно, как вы к этому хотите применить алгоритм Гровера.
Во первых хочу заметить, что задачей при майнинге является нахождение Nonce, а не хеша.
Алгоритм Гровера — это квантовый алгоритм, предназначенный для поиска в неструктурированной базе данных с элементов за операций, в отличие от классического подхода, который требует операций. В контексте майнинга блокчейна этот алгоритм потенциально может ускорить процесс нахождения подходящего Nonce, перебирая возможные значения быстрее, чем классический перебор.
Применение алгоритма Гровера к майнингу:
Формализация задачи поиска:
Найдём подходящее значение Nonce, такое что результат хэш-функции блока (с этим Nonce) будет удовлетворять заданным условиям сложности.
Квантовое представление:
Значения Nonce представляются в виде квантовых состояний и находятся в суперпозиции всех возможных значений Nonce. Например, если Nonce имеет 32-битные значения, это возможных состояний.
Функция оракула:
Оракул — это квантовый подпрограммный блок, который будет помечать состояния, удовлетворяющие заданному условию сложности. Другими словами, для каждого возможного значения Nonce вычисляется хэш блока, и если хэш удовлетворяет требованию сложности, квантовое состояние помечается.
Итерации алгоритма Гровера:
Основная идея алгоритма — это успешное применение оракула в сочетании с оператором амплитудного усиления. После нескольких итераций квантового компьютера вероятность того, что нужное состояние (правильное значение Nonce) будет измерено, становится высокой.
Пример:
Предположим, мы ищем правильное значение Nonce среди возможных вариантов:
Инициализируем квантовый регистр в состоянии суперпозиции, охватывающей все возможных значений.
Применяем оракул, который отмечает состояния, соответствующие правильным значениям Nonce.
Выполняем амплитудное усиление (диффузионное преобразование).
Повторяем шаги 2 и 3 примерно (приблизительно 65 536) раз.
Измерение квантового регистра найдет правильное значение Nonce с высокой вероятностью.
Ограничения
Так-же имеет смысл добавить про ограничения с которыми можно столкнутся. Моя ошибка, что не добавил это в статью.
- Квантовая инфраструктура: На данный момент, практическое применение квантовых вычислений ограничено доступностью и масштабируемостью квантовых компьютеров. Текущие квантовые устройства всё ещё находятся в состоянии исследований и разработки
- Шум и ошибки: Современные квантовые компьютеры подвержены шумам и ошибкам, что может существенно снизить их эффективность на практике.
- Сложность реализации оракула: Квантовый оракул для реальных хэш-функций (таких как SHA-256) будет довольно сложным в реализации.
Как я уже написал выше (в ответе на комментарий), это лишь гипотетически возможное влияние на бумаге. Как это все будет на практике мы увидем думаю не менее чем через 5 лет.
Ух ты! Вы комментарий нейросетью писали?
Спасибо, познавательно.
Вы ж нейронкой сгенерировали статью, да?
Не знал, что дружелюбно-деловая манера общения считается чем-то плохим. Тем более на хабре)
Я использовал ChatGPT 4 для написания примеров и проверки пунктуации в тексте. Все остальное было написано мной.
Это ведь не преступление?
На мой взгляд это как раз уместное применение ChatGPT. Но меня смущает пунктуация уже в самом первом предложении статьи. Нужна ли там запятая?
Хорошо ли ChatGPT с этим справляется?
Попросите нейросеть добавить в ответы немного пассивной агрессии и всё наладится :-)
А по теме, очевидные сложности в том, сколько кубитов потребуется и какой уровень ошибок будет и будет ли на самом деле прирост скорости. Вы же не дали никаких оценок, по этому ваша статья абсолютно бесполезно.
Это как рассуждать о появлении возможности воздухоплавания на баллонах с откаченным воздухом, когда появятся более прочные материалы и при этом на возражения, заставить нейросеть генерировать что-то вроде:
- промышленность осваивает новые технологии, которые позволяют сдавать все более и более прочные материалы
- успехи в математике и моделировании позволяют даже из старых материалов строить все более лёгкие и более прочные конструкции
А после сделать вывод, что эра воздухоплавание на полых твердых конструкциях с откаченным воздухом неизбежно наступит. Отсутсвие понимания веса каждого утверждения и связи с реальным миром как раз и выдаёт нейросетевой подход к написанию статьи, верней нейросетевого высасывания из пальца.
Это худшее применение llm из всех возможных.
Как квантовые компьютеры могут повлиять на майнинг криптовалюты
Никак. Сэкономил вам 5 минут, you're welcome!
Через 20 лет, когда появятся рабочие квантовые компьютеры, способные сделать что-то полезное, майнинг криптовалюты будет делом далекого прошлого.
Спасибо за ваш комментарий!
Уже сегодня появляются готовые квантовые компьютеры, и многие организации уже начинают готовиться к их активному использованию. Например, Национальный институт стандартов и технологий США (NIST) организовал конкурс по выбору квантово-устойчивых криптоалгоритмов. Это свидетельствует о необходимости подготовки к их появлению. Я не думаю, что они бы проводили такие мероприятия, если бы это было актуально только через ~20 лет.
На мой взгляд, квантовые компьютеры начнут широко использоваться через ~5 лет. Поначалу их будут использовать преимущественно ученые, но с постепенным масштабированием их производства их конечная стоимость станет подъемной для некоторых людей связанных с криптовалютой.
Действительно количество монет которые можно майнить ограничено и через те-же 5 лет, скорее всего токены Bitcoin'а уже будут получены. Но не факт, что не появятся другие валюты.
Так-же хочу заметить, что квантовые компьютеры не станут заменой стандартных полупроводников, они лишь станут дополнением (на мой взгляд).
На мой взгляд, квантовые компьютеры начнут широко использоваться через ~5 лет.
А что вам дает такую уверенность? Я вот как человек, непосредственно этим занимающийся, не вижу перспектив появления КК, который можно использовать для реальных задач, в ближайшее десятилетие.
Знаете, сколько вам понадобится физических кубитов для подсчета реального хэша? Можете посмотреть на роадмап IBM и прикинуть, насколько далеко это даже по их оптимистичным прогнозам.
Эффективность: Если классический подход требует, например, проверки возможных нонсов, алгоритм Гровера будет требовать операций.
Это подразумевает ускорение в раз.
классика нейронок) противоречие? не, не слышали)
до слова "Это" примеры показывают ускорение ровно х2, а потом резко ускорение становится 2^32
Так-же имеет смысл добавить про ограничения с которыми можно столкнутся.(что сделать, столкнутЬся)
Я использовал ChatGPT 4 для написания примеров и проверки пунктуации в тексте.
А грамматику ChatGPT 4 не проверяет?
возможность параллельно перебирать хеши вместо последовательного - никак не повлияет на майнинг от слова совсем.
вот и весь спойлер.
но ученым надо же куда-нибудь "вставить" квантовые самоделки, а то "квантовый прогресс" все идет-идет, да все никак никуда не придет. А между тем китаезы уже научились моделивать квантовые процессы на обычном х86-ПК, и даже оно дает ускорение вычислений. Вобщем, даже квантовая эмуляция без самих квантовых копухтеров способна. Вопрос скорее в применении методологии. Но и тут не обошлось без человеческого фактора. Кто-то (ученые) хочет познавать мир на новых уровнях и исследовать квантовые процессы, а кто-то (инвесторы) просто хотят "обчистить всех и каждого", главное найти подход.
Ну а биткоин? Биткоин не дает покоя тем, у кого его нет. Причем просто "купить и успокоиться" или "намайнить и успокоиться" - не наши методы. Надо же "захватить и доминировать", недостаточно просто иметь биткоины, надо иметь "все биткоины в мире"...
вобщем технологии еще нет, но зато ее "военное применение" уже стоит в очереди под номером 1.
Не волнуйтесь, задолго до появления квантовых компьютеров алгоритмы майнинга актуальных криптовалют обновятся, чтобы исключить преимущество. Сейчас такое происходит в шифровании. А если кто-то (?) неожиданно сейчас подключит квантовый компьютер майнинга биткоина - его преимущество будет действовать до пересчёта сложности, т.е. не более 2-х недель. И производство новых монет не точно не ускорит. Скорее ускорит переход к постквантовым алгоритмам.
Алгоритм гровера вообще довольно бесполезная штука, так как дает всего лишь квадратическое приимущество по сравнению с классическими компьютерами.
Казалось бы неплохо, но надо помнить, что во первых КК врятли когда-нибудь сравняются по производительности и цене с классическими процессорами, а во вторых алгоритм должен быть выполнен от начала до конца без ошибок, а с этим мягко говоря проблемы. Причем если какой-нибудь шор выполняется за приемлимое время, то гровер, для приложений где он в теории даст хоть какой-то выхлоп, все равно будет выполняться долго - а сбои недопустимы. И параллелятся квантовые вычисления в лучшем случае по классическим принципам, а в худшем - вообще никак. А еще, если классический алгоритм может угадать и с одной попытки, гровер должен выполняться всегда до конца, т.е. в случае майнинга, если ты гарантированно вычисляешь нужный nonce допустим за час - толку от этого нет, т.к. блок будет намайнен за 10 минут, и придется ресетать алгоритм и начинать сначала.
Кстати а применим ли вообще гровер к задачам, где нет одного решения, а множество решений рандомно распределено по диапозону возможный значений? Какое из них он должен найти?
Как квантовые компьютеры могут повлиять на майнинг криптовалюты