Google представила новый квантовый процессор

    Корпорация Google представила 72-кубитный квантовый процессор Bristlecone. С помощью этого процессора подразделение Google Quantum AI lab, ответственное за разработку квантового компьютера, будет тестировать системные ошибки и масштабируемость технологии, а также области применения квантовой симуляции, оптимизации и машинного обучения «для решения проблем реального мира», как пишет компания в блоге.

    Квантовый процессор Google Bristlecone

    Новый 72-кубитный квантовый процессор Google Bristlecone построен по принципу, который позволил в предыдущем 9-кубитном процессоре показать низкую частоту ошибок при считывании данных (1%), при работе однокубитного вентиля — 0,1% и при работе двухкубитного вентиля — 0,6%, что, как отмечает Google, было лучшим результатом компании. Перед применением нового процессора в работе важно понять его возможности: команда создала инструмент, проверяющий его на ошибки, с помощью решения идентичных задач на квантовом процессоре и в классической симуляции. При низком количестве ошибок может быть достигнуто «квантовое превосходство».

    Прогноз Google: График показывает снижение количества ошибок при увеличении количества кубитов в процессоре. Начиная с количества кубитов 10 в шестой степени количество ошибок будет находиться ниже уровня 10 в минус третьей степени, что сделает приемлемым использование квантовых вычислений
    Прогноз Google: зависимость количества ошибок от количества кубитов в процессоре

    Квантовые компьютеры используют квантовую суперпозицию и квантовую запутанность для передачи и обработки данных. Одной из главных задач квантовых компьютеров станет усиление искусственного интеллекта. Кубиты квантового процессора — это квантовые аналоги битов. Два расположенных рядом кубита имеют четыре состояния — оба вкл, оба выкл, вкл/выкл и выкл/вкл, каждый из них имеет вес или «амплитуду», которая способна играть роль нейрона; третий кубит в такой системе позволяет представить восемь нейронов, а четвёртый — шестнадцать. Изменение состояния четырёх кубитов приводит к обработке шестнадцати нейронов за один раз, в то время как классический компьютер обрабатывал бы эти числа по одному.

    Одной из проблем при работе квантового компьютера является количество ошибок, которые возникают при вычислениях, считывании и записи информации в кубиты. В июне 2016 года исследователи из Google построили процессор из 9 кубитов, который показал высокую надёжность. Эту разработку они смогли масштабировать к марту 2018 года, увеличив количество кубитов до 72. В процессоре кубиты расположены в два слоя 6x6 друг над другом. Подразделение Google Quantum AI lab тестирует разработку.

    Схема внутреннего строения квантового процессора Google Bristlecone состоит из 72 кубитов, расположенных в шахматном порядке в два слоя, каждый 6 на 6 кубитов. Изображены в виде символов X
    Квантовый процессор Bristlecone состоит из 72 кубитов, изображённых на схеме (справа) в форме «X», где точки соприкосновения концов символа отображает связь кубита с ближайшими «соседями»

    На данный момент квантовыми компьютерами занимаются ряд исследовательских команд, в том числе — IBM. В марте 2017 года компания объявила о запуске проекта IBM Q, и к июню представила два процессора: 16-кубитный для работы в научной сфере и 17-кубитный для коммерческого использования. В 2017 году IBM Research разработала 49-кубитный процессор.

    В июле 2017 года команда российских и американских учёных из Гарвардского университета, возглавляемая сооснователем Российского квантового центра (РКЦ) Михаилом Лукиным, сообщила о создании 51-кубитного квантового компьютера.

    В России в марте 2018 года между Внешэкономбанком, компанией «ВЭБ Инновации», Фондом перспективных исследований (ФПИ), МГУ имени Ломоносова и АНО «Цифровая экономика» было подписано соглашение о разработке 50-кубитного квантового компьютера.
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 85

      +3

      Вы так написали, как будто они его уже построили, а это просто концепт:


      The goal of the Google Quantum AI lab is to build a quantum computer...
      • НЛО прилетело и опубликовало эту надпись здесь
          +1

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

            +1
            Так они сами пишут про nearest neighbor connectivity. Из нового на нем разве что коррекцию ошибок отрабатывать — ну а что поделать, технология еще недалеко ушла от ловушек с двумя ионами.
              +1

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

          0
          Из того что пишут, выходит что реально построили. Просто об ошибках не надо забывать. Вопрос такие ли они «маленькие», чтобы реально что-то делать. Связность там примерно та же, что у Intel. Сам немного повозился только с IBM. Там у 16 кубитов вообще «лесенкой» 8х2. Люди даже на ней что-то делают, но у меня не особо выходило. Слишком быстро всё разваливается.
            +1

            Ну я не знаю, я читаю их блог:


            We are looking to achieve similar performance to the best error rates of the 9-qubit device, but now across all 72 qubits of Bristlecone. We believe Bristlecone would then be a compelling proof-of-principle for building larger scale quantum computers.

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

              0
              Они пишут, что хотят получить тот же малый уровень ошибок. Я так понимаю, значит что-то работает. Иначе это вообще шутка не очень смешная — посмотрите сколько пошло комментариев по разным источникам. На моей памяти один кубит у IBM вдруг стал работать хуже раз в сто, потом через неделю исправили. Тут может что-то похожее.
                +2

                Нет, ну в целом нормально — они могли представить на конференции концептуальный дизайн и первые идеи, как это должно работать. Это если основываться только на их источнике — блоге, а не заниматься гаданием. Они же не пишут: "мы построили новый компьютер", они пишут: "мы представили прототип и концепт, как он будет когда-нибудь хорошо работать для error correction".

                  0
                  C error correction не особо понятно — сейчас обычно обсуждаются схемы с сотнями, тысячами на каждый бит. Что там на 72 тестировать. Только Microsoft со своими топологическими кубитами надеется на десятки за счёт другой схемы работы.
                    0

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

                    +2
                    Вот тут цитируют Мартиниса, что мол только что начали его тестировать.
                      +1

                      Чтд, спасибо:) Но все равно дело хорошее, посмотрим, куда эта гонка КК нас приведет.

              0
              Так вроде всё хорошо:

              — The goal of the Google Quantum AI lab is to build a quantum computer
              — Today we presented Bristlecone, our new quantum processor

              Представили процессор, а построить хотят компьютер. Или Вы системный блок процессором называете?))
                0

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

              0
              Это такой же ненастоящий квантовый процессор как dwave (где действительнро связанными были максимум 8 кубит) или речь идет о полной связности всех 72-ух?
                +1
                Это такой же ненастоящий квантовый процессор как dwave (где действительнро связанными были максимум 8 кубит) или речь идет о полной связности всех 72-ух?

                Связность здесь ни при чем. Настоящий квантовой процессор может быть и из 2 кубит и такие были. Просто он не очень полезен. У DWave — устройство, которое может решать одну конкретную задачу, а Гугл и остальные хотят создать наподобие универсального процессора в обычных компьютерах. Сейчас по видимому, это устройство по разным параметрам не дотягивает до приемлемого состояния, а то бы они уже продемонстрировали «квантовое превосходство»
                  0
                  я и говорю о спектре доступных задач, чем больше связанных кубит тем он шире.
                  • НЛО прилетело и опубликовало эту надпись здесь
                      +2
                      Не факт. А вот практический предел на данный момент очень низок.
                        0
                        На текущий момент — этот предел определяет количество ошибок при чтении результата, чем больше связанных кубит тем эта зависимость выше.
                          0
                          А на графике в статье все наоборот. Чем больше кубитов тем ошибок меньше.
                            +2
                            Это не график. Это двумерное пространство, в котором есть линия, подписанная «Направление исследований Google» :)
                      0
                      а Гугл и остальные хотят создать наподобие универсального процессора в обычных компьютерах
                      Интересно, какие физические принципы они планируют использовать?

                      Во всяких популярных публикациях по квантовым вычислениям нарисованы гейты, соединённые так, как требуется для решения задачи. А как физически планируется достигать таких конфигураций — никто почему-то не пишет.
                    +1

                    Компьютеры D-Wave работают на принципе квантовой релаксации и решают крайне узкий спектр задач, в отличии от Google аналогов.

                      0

                      Вы совершенно правильно ставите вопрос: сколько из этих купит реально запутаны. Гугл скромно молчит, т.к. похвастаться, скорее всего, нечем.


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


                      Убеждает меня в этом их график, что ошибки снижаются при росте числа "ихних" кубитов. В настоящем квантовой компьютере ошибки будут только нарастать с ростом количества кубитов, что очевидно.


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


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

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

                          Они используют корректировку ошибок с помощью кубитов, поэтому, чем больше кубитов, тем легче им корректировать ошибки: ". That’s a key result — it shows that the quantum logic operations are trustworthy enough that by adding more qubits, we can detect more complex errors that otherwise may cause algorithmic failure." (из предыдущей статьи о 9-кубитоном варианте)
                          Ещё один мой аргумент против Гугл: компьютер, это видно, не криогенный. А большое количество настоящих кубитов сегодня достигается только вблизи нуля кельвинов.

                          Не знаю, что там видно, но компьютер этот использует сверхпроводящие гейты. Что-то я сомневаюсь, что у ГУгла есть сверхпроводники при комнатной температуре.
                            0
                            Они используют корректировку ошибок с помощью кубитов, поэтому, чем больше кубитов, тем легче им корректировать ошибки

                            Разумеется. Вот только они добавляют кубиты, которые многократно дублируют базовую ячейку. Грубо говоря, если из 36 ячеек 19 посчитали 2х2=4, а 17 ячеек посчитали 2х2=5, то стало быть, правильный ответ 4. В таком случае действительно, если наращивать число ячеек, вероятность ошибки будет падать. О чём они и говорят.

                            Это ни то же самое, что добавлять кубиты в запутанный набор. Их реально считающий квантовый компьютер состоит, по-видимому, всего из двух кубит. Остальное многократное резервирование для исправления ошибок.
                              +1
                              >Разумеется. Вот только они добавляют кубиты, которые многократно дублируют базовую ячейку. Грубо говоря, если из 36 ячеек 19 посчитали 2х2=4, а 17 ячеек посчитали 2х2=5
                              То, что вы описываете это стандартная схема утроения, она может либо фазовые ошибки исправлять либо bit flip, но не обе вместе, для больших нужно либо shor code либо два уровня [7,1,3].

                              Проблема даже не в этом, например если они используют shor code для QEC то у них в лучшем случае 8 лог кубитов(полезных для вычислений), а не 72. Но проблема в том, что для shor code нужно 72 запутанных кубита, а у них их нет, т.е если смотреть что у них реально может быть дай бог 6-8 запутанных кубит, то получим что error correction только на bit flip или только на фазу и 2-3 логических
                    • НЛО прилетело и опубликовало эту надпись здесь
                        –1
                        Прелесть квантового компа в потенциальном преодолении экспоненциального взрыва: квантовый компьютер позволит решать NP-трудные задачи за вменяемое время… Правда для этого нужно количество кубит подтянуть до N. 72 кубита ну никак не порвут классические компы.
                        • НЛО прилетело и опубликовало эту надпись здесь
                          • НЛО прилетело и опубликовало эту надпись здесь
                              +1
                              FPGA в виде PCI плат не так уж и мало.
                                +1
                                Цены там мягко говоря неадекватные, как тестовое устройство разработчика устройств это покатит, но не как вычислительное устройство общего назначения.
                              +2
                              но ведь и взять на борт современного CPU ПЛИСу, то точно так же это позволит решать NP-трудные задачи за вменяемое время.

                              Не позволит. Возьмем задачу коммивояжера. Ее можно решать точно для размерности N=1000. А вот уже для N=1001 она не решается — время решения уже неприемлемо долгое. И даже если вы при помощи ПЛИСов поднимете размерность до N=1001, то уже N=1002 будет недоступно даже для ПЛИСов. Я уж не говорю про энергозатраты такого мероприятия. В том-то и проблема экспоненциального взрыва, что на классических архитектурах вы упретесь в масштабирование.

                              вот вспомнить пресловутых майнеров. У них NP-трудная задача, а денег им хочется. Что они делают? берут ПЛИС, решают на ней эту NP-трудную задачу, затем оформляют ПЛИС как относительно недорогую микросхему и начинают копать.

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

                              Квантовые компьютеры, если они будут созданы (в чем есть сомнения), решат проблему экспоненциального роста сложности задач на корню. Не нужно будет для новой задачи строить АЭС и фермы для майнинга решения.
                              • НЛО прилетело и опубликовало эту надпись здесь
                                  0
                                  у Вас ошибка: при размерности 1000 точно ее решать невозможно

                                  Возможно, методом ветвей и границ. Хотя, конечно, конкретная размерность, какую осилит метод ветвей и границ, сильно зависит от свойств самой задачи. Но N=1000 точно решается.

                                  Уже при размерности 10 ее решать точно нельзя

                                  Метод ветвей и границ а) точный, б) позволяет поднять размерность до 1000.

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

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

                                  так я и прошу помочь мне понять как квантовый компьютер мне поможет с той же задачей комивояжера?

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

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

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

                                    Буквально на днях тут была статья-перевод какраз о попытках использования квантовых компьютеров именно для ускорения нейросетей и их обучения.
                                      –2
                                      Нет, если рассматривать процесс обучения в комплексе, он ложится на квантовый компьютер отлично, но к сожалению размерность сети потребует аналогичный порядок количества связных кубит.

                                      Еще раз: в нейросети нет экспоненциальной вычислительной сложности. алгоритм обучения — линейный (или квадратичный? не спец. Факт, что не экспоненциальный). На хрена использовать квантовые компы для обычных линейных алгоритмов?
                                      Вам никто не запретит умножение двух чисел реализовать полным перебором, но это ведь попахивает идиотизмом? Тоже и с нейросетями.
                                      +1
                                      > Если не ошибаюсь, для гипотетического квантового компьютера разработали алгоритм, решающий задачу за линейное время.

                                      Ошибаетесь. Квантовые алгоритмы, решающие NP-полные задачи, неизвестны.
                                        –1
                                        Вы правы. Есть, например, реализация метода ветвей и границ к коммивояжеру, но, говорят, что от экспоненциальной сложности не спасает.
                                        +1
                                        >Если не ошибаюсь, для гипотетического квантового компьютера разработали алгоритм, решающий задачу за линейное время. Идея в том, что экспоненциальная сложность не исчезает сама по себе. Просто квантовая природа прячет в себе экспоненту.

                                        Общий случай TSP не BQP так что в общем случае будет вместо факториала, корень из него. Если известно, что веса рёбер имеют нормальное распределение, вот тогда только BQP

                                        Во вторых вы ошибаетесь что на КК можно решать NPC задачи, ни одного алгоритма ускоряющиеся NPC задачи мне не известно. Задача факторизации не является NPC.
                                        • НЛО прилетело и опубликовало эту надпись здесь
                                          0
                                          так я и прошу помочь мне понять как квантовый компьютер мне поможет с той же задачей комивояжера?
                                          Если совсем грубо, перебирая варианты классическим компьютером, мы за 1 шаг можем из пункта A пойти в B, а за другой шаг — из A в C.

                                          Используя квантовые вычисления, можно создать состояние суперпозиции, когда за один шаг мы пошли одновременно во все точки, достижимые из A (т.е. сразу в B, C, E, H, ...). За второй шаг — суперпозиция всех возможных маршрутов длины 2 (ABA, ABC, ACD, ADE, AEC, ...). Затем через N шагов происходит редукция и из всех состояний суперпозиции выживает то, которое оптимально. Его считываем как решение.
                                            0
                                            у Вас ошибка: при размерности 1000 точно ее решать невозможно

                                            Возможно, методом ветвей и границ. Хотя, конечно, конкретная размерность, какую осилит метод ветвей и границ, сильно зависит от свойств самой задачи. Но N=1000 точно решается.

                                            Прошу пардону! Я Вас ввел в заблуждение. N=1000 действительно точно не решается. Метод ветвей и границ для точных решений осиливает N=100, т.е. в 10 раз меньше.
                                        0
                                        Поидее ни один квантовый комп не порвет современные на современных же программах.
                                        Когда-то давно еще читал, что для них и программирование отдельное, несовместимое с обычными ПК. Т.е. интерпретатор написать конечно же можно, но это будет тормозное чудовище как эмулятор PS4 например.
                                          +1
                                            +2
                                            Поидее ни один квантовый комп не порвет современные на современных же программах.

                                            Мгновенно порвет на специфических задачах. NP-трудные задачи не имеют эффективных алгоритмов, а неэффективные алгоритмы могут искать решение дольше, чем существует Вселенная. Квантовые же компьютеры способны выдавать решение таких задач (для которых может потребоваться в миллиарды раз большее время, чем существует Вселенная), за несколько секунд.

                                            Но все это при условии, что квантовые компьютеры будут созданы. Там тоже проблема масштабирования присутствует. Преодолеют — майнинг в прошлое уйдет. Как и вся цифровая экономика и приватность в интернете. Зато задача фолдинга белков будет решена, что круто :)
                                              0
                                              Экономика и интернет адаптируются одними из первых еще ДО появления достаточно опасного квантового компьютера, уже сейчас разрабатываются алгоритмы шифрования, защищенные от этого.
                                                0
                                                уже сейчас разрабатываются алгоритмы шифрования, защищенные от этого.

                                                … Для которых как раз и требуются квантовые компьютеры, которые поломают классическую криптографию.
                                                  0
                                                  Разные люди подразумевают под квантовым компьютером разные вещи, обычно считают саму возможность связывания кубитов, но с появления dwave стали называть квантовыми компьютерами системы, ограниченные по задачам и количеству одновременно связных кубит.

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

                                                  Я же имею в виду что достаточно разработать защиту от универсального квантового компьютера.
                                                    +1
                                                    Я же имею в виду что достаточно разработать защиту от универсального квантового компьютера.

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

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

                                                    3. У вас есть задача и кто-то вам предлагает ответ. Вы можете быстро проверить, является ли ответ решением задачи или нет. Иными словами, для проверки вам не нужно создавать новых Вселенных, проверить вы можете за считанные секунды на обычных компьютерах.

                                                    Так вот, ВСЯ современная криптография основана на задачах из класса NPC: вы быстро можете перемножить пару случайно сгенерированных чисел. А вот разложить полученное число на множители вы уже быстро не можете: NP-трудная задача.

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

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

                                                    Ну т.е. представьте себя на месте ракового больного, которому осталось считанные дни жить. И он тут узнает, что появилось новое уникальное лекарство от рака, которое его вылечит. Одна беда. Получить такое лекарство он сможет минимум через 10 лет.
                                                      +1
                                                      И никакую защиту на КЛАССИЧЕСКИХ компьютерах вы не сможете придумать даже теоретически.

                                                      А разве алгоритмы на изогенных эллиптических кривых не устойчивы к перебору на квантовых компьютерах? При этом вполне считается на обычных ПК.
                                                        +1
                                                        Не могу сказать. Да, на хабре была статья, что изогения спасет криптографию при появлении квантовых компьютерах. Так что, похоже, я не прав. Речь я вел про класс задач NPC, к какому классу относится криптография на изогенных эллиптических кривых — я не знаю.
                                                          0
                                                          Я тоже не светоч разума в этой области, просто меня задела процитированная мною фраза, тогда как алгоритм Шора существенно ускоряет только один конкретный класс задач.
                                                          +1

                                                          Алгоритм Шора решает две задачи: разложение на множители и дискретный логарифм (сама статья Шора так и называется Algorithms for Quantum Computation: Discrete Log and Factoring, 1994, doi:10.1109/SFCS.1994.365700). При этом он работает "для любой коммутативной группы работает, нужно только умножать уметь", см http://logic.pdmi.ras.ru/~sergey/teaching/crypto10/12-quantum.pdf "Алгоритм Шора" — Сергей Николенко, Криптография — АФТУ РАН, 2010


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

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

                                                          (для создания некоммутативной криптографии не нужны квантовые компьютеры, а "квантовая криптография" = Quantum Key Distribution — это всего лишь линии связи на одиночных квантах и никаких кв.комп. также не требуют: http://sqi.cs.msu.su/store/storage/ss8dw5n_quantum_cryptography.pdf "квантовой криптографии… возможность генерации ключей, секретность которых гарантируется фундаментальными законами квантовой механики", http://book.itep.ru/6/q_crypt.htm)

                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                            +2
                                                            почему на квантовом компе задача будет решена за линейное время?

                                                            Алгоритм Шора.
                                                            давайте мы эмуляцию кубита запрограммим

                                                            Любая эмуляция тормоза, а тут и не факт, что это вообще возможно заэмулировать.
                                                              0
                                                              почему на квантовом компе задача будет решена за линейное время?

                                                              Потому что квантовый мир «прячет в себя» экспоненту. Суперпозиции, квантовая запутанность — это про то самое.

                                                              давайте мы эмуляцию кубита запрограммим на обычном компе и будем решать за линейное время? почему нельзя?

                                                              Когда вы будете эмулировать квантовую систему на классическом компьютере, ваша физическая «квантовая экспонента» развернется в вычислительную экспоненту. И эмулировать вы будете эту систему ровно столько же, сколько будете решать NP-трудную задачу на классическом компьютере.
                                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                                  +1
                                                                  плюс если бы кто-то написал эмулятор кубита, то во первых широкие массы получили бы доступ к возможности его (кубит) изучать, ну и заодно оптимизировать этот самый эмулятор.

                                                                  Есть все эти эмуляторы. Поищите по "open source quantum computer emulator". Проблема в том, что требуемый объем памяти и время расчетов растет экспоненциально с ростом количества кубитов. Самая большая эмуляция — 51 кубит, кажется.

                                                                  • НЛО прилетело и опубликовало эту надпись здесь
                                                                      0
                                                                      16-70 кубит всего

                                                                      Там не те кубиты :) Там резервирование, а не квантовая запутанность.
                                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                                    0
                                                                    вот этого «прячет в себя» я и не понимаю.

                                                                    Подозреваю, что полноценно никто не понимает. Квантовое состояние описывается суперпозицией квантовых состояний отдельных частиц. Ну т.е. про кота Шредингера будет описание вида «кот жив с вероятностью 0.5 и одновременно кот мертв с вероятностью 0.5». Когда количество запутанных частиц растет, описание квантовой системы растет с экспоненциальной сложностью. И при этом продолжает работать в реальном времени. :) Наша Вселенная не тормозит и не подвисает :)

                                                                    А решая ОДНУ задачу на обычном компе мы можем поискать способы оптимизации ее решения и выбрать какой-то который будет приемлем для эмуляции.

                                                                    И любой из этих способов будет сильно тормознее физической вселенной. Сильно — это в экспоненту раз.

                                                                    а потом на кубитах мы сможем решать множество NP-трудных задач.

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

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

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

                                                                    вот ту же задачу комивояжера на современных компах решают же 100500 способами.

                                                                    И среди этих 100500 способов нет ни одного, который был бы а) быстрым и одновременно б) точным. Есть или точный, но для которого нужно стотыщмильярдов тысячелетий времени или есть быстрый, который даст решение вот прям щас, зато с погрешностью в два раза (что, кстати, круто, потому как ГАРАНТИРУЕТСЯ, что погрешность не хуже).
                                                                    Иными словами: задача коммивояжера не решена.
                                                                    На квантовом компьютере можно придумать алгоритм (вроде еще не придуман, но, кажется, что придумать его гораздо проще, чем решить проблему P<>NP). И тогда задача будет решаться за линейное время. (несколько секунд против стотыщмилярдов тысячелетий).

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

                                                                    Вы правда хотите исследовать ФИЗИЧЕСКИЙ мир по эмуляции? :) Так-то кубиты и иже с ними изучают на ускорителях. Если вы про теорию, то эмуляцию написать нет проблем. На пару-тройку кубит вы эмулировать сможете. На большее у вас мощностей не хватит.

                                                                    ну и заодно оптимизировать этот самый эмулятор.

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

                                                                    почему в этом направлении работы не ведутся?

                                                                    В какой именно? Эмуляция кубитов? Потому что тут нечего исследовать. Эмуляция вопросов не вызывает.
                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                        0
                                                                        ну исследуем же мы физический мир по виртуальным опытам (глядя на опыты на рисунках в учебнике физики или глядя на видеоопыты). Соответственно — почему нет?

                                                                        Для обучения — нет проблем. Для ученых — такой опыт не несет ничего нового.
                                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                                +1
                                                                > Можно ли разработать криптографию, устойчивую к взлому квантовыми компьютерами? Можно. Но для ее создания нужны квантовые компьютеры.

                                                                А как же шифр Вернама от 1917 года и широко используемые во Второй Мировой одноразовые шифроблокноты?
                                                                В лучшем случае квантовый компьютер выдаст столь неудобоваримое количество расшифровок, что явно потребуется неудобное количество времени на анализ. Есть поговорка — гора родила мышь. В нашем случае с точностью до наоборот — мышь наложила кучу с Эверест.
                                                                Естественно, для непрерывных потоков данных сложно извратиться с подобным методом, но на то пусть голова болит у гуру. Криптостойкость метода заставит им воспользоваться в своё время.
                                                                  0
                                                                  Моего внутреннего параноика всегда напрягало, что во всех курсах, книгах и статьях на тему крипторграфии про шифр Вернама рассказывают в самом начале, в двух абзацах. Заключают, что он неудобен до полной невозможности им пользоваться на практике и вообще не нужен, используйте замечательный AES и забудьте, забудьте, забудьте про одноразовый блокнот. Почему? Выдаешь товарищу самую маленькую флешку со случайными данными — переписываться на всю жизнь хватит. Зато абсолютная теоретическая невскрываемость никем и никогда, это не круто разве?
                                                                    0
                                                                    То, что шифр Вернама обходят стороной, вполне объяснимо. И что на него всего два абзаца отведено тоже понятно — он прост до безобразия.
                                                                    В современной жизни, когда наблюдается засилие вычислительной техники, все стремятся к упрощению своей жизни и во главу угла поставлено пресловутое «баланс цены и качества».
                                                                    С лёгкой руки математиков (им только дай волю порезвиться, разведут малину) были разработаны симметричные и не очень шифровальные методики, суть которых мы прекрасно знаем — невозможность современными средствами раскрыть зашифрованное в сроки, когда информация является актуальной. И теперь мы подходим к тому, что это изначально неправильное в глобальном масштабе направление подошло к грани теоретического провала.
                                                                    С шифроблокнотами крайне сложно решить задачу передачи самого блокнота с гарантированным непопаданием его в чужие руки.
                                                                    Второй неприятный момент — ёмкость блокнота. При современных потоках информации любой шифроблокнот весьма быстро истощится.
                                                                    Третий момент связан со вторым. При необходимости генерации одноразового кода есть далеко ненулевая опасность повторения последовательности произвольной длины, а это абсолютно недопустимо. В той же Второй Мировой был зафиксирован факт вскрытия сообщения из-за ошибочного повторного использования старого кода. И это в условиях, когда про цифродробилки ни ухом, ни слухом.

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

                                                                    Вот этот хвалёный AES и вкупе с ним и находятся сейчас на последнем издыхании. И современные методы шифрования имеют неустранимый критический недостаток. Провал шифровального механизма, ключей означает, что буквально вся перехваченная за многие лета информация будет прочитана, в отличии от попадания в чужие руки «странички блокнота». Да, одно сообщение будет раскрыто, но не более того. Разница налицо.
                                                                    Если разобраться, то каждый метод имеет свою область применения.

                                                                      0
                                                                      Я знаю о недостатках одноразового блокнота и отнюдь не призываю его использовать повсеместно. Оспариваю лишь тезис, что он-де на сегодняшний день вообще не может иметь никакого применения.
                                                                        0
                                                                        Вот это уже точно не ко мне. Я не только не писал, что блокнот не имеет применения, но считаю, что в итоге именно этот метод придётся использовать. Если квантовые компьютеры достигнут нужной мощности и если вся шелуха вокруг них окажется правдой, а не рекламой надежд.
                                                                          0
                                                                          И в чём смысл минусовки?
                                                        +2

                                                        Пока ещё неизвестно могут ли квантовые компьютеры ускорить решение NP-полных задач, так что про NP-трудные задачи говорить рановато. О взаимосвязи класса сложности BQP с другими классами сложности пока мало что известно.

                                                          0
                                                          Пока ещё неизвестно могут ли квантовые компьютеры ускорить решение NP-полных задач, так что про NP-трудные задачи говорить рановато.

                                                          Насколько я помню, есть квантовый алгоритм для факторизации чисел. Рассчитан такой алгоритм на идеальный квантовый компьютер, который выдает достоверные решения, а не с какой-то заданной вероятностью.
                                                          Другое дело, что пока что даже реальных квантовых компьютеров нет, не то, что идеальных. И да, есть большие сомнения, что таковые вообще будут созданы. Так что, да, есть подозрения, что классическая криптография еще поживет, вместе с насущными нерешенными проблемами вроде фолдинга белков.
                                                            +1
                                                            Не было доказано, что факторизация — NP-полная (NP-complete) задача, то есть пока неизвестно, можно ли любую задачу из класса NP свести к разложению на множители.

                                                            Оригинальный алгоритм Шора выдает правильный результат с вероятностью 1/2 (см. arxiv.org/abs/quant-ph/0208183 ) на идеальном квантовом компьютере и это не имеет отношения к классу сложности. Реальные квантовые компьютеры вполне себе есть, например www.nature.com/articles/nature18648

                                                        +2

                                                        Если очень в общем виде объяснять (как дилетант дилетанту), то фишка в том, что из-за суперпозиции квантовый комьютер может осуществлять перебор различных вариантов одновременно. Надеюсь, более понимающие люди объяснять более корректно.


                                                        Но. Кто мешает выполнять нейроны на околопроцессорной периферии?

                                                        Так уже делают.


                                                        • GPU
                                                        • NVidia Volta с аппаратными "тензор-блоками"
                                                        • и не только, тысячи их

                                                        А ПЛИС… ПЛИС хорошо работают при конвейеризации вычислений, например, потоковой обработке сигналов. У сферического плиса в вакууме частоты существенно ниже, чем у современных ЦПУ

                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                            +1

                                                            Традиционный комментарий, лучшее объяснение работы квантового компьютера (то, о чем комментарий Alex_Q выше, чуть более подробно):
                                                            If you don't talk to your kids about quantum computing, someone else will.
                                                            image


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


                                                            If you take just one piece of information from this blog:
                                                            Quantum computers would not solve hard search problems
                                                            instantaneously by simply trying all the possible solutions at once.
                                                              +2
                                                              Его книжка Quantum Computing since Democritus — очень мне понравилась. Всем рекомендую

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

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