company_banner

Квантовый компьютер: взлом любого шифра, кубиты и крайне низкие температуры



    Теоретически квантовые компьютеры будут способны быстро решать задачи, на которые у суперкомпьютеров уходили бы тысячи лет. Эта технология может изменить привычный нам мир. Популярно о квантовых компьютерах рассказывает Евгений Глушко в очередном выпуске на канале наших друзей Sci-One TV. Текстовую версию — как и всегда — читайте под катом.



    Обычному пользователю квантовый компьютер ещё долго будет не нужен, может быть даже никогда. Но с его помощью уже сегодня можно поставить на колени всё и всех, кто зависит от интернета: например, мировые банки и любые современные финансовые системы. Ну или просто можно узнать всё, что от вас пытаются скрыть другие люди.

    В 90-х годах прошлого века американский математик Питер Шор придумал квантовый алгоритм, который способен очень быстро разложить большущее число на два простых сомножителя. Казалось бы, кому это вообще надо? К сожалению, обычные компьютеры (как и суперкомпьютеры) справляются с этой задачей из рук вон плохо. Т.е. разложить число 15 в произведение 3*5 они могут, а вот если в числе 100 или 1000 знаков, то уже не очень. Чисто технически они могут это сделать — просто переберут все комбинации, но на это уйдёт не один миллион лет. И эту слабость классических компьютеров используют современные криптографические алгоритмы. На сегодняшний день практически вся ценная информация, которая передаётся через интернет, зашифрована с таким расчётом. Это и банковские транзакции, и секретные переговоры, и даже ваша переписка в социальных сетях. Расшифровать всё это с помощью классических компьютеров практически нереально. Теперь представьте, что кто-то вдруг создал квантовый компьютер и запустил на нём алгоритм Шора. И тогда любая зашифрованная в мире информация станет для него доступна.



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

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



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

    Кстати, кубиты были одной из любимых тем Фейнмана! В 1980-х годах он предложил использовать существующие в природе квантовые системы с двумя состояниями (двухуровневые системы), чтобы симулировать сложные для классических компьютеров задачи. Правда, сам он не знал слово «кубит» — оно было придумано чуть позже Стивеном Визнером. А кубит Визнер придумал для обозначения квантовых денег.

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

    Сверхпроводящий кубит — это просто кольцо из сверхпроводника (металла, по которому электрический ток может течь без потерь). Но можно заметить и несколько особенностей. Они называются джозефсоновскими переходами и представляют собой два кусочка сверхпроводника, разделенных тонкой прослойкой изолятора. Пары электронов могут без проблем проникать через эту прослойку благодаря квантовому туннелированию. Благодаря джозефсоновским переходам мы можем управлять энергетическими уровнями в наших кубитах, подстраивая их необходимым образом. К примеру, когда ток в кольце течёт по часовой стрелке, кубит находится в состоянии 0, а когда против часовой — в состоянии 1. Но и это всё в теории. Как же практически создать такие структуры? Здесь на помощь приходит электронная литография — рисование пучком электронов по чувствительной поверхности. Таким способом можно создавать невероятно маленькие структуры размером вплоть до 10 нанометров!

    Когда нужная структура нарисована, на поверхность чипа напыляется металл (например, алюминий). И сверхпроводящий кубит готов! Потом его нужно измерить. Для этого мы помещаем чип в большой криостат. Это тот же холодильник, только очень дорогой и работающий на смеси жидкого гелия. Он позволяет получать крайне низкие температуры — вплоть до одной сотой градуса выше абсолютного нуля! Это в сто раз холоднее, чем в самом холодном месте во Вселенной! Зачем нужны такие низкие температуры? Во-первых, чтобы сверхпроводники, из которых сделан наш чип, начали сверхпроводить — чтобы электроны объединились в пары и стали двигаться согласованно и без потерь энергии. Во-вторых, чтобы максимально изолировать нашу хрупкую квантовую систему от внешнего мира. В первую очередь — от теплового шума — злейшего врага любой «квантовости».

    Собственно, это одна из проблем, из-за которой до сих пор не удалось создать настоящий полноценный квантовый компьютер. Вы, наверное, слышали, что компания IBM объявила о наступившей эре квантовых компьютеров и даже дала всем желающим доступ к одному такому через интернет. Но это пока больше реклама, хотя и основанная на серьёзной научной работе. Правда в том, что инженеры IBM собрали процессор всего из 5 кубитов, на котором ничего серьёзного запустить нельзя (для этого их нужно несколько сотен). Хрупкость кубитов мешает нам вступить в новую эру. А когда их соединяют вместе, время жизни кубитов стремительно уменьшается.



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

    Любители компьютерных игр наверняка спросят: и столько сил ради компьютера, на котором даже Доту или Майнкрафт не запустить? Про шифрование я уже говорил. Но важно и другое. Создав квантовый компьютер, мы сможем выиграть в скорости решения пусть всего нескольких, но крайне важных для современной цивилизации видов задач:

    • быстрый поиск по гигантским базам данных (а их становится всё больше);
    • оптимизация грузоперевозок (задача коммивояжёра);
    • ускорение и удешевление поиска новых лекарств и материалов, например, высокотемпературных сверхпроводников.

    Но впереди ещё много работы. Да пребудет с вами наука!

    Полезные ссылки:

    makeitquantum.ru — для дальнейшего чтения по теме.
    vk.com/makeitquantum — свежие квантовые новости.
    mipt.ru/science/labs/artificial_quantum_systems_lab — лаборатория Искусственных квантовых систем.
    Mail.Ru Group 231,10
    Строим Интернет
    Поделиться публикацией
    Комментарии 104
    • +7
      «если в числе 100 или 1000 знаков, то уже не очень.» — не совсем верно. Число в 100 цифр факторизуется за разумное время.
      «Чисто технически они могут это сделать — просто переберут все комбинации, но на это уйдёт не один миллион лет.» — давно уже не так. Алгоритмы, более оптимальные чем полный перебор есть. В частности NFS-алгоритмы.
      «И тогда любая зашифрованная в мире информация станет для него доступна. » — в общем-то нет. Если кто-то сможет факторизовывать любые числа за разумное время, это не значит, что он вскроет любой шифр.
      • +3
        Да, обычно упоминают эллиптические кривые, которые, вроде как, не подвержены уязвимости.

        «они могут находиться в любом из состояний между нулем и единичкой»
        Ну вот не так. Это что, выходит, вместо типа int у нас бит типа float? И как это поможет факторизовать? Зачем вводить неокрепшие умы в заблуждение?
        • +1

          Эллиптические кривые и задача дискретного логарифмирования ломаются практически тем же самым алгоритмом Шора: http://logic.pdmi.ras.ru/~sergey/teaching/crypto10/12-quantum.pdf "Алгоритм Шора" — Сергей Николенко, Криптография — АФТУ РАН, 2010


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

          Мы взломали всю коммутативную криптографию. Что делать? Один ответ — строить квантовую криптографию. Другой ответ — строить некоммутативную криптографию.

          Неясно как ломать (не найдены подходящие алгоритмы) асимметричные криптосистемы из группы т.н. постквантовой криптографии, например на решётках (NTRU).


          Перебор ключей для симметричных алгоритмов на квантовых компьютерах в теории ускоряется (алгоритм Гровера), но не так эффективно как взлом асимметричных. Гровер снижает сложность ряда атак лишь квадратично, и для защиты от него достаточно увеличить длину ключей в 2 раза:


          Grover's algorithm could brute force a 128-bit symmetric cryptographic key in roughly 2^64 iterations, or a 256-bit key in roughly 2^128 iterations.

          АНБ не так давно обновляло рекомендации по алгоритмам: https://geektimes.ru/post/260684/
          https://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml


          … we announce preliminary plans for transitioning to quantum resistant algorithms.… Additionally, IAD customers using layered commercial solutions to protect classified national security information with a long intelligence life should begin implementing a layer of quantum resistant protection. Such protection may be implemented today through the use of large symmetric keys and specific secure protocol standards.

          AES… Use 256 bit keys; ECDH… Use Curve P-384; ECDSA… Curve P-384; SHA… Use SHA-384; DH… Minimum 3072-bit modulus; RSA… Minimum 3072 bit-modulus

          http://csrc.nist.gov/groups/SMA/ispab/documents/minutes/2015-10/oct21_stanger_final_approved_nsa.pdf "Quantum Resistant Algorithms": "Cryptography Tomorrow Suite… Public Key TBD; Symmetric AES 256; Hash SHA-384"


          https://cryptome.org/2016/01/CNSA-Suite-and-Quantum-Computing-FAQ.pdf "Commercial National Security Algorithm Suite and Quantum Computing FAQ", 2016: "The AES-256 and SHA-384 algorithms are symmetric, and believed to be safe from attack by a large quantum computer.… In the area of public key algorithms the future is less clear. One area of general agreement appears to be that the key sizes for these algorithms will be much larger than those used in current algorithms"


          https://eprint.iacr.org/2015/1018.pdf "A RIDDLE WRAPPED IN AN ENIGMA" — NEAL KOBLITZ AND ALFRED J. MENEZES


          5.4. The NSA believes that RSA-3072 is much more quantum resistant than ECC-256 and even ECC-384. The quantum complexity of integer factorization or discrete logarithm essentially depends only on the bit length of the group order. Thus, there could be a big lag between the time when quantum computers can solve the ECDLP on P-256 and even P-384 and the time when they can factor a 3072-bit integer. However, it will require major advances in physics and engineering before quantum computing can scale significantly. When that happens, of course P-256 and P-384 will fall first. But, as the head of cybersecurity research at a major corporation put it, “after that it’s just a matter of money” before RSA-3072 is broken. At the point when P-384 is broken it would be unwise to use either ECC or RSA. It is not likely that the gap between quantum cryptanalysis of a 384-bit key and a 3072-bit key will be great enough to serve as a basis for a cryptographic strategy
        • +4
          Статья полна фраз, которые следует зачеркивать и писать рядом «на самом деле нет»
          • 0
            Да я дальше даже читать не стал… Факторизация и криптография мне хорошо знакомы, вот и отметил «вкусное».
            • +2
              Если дальше читать не стали, много ещё более «вкусного» могли пропустить. Там в самом конце написано, что квантовый компьютер может решить задачу коммивояжера. Я не настолько спец по криптографии, чтобы дискутировать, какие шифры он бы в этом случае мог ещё ломать (тем более что в зависимости от формулировки эта задача может принадлежать двум разным классам сложности), но по ходу чтения возникло впечатление, что автор придерживается ещё более смелой гипотезы о том, что квантовый компьютер вообще может решать переборные задачи вот так сразу (ну или хотя бы за логарифмическое время) из-за своего квантового параллелизма.
              Да, а ещё термин «кубит» ввёл Бен Шумахер, а не Визнер, а Визнер придумал квантовые деньги до того как Фейнман придумал квантовый компьютер, а не чуть позже и т.д.
        • 0
          Я наверное тупой, но сколько не размышлял, так и не смог понять идею с котом Шрёдингера.
          • +3
            Идея как раз в том, что нельзя переносить законы квантовой механики в макромир.
            • +1
              А Шредингер-то хотел этим примером показать, что в квантовой теории что-то не так.
              • +1
                «которым он хотел показать неполноту квантовой механики при переходе от субатомных систем к макроскопическим.»
            • 0
              тоже не очень понимаю. Там вроде атом цезия с известным периодом полураспада. То есть состояние кота зависит от времени. Как только закрыли кота, велика вероятность, что он еще жив, и наоборот, через много времени вероятность что мертв больше. Или что-то не понимаю?*
              • +3
                Период полураспада хорошо работает с огромной кучей атомов, а единственный атом может существовать ну оочень долго и никто не может определить, когда он распадётся.

                Вроде, так.
                • 0
                  Да, точно!
                  • –8
                    Просто ещё не научились определять, когда же он распадётся.
                    Вообще вся современная физика — костыль на костыле.
                    • 0
                      Предложите что-то получше.
                      • –4
                        О, у кого-то бомбануло.
                        Это просто констатация факта.
                        Я — программист, а не физик. Так что с этой проблемой разберутся физики через пару десятков лет сами.)
                        • +1
                          Физическая модель позволяет построить закон распределения для времени распада, который соотносится с реальными данными. Из чего и следует невозможность точного определения времени распада. Период полураспада — срок времени, который даёт вероятность распада 1/2 и является статистической характеристикой.
                          • 0
                            Ну вообще, если говорить формально — принцип скрытых локальных переменных определяющих распад ядра (или нейтрона, если упростить задачу) кажется достаточно чудным (и я бы сказал — не очень ложащимся в дух существующей квантовой теории), но я не в курсе чтобы существовал какой либо эксперимент, позволяющий их исключить, что уж говорить о скрытых нелокальных переменных.
                            Физические модели не говорят о том, является ли процесс распада истинно случайным (два абсолютно идентичных ядра не факт что распдутся одновременно) или завязан на локальных параметрах (например в момент образования ядра происходят процессы, определяющие значение скрытого параметра, который ответственнен за точное время распада).
                            • –1
                              FYI Неравенства Белла давно продемонстрированы экспериментально, так что про локальных, конечно, нет.
                              • 0
                                Я вот думал при написании — стоит ли пояснить про неравенство Белла, ведь найдется же уникум который увидит два слова и вставит не к месту.
                                Нашелся.

                                Неравенство Белла показывает отсутствие скрытых локальных переменных для квантовой запутанности. К его доказательству до сих пор есть вопросы, но склоняются конечно к тому что оно все же нарушается. Но к распаду это какое отношение имеет?
                                • 0
                                  Это хороший вопрос, но мне кажется, что было бы странно, если бы существовали локальный переменные, которые влияют на одни вероятностные процессы в квантовой механике, но не на другие. В конце концов, что распад ядра, что запутанность описываются одними и теми же уравнениями. Поэтому если мы можем с уверенностью сказать, что неравенства Белла нарушаются для запутанности (а мы все же можем, практически все loopholes закрыты уже), то почему они не должны нарушаться в более простых процессах (где скрытые переменные даже и не добавляют ничего к пониманию).
                                  • 0
                                    Да. Это именно то что я имел ввиду. С точки зрения текущего понимания теории — вроде подобные локальные переменные выглядят странно, но с формальной точки зрения я не нашел фундаментального обоснования. В квантовой теории иногда появляются такие выходящие за рамки бытовой логики и прошлых теорий вещи, что я допускаю возможность любых чудных поворотов в том как это на самом деле работает.
                                    Кстати, есть интересная гипотеза о локальных «вешних» переменных вызывающих распад (в книжке это тоже относят к «локальным переменным»). Объясняется это тем что квантовые флуктуации пространства/вакуума в области нахождения частицы и являются тем триггером, который вызывает распад. Если подобные флуктуации окажется что на деле не флуктуации, к являются возмущениями неизвестного поля(к примеру) и могут быть рассчитаны — то мы можем рассчитать точное время распада каждого атома.

                                    В целом я склоняюсь что локальных переменных нету.
                                    • 0
                                      Мне кажется, тут есть некоторая неточность в термине «скрытые переменные». Обычно он относится к процессу измерения — мы не пониманием, почему происходит коллапс волновой функции, и как объяснить ЭПР парадокс, и вот придумываем скрытые переменные. В случайных же процессах нет нужды в таких скрытых переменных. Случайный процесс — дело обычное, и распад в этом смысле — «классический» процесс. То бишь, в нем нет никакой квантовой «странности», по сравнению с измерением запутанных частиц. Поэтому если и существует такая теория скрытых переменных, которая не проявляется для запутанных частиц, а только приводит к распаду ядра — она неотличима от «обычной» физики, и не принесет ничего нового к объяснению странностей квантов.
                                      • 0
                                        Может проблема в терминологии. Та которая мне встречалась говорит о скрытых переменных как о переменных на принципиально ином уровне нежели обсуждаемая система — как, например, спины отдельных частиц в куске хлеба. Это не подразумевали принципиальной невозможности измерения подобных параметров. В этом случае открытие локальных внутренних скрытых параметров определяющих распад позволят, возможно (если измерение неразрушающее), предсказать распад каждой конкретной частицы.
                                        • 0
                                          Вот тут в чем дело: если рассматривать систему квантовомеханически, то каждый атом находится в состоянии суперпозиции распался — не распался. Для бета распада, например, это значит, что система (бета частица — остальное ядро) является запутанной. А для запутанной системы неравенства Белла должны нарушаться, что было экспериментально доказано. Поскольку наше измерение — это наблюдение бета частицы, то это измерение производит коллапс состояния ядра в «распалось». Именно для таких процессов были придуманы неравенства Белла.
                                          • 0
                                            Согласно тому что мне удалось найти — неравенства Белла не проверяли для конкретно вашего примера (с распадом). Т.е. чисто формально (опять же — это из серии бозона Хиггса, все знали что он скорее всего есть, но пока не доказали — не вроде бы как была и толика сомнения, здесь эта толика — еще меньше) — может оказаться что природа процесса другая, как с двумя перчатками, выглядит как запутанность, но если для процесса проверить неравенство Белла — то получим что не запутанность.

                                            Может, конечно, я упустил из виду какую-то статью, доказывающую что именно процесс распада тоже нарушает неравенство Белла.
                                            • 0
                                              Потому что каким образом вы можете измерить состояние ядра после? Это же не фотоны, где просто поменять базис измерений, и не электроны… Вообще я не очень представляю, как образом можно измерить состояние ядра в неортогональном базисе. Так что проверка на распаде ядра довольно проблематична.
                                              • 0
                                                Да, я об этом и говорю. Скорее всего это тоже запутанное состояние, но учитывая историю открытий за последние несколько десятилетий — отметать вероятность обратного полностью я бы не решился.
                                                Просто когда видел теории о том что распад определяется локальными переменным ответы на нее были не «почтай учебник, неуч», а «ну может быть конечно, но вряд ли, да и предсказаний оно не изменит».
                                                • 0
                                                  Ну да, я так же и писал. Тоже считаю, что такая теория локальных переменных не изменит ничего. А чисто из бритвы Оккама исходя — зачем вводить эти локальные переменные исключительно для распада, если отлично все описывается стандартными квантами.
                                    • +1
                                      Имхо принцип, который применили для неравенства Белла, работает и для распада (в ссылке выше сказано, что теорема Белла применима к любым физическим характеристикам квантовой частицы, а ядро и время его распада туда подходит). Никаких статистических отклонений для распада не зафиксировано, значит наличие большого класса локальных переменных можно исключить сразу, а остальные, даже при их наличии, могут оказаться принципиально не наблюдаемыми (эксперименты никак не могут определить их наличие или значения, подчиняясь только принципам тервера).

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


                                      Эта цитата применима и к распаду. Путешествия во времени могут проверить детерминированность, но без этого модель проще без скрытых переменных, когда два разных ядра одного изотопа принципиально ничем друг от не отличаются.
                                      • 0
                                        Неравенство Белла говорит о том что не существует квантовой теории которая объясняла бы все явления скрытыми переменными, разве не так? (Английская версия статьи на Вики более доходчива, советую). Из этого не следует автоматическое опровержение локальных переменных для распада. Хотя, соглашусь, подобное объяснение выглядело бы чудно.
                                  • +2
                                    Михаил, вне зависимости от того прав я или нет — вы меня извините за резкий тон. Вы без наезда, а меня что то дернуло.
                        • –4
                          — Кот жив(1) или мёртв(0)?
                          — Он жив на столько же на сколько мёртв (суперпозиция).

                          Существование Бога тоже в суперпозиции — его не существует на столько же на сколько он существует, потому что не доказано ни то ни другое.
                          • НЛО прилетело и опубликовало эту надпись здесь
                            • НЛО прилетело и опубликовало эту надпись здесь
                              • 0
                                Большой взрыв — фальсифицируемая гипотеза. Темная материя — вообще термин для «нечто» которое приводит к наблюдениям отличным от предсказаний классических (на момент обнаружения) теорий не учитывающих, соответственно, это «нечто».
                                • НЛО прилетело и опубликовало эту надпись здесь
                                  • 0
                                    Ну например если бы небыло микроволнового излучения, вселенная бы не расширялась, мы бы получили доказательство негомогенности и неизотропности вселенной на любых масштабах и так далее. Это достаточно очевидные вещи. Посмотрите Вики статью. Там есть достаточно описания, показывавшего что теория большого взрыва фальсифицируема.
                                    • 0
                                      Я думаю, стоит добавить ссылку, а то мне кажется, не всегда понимают, что «фальсифицируемость» не значит неверность.
                              • 0
                                Однажды Альберт Эйнштейн спросил своего друга Нильса Бора:

                                — Ты веришь, что Луны нет, когда мы на неё не смотрим?

                                На что Бор отверил:

                                — А ты можешь доказать обратное?

                                «Этим двум никчёмных тёмным людишкам нужно к психиатру сходить» — Вы так думаете?
                                • НЛО прилетело и опубликовало эту надпись здесь
                                  • 0
                                    Нет, это ты не понял.
                                    Как можно утверждать «НЕ ВОЗМОЖНО»?
                                    Что мешает генной инженерии пони отрастить крылья достаточного размера для полёта?
                                    Что мешает биоинженерам создать вирус синтезирующий в зараженном человеке гены клыков и неутолимой жажды крови и остальные атрибуты вампиров?
                                    Тоже касается единирога.
                                    Вот с макаронным монстром придётся повозиться…
                                    Просто как говорится на вики «чайник Рассела» — ВСЕМУ СВОЁ ВРЕМЯ.
                                    Любой адекватный ученный скажет, что невозможного нет, просто не пришло еще время.

                                    Тоже и с богом, не пришло еще время доказать или опровергнуть его существование.
                                    • НЛО прилетело и опубликовало эту надпись здесь
                                      • 0
                                        Взял с полки баночку и протёр лоб фэйспалмовым маслом.
                                        Кто сказал, что не_существует? Да кто бы он не был, это человек, а ВСЕ люди ошибаются.
                                        Математиками и физиками доказана невозможность существования радиоволн квадратной формы.
                                        И если вы не верите математикам и физикам, потому что они люди, можете всегда сами проверить это утверждение!
                                        • НЛО прилетело и опубликовало эту надпись здесь
                                        • 0
                                          Roboserv > Доказать отсутствие того, чего _не_существует_ — не возможно.

                                          Это просто. Просто перебираем всё множество. Оно конечно. И доказываем.
                                          • 0
                                            Не соглашусь с Вами, когда-то пределом множества объяснений было «Солнце вращается вокруг земли, потому-что..», из той же оперы гравитация и прочие явления, чью природу не возможно было раскрыть на тот момент.
                                          • 0
                                            Абсолютно согласен с предыдушем комментарием. Если система конечна, то доказать отсутсвие чего-либо можно перебором всего, что есть. Если система бесконечна, то смысла доказывать, что в ней чего-то нет — нет, ведб в ней должно быть всё.
                                            • 0
                                              +100500 с Вами согласен!
                                              Не доказано, что система конечна или бесконечна, а значит остаётся перебирать варианты, пока что-нибудь не докажут :)
                                              • 0
                                                Varkus > Не доказано, что система конечна или бесконечна

                                                Стоп! — Доказано что число атомов во Вселенной конечно. И даже подсчитано примерно чему равно.

                                                Так что — система конечна — Перебираем всё множество. Оно конечно. И доказываем.
                                                • +1

                                                  Количество в видимой (причем видимой конкретно сейчас) вселенной.


                                                  А о ее реальных (полных) размах и конечны они или нет вообще есть только пачка разных гипотез, которые никак не проверить.

                                                  • –1
                                                    «Mad__Max > А о ее реальных (полных) размах и конечны они или нет вообще есть только пачка разных гипотез, которые никак не проверить.

                                                    Итан писал недавно — протоном больше и Вселенная в чёрную дыру. Протоном меньше и Вселенная в полный разброс (инфляция не остановилась бы).

                                                    Так что — система конечна — Перебираем всё множество. Оно конечно. И доказываем.
                                                    • +1
                                                      Цитировать Итана в научных спорах… нда… вы бы еще пост на однокласниках предложили в качестве довода.
                                                      • –2
                                                        Shkaff > Цитировать Итана в научных спорах… нда… вы бы еще пост на однокласниках предложили в качестве довода.

                                                        Вы часом сайт не попутали? — Итан вещает на geektimes.ru

                                                        И вы сейчас на geektimes.ru в коментах.

                                                        • +2
                                                          Итан, при всем уважении как к ученому, вещает порой невообразимую желтизну и отсебятину, которая не подтверждена никакими источниками. Он делает хорошее дело для популяризации, но частенько переходит границы, что делает его исключительно ненадежным подкреплением аргументов.
                                                          • –1
                                                            Shkaff > Он делает хорошее дело для популяризации, но частенько переходит границы, что делает его исключительно ненадежным подкреплением аргументов.

                                                            Он вполне надёжен для ссылок в коментах на geektimes.ru

                                                            Возможно в диссертации на него и не надо ссылаться, но мы на geektimes.ru
                                                            • +1
                                                              Вы либо ставите диагноз качеству аудитории на гиктаймс, либо своему пониманию физики.
                                • +1
                                  Это Вы еще про слабые измерения не слышали)
                                  • +1
                                    Известный кот тут упомянут конечно не к месту, суперпозиция в кубите важна, но главная особенность заключается в возможности их запутать (в квантовом смысле), что позволит параллельно (условно говоря за один такт) произвести огромный объём вычислений.
                                    • +5
                                      «Шрёдингер ходил по комнате в поисках нагадившего котёнка, а тот сидел в коробке ни жив, ни мертв.»
                                    • 0
                                      Любопытно, а можно ли вообще сказать, что квантовый компьютер непременно быстрее обычного? С глупым перебором — конечно, да… А вот есть ли доказательство, что не существует алгоритма на классическом компьютере, который будет сравним с квантовым?
                                      • –1
                                        Однозначно быстрее:
                                        — в электронике информация переносится электронами с конечной скоростью, которую уже давно посчитали. На сколько помню она чуть меньше световой скорости.

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

                                        https://ru.wikipedia.org/wiki/Квантовая_запутанность
                                        • +4
                                          Да ну, что вы. Во-первых, не электронами, а ЭМ полем, ведь скорость электронов вообще мизерная — сантиметры в секунду. Во-вторых, между связанными частицами информация не передается. В-третьих, речь идет о пределах эффективности. Теоретически может ли классический алгоритм быть сравним с квантовым.
                                        • +1
                                          Он не быстрее, он МЕГАПАРАЛЛЕЛЬНЕЕ, то есть кубиты устроены так, что на выходе есть информация о всех вариантах развития событий, как если бы обычный компьютер работал одновременно со всеми вариантами исходных данных и выдавал бы вместо просто результата все результаты одновременно, но так, чтобы их можно было отделить друг от друга совершенно не напрягаясь и даже не имея докторской степени. Всё здесь мною сказанное является исключительно моим частным мнением и претендует на правоту не в большей степени, чем выделение газа в резервуар жидкости.
                                          • 0
                                            Ну, по сути мы имеем вместо одного бита (1, 0) один кубит (много состояний). Так что даже не в параллельности дело, а в большем количестве информации в одном кубите. Но операции над кубитами все равно линейные (унитарные). Меня интересует алгоритмическая сложность выполнения операций. Скажем, данный квантовый алгоритм производит операцию за линейное время О(n). Есть ли строгое доказательство, что не существует классического алгоритма с той же эффективностью.
                                            • 0
                                              Такого вроде нет. Есть другое: множество задач на которых можно получить экспоненциальное ускорение на КК имеет меру 0. Классической информации в 1 незапутанном кубите столько же.
                                              • 0
                                                Я понимаю, что существуют задачи, с которыми квантовый компьютер скорее всего справится лучше. Мне было любопытно, есть ли какие-то предпосылки для общего утверждения о потенциальном превосходстве квантового компьютера над классическим в любой задаче (доступной квантовому компьютеру) в смысле алгоритмической сложности.
                                                • +1
                                                  Про экспоненциальное ускорение писал выше(таких задач очень мало). На обычных задачах с внешним оракулом, нет замеделения, т.к алгоритм Гровера(точнее есть ускорение по кол-ву обращений к оракулу в \sqrt{2} раза). Большинство алгоритмов описано здесь http://math.nist.gov/quantum/zoo/
                                              • 0
                                                Много? Не много, а ВСЕ, для одного бита всего два, но.
                                                Дело не в количестве информации: если бы дело было в количестве, разница легко бы нивелировалась увеличением количества бит.
                                                • 0
                                                  Я неправильно выразился про информацию, уточняю вопрос тут.
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                            • +5
                                              Может кто нибудь написать статью не с красивой водой ни о чем, а с примерами «квантовой» арифметики и сравнением её с классической?
                                              • 0
                                                Нашёл такое: пояснение факторизации в старой алгебре и пояснение как такой алгоритм критического этапа должен считаться на квантовом компе.
                                                • +1
                                                  (Ссылку ранее съело) http://eax.me/shors-algorithm/
                                                  • +1
                                                    Я дико ищвиняюсь, что влезаю. Нов приведённой вами статье используется допущение что мы можем построить сколь угодно большой унитарный оператор. Как правило это не так и a**x mod n нужно реализовывать через одно и двухкубитные преобразования.
                                              • +1
                                                >> «оптимизация грузоперевозок (задача коммивояжёра)»

                                                В отличие от взлома криптографии (где принципиально нет возможности узнать насколько вы близки к правильному ответу), на грузоперевозках идеальный результат будет лишь незначительно лучше, чем полученный отижигом, ГА, и т.п методами. Да быстрее, но для таких задач обычно это непринципиально (то же школьное расписание можно хоть все лето составлять).
                                                • +4
                                                  Что я уточнил для себя в последнее время:
                                                  -Квантовая телепортация не про перенос объектов.
                                                  -Путешествия во времени возможны только в будущее и равносильны «заморозке» себя и «разморозке» в будущем.
                                                  -Квантовые компьютеры — не замена обычных ПК, а специализированные, как видеокарты.
                                                  Так ведь?
                                                  • 0
                                                    Про путешествие во времени:
                                                    На сколько я знаю про прошлое вы правы. Но вот для того чтобы в будущее попасть не обязательно себя замораживать. Нужно просто двигаться со скоростью сильно большей чем тот относительно кого вы хотите двигаться во времени. Так же время течёт быстрее для объектов находящихся возле других объектов с большой гравитацией, звёзды, чёрные дыры.

                                                    Где-то было хорошее видео про возможные путешествия во времени — из серии научно познавательных фильмов, но уже не вспомню. Там были вычисления вроде: если мы построим корабль который сможет летать на грани горизонта событий N часов, потом вернётся обратно на Землю, то он вернётся на M дней позже. что-то вроде такого
                                                  • +3
                                                    Квантовый компьютер: взлом любого шифра, кубиты и крайне низкие температуры

                                                    Возможно придираюсь, но, имхо, заголовок слишком желтушный: квантовые компьютеры страшны прежде всего для асимметричных алгоритмов шифрования, для нормальных симметричных алгоритмов, они гораздо менее страшны…
                                                    А для шифра Вернама любой квантовый компьютер страшен настолько же, насколько обычный калькулятор, то есть чуть менее чем никак…
                                                    • +1
                                                      … и хотелось бы заодно у автора статьи узнать, применим ли, например, предел Бремерманна к квантовым компьютерам.

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

                                                      Заголовок и общий стиль, действительно, «желтушный». Было бы интересно увидеть больше чисел — например, тщательное, подробное описание того, как сравниваются скорости работы квантового компьютера и компьютера полупроводникового.

                                                      Чтобы не возникало ощущения, что всю дорогу сравнивают красное с мягким.
                                                      • +1
                                                        Не, вот есть у меня куча кубитов, если есть надёжный квантовый канал и возможность запутать их все, то в «идеальных условиях» наращивать кол-во кубитов можно сколь угодно долго. Про шифрование: для длинны в n бит нам всегда понадобится p(n)(полином) даже с учетом коррекциии, а далее гровером перебираем, главное оракул нормально реализовать. Но вообще Симметричное без рассмотрения алгоритма передачи ключа не имеет смысла рассматривать. А алгоритмы передачи ключа через асимметричные криптосистемы ломаются. Так что придётся использовать либо неабелеву классическую криптографии(Без доказательств, что завтра их не сломают). Либо алгоритмы квантового распространения классических ключей, в которых факт прослушки устанавливается моментально.
                                                        • 0
                                                          Насколько помню, навскидку, тот же NTRUEncrypt квантовыми компьютерами фундаментально быстрее не ломается, так что

                                                          > А алгоритмы передачи ключа через асимметричные криптосистемы ломаются.

                                                          не всегда верно (про полный перебор не говорим, там нас защитит предел Бремерманна). Поэтому рабочий вариант — передать длинный симметричный ключ (256 бит или больше) посредством NTRUEncrypt или аналога, после чего квантовыми компьютерами уже можно и не пугать.
                                                          • 0
                                                            Он не ломается потому что в Svp группа неабелева. Т.е та та самая неабелева криптография, к которой не применим подход через Qft. Про предел не понял. Из определения предела следует только то сто вот этот ящик не может считать быстрее чем что-то если у меня ящиков куча и сильнозапутанные состояния то что мне мешает проводит того же гровера и перебирать? P.S и да состояние меняется быстрее чем за c даже если кубиты в этом состоянии очень далеко.(В теории)
                                                        • +1
                                                          Про сравнение скоростей: Скорость выполнения самих операций, пока никто не сравнивает. Просто рассматриваются сложность в худшем случае для известных классических алгоритмов, и сложностные оценки квантовых алгоритмов (количество унитарных преобразований). Для некоторых задач второе число оказывается экспоненциально меньше первого.
                                                          • 0
                                                            > Скорость выполнения самих операций, пока никто не сравнивает.

                                                            Из соображений общего развития было бы интересно увидеть оценки (сравнение скоростей), когда они имеют смысл. Понятно, что в таком случае как минимум нужно гонять один и тот же алгоритм.
                                                            • +1
                                                              Квантовые алгоритмы сильно отличаются от классических(другая модель вычислений). Так что кроме бенчмарков каких то простых ооператоро и bruteforce vs Grover вряд ли что-то можно сделать
                                                      • –1
                                                        Если я правильно понял, квантовый компьютер расшифрует любой шифр почти мгновенно. Но чтобы понять, что он расшифровал, потребуются годы труда обычных компьютеров?
                                                        • –1
                                                          Нет. Неправильно.
                                                          Квантовый компьютер поможет почти мгновенно найти ключ к сообщению. Но только для тех алгоритмов, что построены на факторизации больших чисел.
                                                          • +1
                                                            Не мгновенно, а экспоненциально быстрее классического компьютера. И не только для факторизации, для дискретного логарифма тоже. Вообще для любой задачи сводящийся к поиску скрытой подгруппы конечной абелевой группы можно экспоненциально быстро найти решение.
                                                        • 0
                                                          Меня вот очень давно интересует ответ на вопрос
                                                          есть ли доказательство того что в нервных системах происходят «квантовые вычисления»?
                                                          • 0
                                                            Насколько я знаю — именно для нервных систем пока нет таких наблюдений.
                                                            Однако, было показано, что биологические организмы используют на внутриклеточном уровне квантовые эффекты (на примере фотосинтеза растений).
                                                            Я думаю, что наличие таких эффектов более чем вероятно в мозгу, и наверняка в процессе эволюции эти эффекты активно участвуют в его функционировании. Но вряд ли они делают там какие-то совсем уж невероятные вещи.
                                                            • 0
                                                              вопрос как вы наверно догадались имеет отношение к ИИ
                                                              вряд ли получится построить полноценный ИИ если окажется что квантовые эффекты являются значимой частью в функционировании мозга
                                                              • 0
                                                                Вряд ли для создания сильного ИИ так уж необходимо копировать принцип функционирования биологического мозга.
                                                                Впрочем, тут пока слишком много белых пятен и это просто гадание на кофейной гуще.
                                                            • 0
                                                              Доказательств такого нет. Есть подобные предположения(гипотезы). Пока не доказанные и ИМХО вообще не особо то обоснованные.

                                                              Квантовые эффекты на самых глубинных уровнях конечно есть. Но они вообще везде есть, даже в закипающем на плите чайнике или куске металла лежащего на столе. А вот надежных свидетельств того, что эти мельчайшие эффекты имеют влияние и выходят на вышестоящие макроскопические уровни пока нет.
                                                              Скорее есть противоположные свидетельства — что работа нейронов в мозге (и шире — нервной ткани) неплохо защищена от влияния подобного «квантового шума». Например у нейронов есть пороги срабатывания (как четкие пороги по напряжению есть у 0 и 1 в классических компьютерах и мелкие флуктуации напряжения не оказывают никакого влияния на результат вычислений), а например нейромедиаторы выбрасываются дозированными порциями по неск. тысяч молекул за раз(на 1 переданный сигнал), что практически исключает влияние квантовых эффектов имеющих место на масштабах отдельных элементарных частиц и одиночных атомов.
                                                              • 0
                                                                Есть интересная гипотеза, что квантовость в нашем мозгу появляется в спиновых центрах в инонах фософора. Такие центры чрезвычайно устойчивы к декогеренции, и могут сохранять запутанность на временах, достаточных для «вычислений». Более того, он связывает работу нейронов с этими центрами и описывает, как собственно происходит переход информации от запутанных центров к нейронам, и как это может ускорять работу мозга. Самое любопытное, что это единственный элемент, который нам жизненно необходим (это мы знаем из опыта), его очень много в мозгу, и при этом может сохранять квантовые свойства долгое время.
                                                                • +2
                                                                  Да, весьма интересная. Правда в самой научное статье имхо больше «подгонки под результат» и wishful thinking — изначально делается предположение, что в мозгу происходят квантовые вычисления, а потом под это пытается найти хоть какой-нибудь механизм, который не противоречил бы явно известной физике и уже известным данным о работе мозга. Чем какое-то исследование имеющегося явления.
                                                                  И такой потенциальный механизм в результате нашел. Но там нет ничего о том, что такое на самом деле происходит. Только показано, что в принципе такое может происходить (не запрещено законами физики).

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

                                                                  P.S.
                                                                  Если связь подтвердится — уже представляю желтые заголовки у журналистов: квантовая запутанность вызывает маниакальные психозы и депрессию!
                                                                  (Препараты лития широко используют для лечения подобных нарушений, будет забавно если выясниться, что это происходит именно за счет того что литий разрушает квантовую запутанность между нейронами).
                                                            • +1
                                                              «Обычному пользователю квантовый компьютер ещё долго будет не нужен, может быть даже никогда.»

                                                              Напомнило:

                                                              «Я не вижу никакого смысла в том, чтобы в каждом доме стоял компьютер.» (Кен Олсен, 1977 год)
                                                              • –4
                                                                Обычный компьютер на Маткаде за доли секунды разложил на множители число 2^607-1 (правда, множитель всего один). Это 182 десятичных знака.

                                                                Алюминий (а также медь, серебро, золото) не переходят в сверхпроводящее состояние ни при какой температуре! Автор сам не знает, что пишет!
                                                                • +1

                                                                  Да ну, как это — алюминий не сверхпроводник? Критическая температура 1.2К. Источник.
                                                                  А про медь, серебро и золото автор и не говорил вроде ничего.

                                                                  • 0
                                                                    Компьютер, работающий при 1 К (а лучше 0,5 К с запасом) — это несерьёзно. Температура жидкого гелия (при атмосферном давлении) намного больше (4 К).
                                                                    • +1
                                                                      А в чем проблема? Криостаты растворения — это просто и приятно, 20 мК — обычное дело. А также можно парами гелия охлаждать ниже 1К, или адиабатическим размагничиванием (что не очень хорошо для компьютера, правда).
                                                                      Дома не поставить, конечно, но дома квантовый компьютер и не нужен.
                                                                • 0
                                                                  Может это надо было размещать на сайте mail.ru в разделе хайтек? Там бы прекрасно зашел такой заголовок. А так постквантовые алгоритмы даже не вчера были придуманы.
                                                                  • 0
                                                                    кубиты — хрупкие квантовые системы… А когда рядом с ними мы сажаем ещё кубиты, они неизбежно начинают взаимодействовать друг с другом, и квантовое состояние каждого из них разрушается. И чем больше их будет рядом — тем быстрее оно будет разрушаться.

                                                                    Может в итоге существует теоретический предел на количество соседних кубитов, который не даст сделать большой квантовый компьютер, превосходящий в вычислениях «простые» компьютеры?
                                                                    • +1
                                                                      mtivkov > Может в итоге существует теоретический предел на количество соседних кубитов, который не даст сделать большой квантовый компьютер, превосходящий в вычислениях «простые» компьютеры?

                                                                      Пока, как я слыхал, нащупывают ПРАКТИЧЕСКИЙ предел. — Ушли недалеко.

                                                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                    Самое читаемое