Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 45
Достопочтенный сэр, почему только в теории-то?
Скучновато без примера кода. Возведение в 17 степень, путем возведения x в 16 степень встроенной процедурой возведения в квадрат, а потом перемножением x и x^16:
o4_POW17 :: QIntTF -> Circ (QIntTF,QIntTF)
o4_POW17 = box "o4" $ \x -> do
comment_with_label "ENTER: o4_POW17" x "x"
(x, x17) <- with_computed_fun x
(\x -> do
(x,x2) <- square x
(x2,x4) <- square x2
(x4,x8) <- square x4
(x8,x16) <- square x8
return (x,x2,x4,x8,x16))
(\(x,x2,x4,x8,x16) -> do
(x,x16,x17) <- o8_MUL x x16
return ((x,x2,x4,x8,x16),x17))
comment_with_label "EXIT: o4_POW17" (x,x17) ("x","x17")
return (x, x17)
Нет, квантовые эффекты распространяются только на посылки, пересылаемые Почтой России.
— О боже, что произошло, как такое вообще могло случиться?
— Кто-то случайно посмотрел на посылку в процессе доставки… и она схлопнулась.
Ух, на ваше сообщение ответить вряд ли смогу также эффектно. Хотел про единственный экземпляр доказательства, подтверждающее моё высказывание, которое писалось много лет и было отправлено почтой в единичном экземпляре с последующей утерей — но как-то боянисто и тупо. Сдаюсь.
… компьютера D-Wave, который критики не считают полноценным квантовым компьютером из-за его узкой специализации.
Тем не менее D-Wave прошел валидацию как квантовый компьютер. По этому поводу даже написана статья в Nature Communication.
D-Wave — вычислительное устройство, реализующее алгоритм оптимизации отжигом — больше ничего (хотя я меньше всех склонен считать, что этого мало). В статье, на которую вы сослались, мне кажется, об этом и написано — «мы признаём, что этот процессор работает на квантовых эффектах и реализует процедуру оптимизации квантовым отжигом». Это очень далеко от «компьютера» по Тьюрингу, и эта штука действительно не может запустить ни алгоритм Гровера, ни алгоритм Шора, ни большинство из тех 45 принципиально квантовых алгоритмов — и уж точно даже в теории не скомпилирует произвольную программу на QCL или Quipper. Зато идеально подходит для задач машинного обучения, так что две установки в Гугле, думаю, только начало.
Одно из самых ожидаемых применений — алгоритм факторизации числа на квантовом компьютере. Если он заработает (интересно, работает ли он на D-Wave), то это поставит под угрозу все текущие алгоритмы шифрования, основанные на сложности разложения числа на множители (RSA к примеру)
Никогда не понимал, что такого ожидаемого в возможности сломать всю криптографию — забавно, конечно, но практическая ценность какая? Устойчивые к этому алгоритмы шифрования, кстати, давно разработаны — внедрят, как только припечёт, да и всё.
D-Wave этого не умеет, но то, что он умеет, мне кажется намного более интересным — он умеет решать задачу оптимизации, а к ней сводится просто невероятное число задач, с которыми мы все сталкиваемся каждый день, и которые решаются всё ещё плохо — распознавание образов, поиск, логистика — это только цветочки, которые на слуху.
D-Wave этого не умеет, но то, что он умеет, мне кажется намного более интересным — он умеет решать задачу оптимизации, а к ней сводится просто невероятное число задач, с которыми мы все сталкиваемся каждый день, и которые решаются всё ещё плохо — распознавание образов, поиск, логистика — это только цветочки, которые на слуху.
сломать всю криптографию — забавно, конечно, но практическая ценность какая?
Для военных и хакеров очень даже высокая практическая ценность :)
Устойчивые к этому алгоритмы шифрования, кстати, давно разработаны — внедрят, как только припечёт, да и всё.
Основная мысль в том, что сейчас практически вся инфраструктура шифрования построена на простых числах. И замена на другие алгоритмы крайне сложна и дорога (SSL-сертификаты, цифровые подписи, хардварные брелки для доступа, GSM и т.д. — все это разом не поменяешь). Потому я и написал про «Одно из самых ожидаемых применений».
Не то чтобы все этого хотят, скорее ожидают, что если полноценный квантовый компьютер будет создан, то у инфраструктуры шифрования появятся серьезные проблемы.
А так да — эффективное решение задач оптимизации очень интересно.
Насколько я помню, наши крайние ГОСТы по шифрованию и ЭП используют алгоритмы на эллиптических кривых. Они тоже поддаются взлому с квантом?
Я не слышал про алгоритм атаки на эллиптические кривые (в отличие от алгоритма факторизации Шора), но мне кажется ГОСТ тоже под угрозой.
Атака на ECC реализуется практически тем же алгоритмом Шора.
http://logic.pdmi.ras.ru/~sergey/teaching/crypto10/12-quantum.pdf
arxiv.org/abs/quantph/0301141 «A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits»
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/l03.pdf
http://logic.pdmi.ras.ru/~sergey/teaching/crypto10/12-quantum.pdf
В результате получается квантовое решение задачи дискретного логарифма. Эллиптические кривые не спасают — для любой коммутативной группы работает, нужно только умножать уметь.
Мы взломали всю коммутативную криптографию. Что делать? Один ответ — строить квантовую криптографию. Другой ответ — строить некоммутативную криптографию.
arxiv.org/abs/quantph/0301141 «A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits»
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/l03.pdf
It is straightforward to use Shor’s algorithm to solve the discrete log problem for an elliptic curve… Ironically, Shor’s algorithm takes a comparable number of steps for both factoring and discrete log (regardless of the group involved), with the caveat that group operations on an elliptic curve take more time to calculate than ordinary multiplication of integers.
Шифрование на эллиптических кривых основано на трудности дискретного логарифмирования. Тот самый Шор показал, что существует эффективный квантовый алгоритм для дискретного логарифирования, так что шифрование на эллиптических кривых взламывается точно так же.
Кстати, в списке 45 запрограммированных квантовых алгоритмов этот вопрос идет сразу вторым пунктом )
Кстати, в списке 45 запрограммированных квантовых алгоритмов этот вопрос идет сразу вторым пунктом )
SSL на всех системах старше WinXP уже умеет ECC. Думаю, если сильно потребуется, смогут быстро ввести технологию вроде SGC для дорогих сертификатов.
Прочитают все, что уже было передано до внедрения новых алгоритмов.
Хм, а кто-то знает, что Google делает с D-Wave?
Quantum Computing Artificial Intelligence Lab, что бы это ни значило.
"… Quantum Artificial Intelligence Lab to find ways to make computers much smarter ..." — по-видимому цели создать полнофункциональный ИИ, который бы мог решать Любую Произвольную задачу, перед этой лабораторией не стоит. Во всяком случае она стоит не на первом месте, т.к. формулировка: «Computers much smarter», не предполагает качественных скачков. Однако ж, не стоит забывать, что это всего-лишь статья и смысл создания этой лаборатории знают только, видимо, в самом гугле…
Несомненно, только в гугле =)
Тем не менее, стоит заметить, что термин AI специалисты всё же часто используют в куда более прикладном смысле — как расширенная дисциплина машинного обучения, в которой не зазорна всякая экзотика и эвристика типа роевых алгоритмов, фракталов, теории хаоса, резервуарных вычислений, нечёткой логики и т. д. и т. п. — уверен, Гуглу это давно и плотно интересно. В академических кругах это всё чаще предпочитают называть Computational Intelligence, для разделения с «философским» понятием ИИ — но для названия лабы это звучит, наверное, недостаточно круто.
Тем не менее, стоит заметить, что термин AI специалисты всё же часто используют в куда более прикладном смысле — как расширенная дисциплина машинного обучения, в которой не зазорна всякая экзотика и эвристика типа роевых алгоритмов, фракталов, теории хаоса, резервуарных вычислений, нечёткой логики и т. д. и т. п. — уверен, Гуглу это давно и плотно интересно. В академических кругах это всё чаще предпочитают называть Computational Intelligence, для разделения с «философским» понятием ИИ — но для названия лабы это звучит, наверное, недостаточно круто.
То есть вместо Глэдос и Скайнет у нас будет Кукай?
«Разработчики Quipper призывают закодировать все известные алгоритмы на новом ЯП, сами они для проверки реализовали семь нетривиальных квантовых алгоритмов из литературы:… » — вот бы кто объяснил мне, глупому — что эти алгоритмы значат, в картинках и с примерами. =)
Вопрос: правильно ли я понимаю, что возможности квантовых компьютеров эквивалентны машине Тьюринга с точки зрения принципиальной вычислимости (не скорости!)?
Имхо, вполне правильно. Эволюция квантовой системы происходит детерминированным образом согласно уравнениям КМ (опровергнуть их пока никому не удалось, хотя и есть вопросы совместимости с ТО, например). Вопрос измерения итогового состояния (редукции) опускаем, пока нет консенсуса относительно интерпретации этой редукции — будем обходиться вероятностной, она тоже (как и уравнения КМ) может быть просчитана на классическом компе.
Так что все что нам насчитает квантовый комп (т.е. эволюция его квантового состояния) — все это может быть посчитано и на обычном компе, но (особенно для специфических квантовых алгоритмов) — гораздо медленнее.
Так что все что нам насчитает квантовый комп (т.е. эволюция его квантового состояния) — все это может быть посчитано и на обычном компе, но (особенно для специфических квантовых алгоритмов) — гораздо медленнее.
Да, BQP содержится в PSPACE, а PSPACE это машина Тьюринга с полиномиальным ограничением по памяти
Множество ЭГ-вычислимых функций совпадает с множеством рекурсивных функций, а также с множеством машин Тьюринга (тезис Черча). Так что если алгоритм в принципе возможно посчитать, то этот компьютер её посчитает. Квантовый компьютер не менее мощный, чем машина Тьюринга, у него просто способность решать не за линейное время, а за логарифм, что обеспечивает экспоненциальный рост быстродействия. Но на формальную вычислимость это не оказывает инкакого результата
Я правильно понимаю, что введение в строй квантовых компьютеров будет новой «Проблемой 2000», причём гораздо страшнее?
Скорее всего сведётся к еще одному расширению в компах — квантовый сопроцессор. Для специальных задач, чтобы вода стала более водная в новых игрушках.
Жду ответа от Nemerle. Эти черти своим ФП с метаподходом «покрыли уже всё стадо», кроме, пожалуй, только программирования по квантовым алгоритмам. И судя по тому, как у них красиво и классно получается до сих пор (если объективно оценивать), я не удивлюсь.
Интересно, вот американские военные столько классных штук для гражданского использования делают — а что из советских военных разработок сейчас используется гражданским населением?..
ну как, форма или ее елементы, противогазы, костюмы химзащиты, иногда автоматы калашникова :)
Ну на вскидку:
* всякие ЗИЛы-КАМАЗы изначально разрабатывались для перевозки по болотам военных грузов;
* АЭС — это заводы для производства оружейного плутония, энергия там побочный продукт реакции, который нужно отводить;
* «гражданский космос» (спутники связи, глонасс и пр.) — разрабатывали средства наведения и доставки плутония из предыдущего пункта на место применения;
* криптография по госту — изначально применялась для шифрования военной связи, сейчас используется для ЭЦП, например
Но, конечно, процент использования военных патентов в гражданской сфере у нас на порядки ниже, чем в США из-за организационных моментов (у нас военку двигают фгупы под грифом секретности, у них коммерческие фирмы, заинтересованные в повторном использовании результатов разработок).
* всякие ЗИЛы-КАМАЗы изначально разрабатывались для перевозки по болотам военных грузов;
* АЭС — это заводы для производства оружейного плутония, энергия там побочный продукт реакции, который нужно отводить;
* «гражданский космос» (спутники связи, глонасс и пр.) — разрабатывали средства наведения и доставки плутония из предыдущего пункта на место применения;
* криптография по госту — изначально применялась для шифрования военной связи, сейчас используется для ЭЦП, например
Но, конечно, процент использования военных патентов в гражданской сфере у нас на порядки ниже, чем в США из-за организационных моментов (у нас военку двигают фгупы под грифом секретности, у них коммерческие фирмы, заинтересованные в повторном использовании результатов разработок).
не ожидал что будет столько комментариев, спасибо всем, выучил несколько умных слов
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Первый высокоуровневый язык программирования для квантовых компьютеров