Первый высокоуровневый язык программирования для квантовых компьютеров

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

    Группа американских учёных, получив финансирование от исследовательского центра Национальной разведки США (IARPA) разработала высокоуровневый язык программирования Quipper. Он создан на основе Haskell и лучше подходит для реализации квантовых алгоритмов, чем QCL (основан на C).

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

    Разработчики Quipper призывают закодировать все известные алгоритмы на новом ЯП, сами они для проверки реализовали семь нетривиальных квантовых алгоритмов из литературы:

    • Бинарное спаянное дерево (Binary Welded Tree, BWT), arXiv:quant-ph/0209131. Поиск обозначенного узла в графе.
    • Булева формула (Boolean Formula, BF), arXiv:0704.3628 и arXiv:quant-ph/0703015, любая формула AND-OR размера N может быть вычислена за время n1/2+o(1) на квантовом компьютере. Реализована версия, которая вычисляет выигрышную стратегию в настольной игре гекс.
    • Порядок класса (Class Number, CL), Proceedings of the 34th ACM Symposium on Theory of Computing, 2002. Квантовый алгоритм для вычисления уравнения Пелля и главного идеала за полиномиальное время.
    • Оценка основного состояния квантово-механической системы (Ground State Estimation, GSE), Molecular Physics, 109(5):735–750, 2011. Вычисление энергетических уровней для конкретной молекулы.
    • Квантовые линейные системы (Quantum Linear Systems, QLS), arXiv:0811.3171. Решение линейной системы уравнений.
    • Кратчайший уникальный вектор (Unique Shortest Vector, USV), arXiv:cs/0304005. Поиск кратчайшего вектора среди имеющихся вариантов.
    • Поиск треугольника (Triangle Finding, TF), arXiv:quant-ph/0310134. Поиск треугольников в насыщенном графе.

    Список алгоритмов определило агентство IARPA, в контексте программы IARPA Quantum Computer Science.

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

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


    Компьютер D-Wave

    Quipper подходит для программирования теоретических квантовых компьютеров нескольких архитектур (реализация кубитов в фотонах, электронах и т.д.), но не подходит для программирования действующего «квантового» компьютера D-Wave, который критики не считают полноценным квантовым компьютером из-за его узкой специализации. Что, впрочем, не помешало компании Google недавно купить два компьютера D-Wave с процессорами по 512 кубитов за $15 млн.

    [New Scientist]

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 45

      +5
      Достопочтенный сэр, почему только в теории-то?
        +19
        Скучновато без примера кода. Возведение в 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)
        

          +5
          А зачем x2, x4 и x8 прокидываются через весь код?
            +12
            От мусора не так-то просто избавляться. Квантовый процесс (описываемый уравнением Шредингера) обратим, поэтому чтобы что-то забыть, нужно выйти за рамки процесса, а это связано с диссипацией энергии и чревато декогерентностью системы.
      • UFO just landed and posted this here
          +16
          Нет, квантовые эффекты распространяются только на посылки, пересылаемые Почтой России.
          • UFO just landed and posted this here
              +1
              — О боже, что произошло, как такое вообще могло случиться?
              — Кто-то случайно посмотрел на посылку в процессе доставки… и она схлопнулась.
                0
                … коллапсировала:)
                +2
                Ух, на ваше сообщение ответить вряд ли смогу также эффектно. Хотел про единственный экземпляр доказательства, подтверждающее моё высказывание, которое писалось много лет и было отправлено почтой в единичном экземпляре с последующей утерей — но как-то боянисто и тупо. Сдаюсь.
            +3
            … компьютера D-Wave, который критики не считают полноценным квантовым компьютером из-за его узкой специализации.

            Тем не менее D-Wave прошел валидацию как квантовый компьютер. По этому поводу даже написана статья в Nature Communication.
              +7
              D-Wave — вычислительное устройство, реализующее алгоритм оптимизации отжигом — больше ничего (хотя я меньше всех склонен считать, что этого мало). В статье, на которую вы сослались, мне кажется, об этом и написано — «мы признаём, что этот процессор работает на квантовых эффектах и реализует процедуру оптимизации квантовым отжигом». Это очень далеко от «компьютера» по Тьюрингу, и эта штука действительно не может запустить ни алгоритм Гровера, ни алгоритм Шора, ни большинство из тех 45 принципиально квантовых алгоритмов — и уж точно даже в теории не скомпилирует произвольную программу на QCL или Quipper. Зато идеально подходит для задач машинного обучения, так что две установки в Гугле, думаю, только начало.
              +3
              Одно из самых ожидаемых применений — алгоритм факторизации числа на квантовом компьютере. Если он заработает (интересно, работает ли он на D-Wave), то это поставит под угрозу все текущие алгоритмы шифрования, основанные на сложности разложения числа на множители (RSA к примеру)
                +4
                Никогда не понимал, что такого ожидаемого в возможности сломать всю криптографию — забавно, конечно, но практическая ценность какая? Устойчивые к этому алгоритмы шифрования, кстати, давно разработаны — внедрят, как только припечёт, да и всё.

                D-Wave этого не умеет, но то, что он умеет, мне кажется намного более интересным — он умеет решать задачу оптимизации, а к ней сводится просто невероятное число задач, с которыми мы все сталкиваемся каждый день, и которые решаются всё ещё плохо — распознавание образов, поиск, логистика — это только цветочки, которые на слуху.
                  +4
                  сломать всю криптографию — забавно, конечно, но практическая ценность какая?

                  Для военных и хакеров очень даже высокая практическая ценность :)

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

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

                  А так да — эффективное решение задач оптимизации очень интересно.
                    0
                    Насколько я помню, наши крайние ГОСТы по шифрованию и ЭП используют алгоритмы на эллиптических кривых. Они тоже поддаются взлому с квантом?
                      +1
                      Я не слышал про алгоритм атаки на эллиптические кривые (в отличие от алгоритма факторизации Шора), но мне кажется ГОСТ тоже под угрозой.
                        +3
                        Атака на 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
                        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.
                        +4
                        Шифрование на эллиптических кривых основано на трудности дискретного логарифмирования. Тот самый Шор показал, что существует эффективный квантовый алгоритм для дискретного логарифирования, так что шифрование на эллиптических кривых взламывается точно так же.

                        Кстати, в списке 45 запрограммированных квантовых алгоритмов этот вопрос идет сразу вторым пунктом )
                        –1
                        SSL на всех системах старше WinXP уже умеет ECC. Думаю, если сильно потребуется, смогут быстро ввести технологию вроде SGC для дорогих сертификатов.
                        +1
                        Прочитают все, что уже было передано до внедрения новых алгоритмов.
                          0
                          Нет, если стороны использовали алгоритмы с PFS — например, получение симметричного сессионного ключа для AES при помощи DH поверх RSA.
                      +4
                      Хм, а кто-то знает, что Google делает с D-Wave?
                        +5
                        Quantum Computing Artificial Intelligence Lab, что бы это ни значило.
                          0
                          "… Quantum Artificial Intelligence Lab to find ways to make computers much smarter ..." — по-видимому цели создать полнофункциональный ИИ, который бы мог решать Любую Произвольную задачу, перед этой лабораторией не стоит. Во всяком случае она стоит не на первом месте, т.к. формулировка: «Computers much smarter», не предполагает качественных скачков. Однако ж, не стоит забывать, что это всего-лишь статья и смысл создания этой лаборатории знают только, видимо, в самом гугле…
                            +1
                            Несомненно, только в гугле =)
                            Тем не менее, стоит заметить, что термин AI специалисты всё же часто используют в куда более прикладном смысле — как расширенная дисциплина машинного обучения, в которой не зазорна всякая экзотика и эвристика типа роевых алгоритмов, фракталов, теории хаоса, резервуарных вычислений, нечёткой логики и т. д. и т. п. — уверен, Гуглу это давно и плотно интересно. В академических кругах это всё чаще предпочитают называть Computational Intelligence, для разделения с «философским» понятием ИИ — но для названия лабы это звучит, наверное, недостаточно круто.
                            0
                            То есть вместо Глэдос и Скайнет у нас будет Кукай?
                              0
                              Пролетая над гнездом?
                          +4
                          «Разработчики Quipper призывают закодировать все известные алгоритмы на новом ЯП, сами они для проверки реализовали семь нетривиальных квантовых алгоритмов из литературы:… » — вот бы кто объяснил мне, глупому — что эти алгоритмы значат, в картинках и с примерами. =)
                            +2
                            Вопрос: правильно ли я понимаю, что возможности квантовых компьютеров эквивалентны машине Тьюринга с точки зрения принципиальной вычислимости (не скорости!)?
                              +3
                              Имхо, вполне правильно. Эволюция квантовой системы происходит детерминированным образом согласно уравнениям КМ (опровергнуть их пока никому не удалось, хотя и есть вопросы совместимости с ТО, например). Вопрос измерения итогового состояния (редукции) опускаем, пока нет консенсуса относительно интерпретации этой редукции — будем обходиться вероятностной, она тоже (как и уравнения КМ) может быть просчитана на классическом компе.

                              Так что все что нам насчитает квантовый комп (т.е. эволюция его квантового состояния) — все это может быть посчитано и на обычном компе, но (особенно для специфических квантовых алгоритмов) — гораздо медленнее.
                              • UFO just landed and posted this here
                                  +1
                                  Да, BQP содержится в PSPACE, а PSPACE это машина Тьюринга с полиномиальным ограничением по памяти
                                  +4
                                  Множество ЭГ-вычислимых функций совпадает с множеством рекурсивных функций, а также с множеством машин Тьюринга (тезис Черча). Так что если алгоритм в принципе возможно посчитать, то этот компьютер её посчитает. Квантовый компьютер не менее мощный, чем машина Тьюринга, у него просто способность решать не за линейное время, а за логарифм, что обеспечивает экспоненциальный рост быстродействия. Но на формальную вычислимость это не оказывает инкакого результата
                                    0
                                    Я правильно понимаю, что введение в строй квантовых компьютеров будет новой «Проблемой 2000», причём гораздо страшнее?
                                      0
                                      Когда идёт обсуждение квантовых компьютеров и эффектов от его внедрения, мне сразу вспоминается 2000 и ещё запуск БАК. Мандраж людей в обоих случаях был схож.
                                        0
                                        Вот я и спрашиваю, насколько проблема реальна.
                                      +11
                                      Скорее всего сведётся к еще одному расширению в компах — квантовый сопроцессор. Для специальных задач, чтобы вода стала более водная в новых игрушках.
                                        +2
                                        … и к этому сопроцессору — система охлаждения на жидком гелии, размером с трехстворчатый шкаф.
                                        0
                                        Жду ответа от Nemerle. Эти черти своим ФП с метаподходом «покрыли уже всё стадо», кроме, пожалуй, только программирования по квантовым алгоритмам. И судя по тому, как у них красиво и классно получается до сих пор (если объективно оценивать), я не удивлюсь.
                                          +1
                                          Интересно, вот американские военные столько классных штук для гражданского использования делают — а что из советских военных разработок сейчас используется гражданским населением?..
                                            +4
                                            ну как, форма или ее елементы, противогазы, костюмы химзащиты, иногда автоматы калашникова :)
                                              +2
                                              Ну на вскидку:
                                              * всякие ЗИЛы-КАМАЗы изначально разрабатывались для перевозки по болотам военных грузов;
                                              * АЭС — это заводы для производства оружейного плутония, энергия там побочный продукт реакции, который нужно отводить;
                                              * «гражданский космос» (спутники связи, глонасс и пр.) — разрабатывали средства наведения и доставки плутония из предыдущего пункта на место применения;
                                              * криптография по госту — изначально применялась для шифрования военной связи, сейчас используется для ЭЦП, например
                                              Но, конечно, процент использования военных патентов в гражданской сфере у нас на порядки ниже, чем в США из-за организационных моментов (у нас военку двигают фгупы под грифом секретности, у них коммерческие фирмы, заинтересованные в повторном использовании результатов разработок).
                                              0
                                              не ожидал что будет столько комментариев, спасибо всем, выучил несколько умных слов

                                              Only users with full accounts can post comments. Log in, please.