Новый 72-кубитный квантовый процессор Google Bristlecone построен по принципу, который позволил в предыдущем 9-кубитном процессоре показать низкую частоту ошибок при считывании данных (1%), при работе однокубитного вентиля — 0,1% и при работе двухкубитного вентиля — 0,6%, что, как отмечает Google, было лучшим результатом компании. Перед применением нового процессора в работе важно понять его возможности: команда создала инструмент, проверяющий его на ошибки, с помощью решения идентичных задач на квантовом процессоре и в классической симуляции. При низком количестве ошибок может быть достигнуто «квантовое превосходство».
Прогноз Google: зависимость количества ошибок от количества кубитов в процессоре
Квантовые компьютеры используют квантовую суперпозицию и квантовую запутанность для передачи и обработки данных. Одной из главных задач квантовых компьютеров станет усиление искусственного интеллекта. Кубиты квантового процессора — это квантовые аналоги битов. Два расположенных рядом кубита имеют четыре состояния — оба вкл, оба выкл, вкл/выкл и выкл/вкл, каждый из них имеет вес или «амплитуду», которая способна играть роль нейрона; третий кубит в такой системе позволяет представить восемь нейронов, а четвёртый — шестнадцать. Изменение состояния четырёх кубитов приводит к обработке шестнадцати нейронов за один раз, в то время как классический компьютер обрабатывал бы эти числа по одному.
Одной из проблем при работе квантового компьютера является количество ошибок, которые возникают при вычислениях, считывании и записи информации в кубиты. В июне 2016 года исследователи из Google построили процессор из 9 кубитов, который показал высокую надёжность. Эту разработку они смогли масштабировать к марту 2018 года, увеличив количество кубитов до 72. В процессоре кубиты расположены в два слоя 6x6 друг над другом. Подразделение Google Quantum AI lab тестирует разработку.
Квантовый процессор Bristlecone состоит из 72 кубитов, изображённых на схеме (справа) в форме «X», где точки соприкосновения концов символа отображает связь кубита с ближайшими «соседями»
На данный момент квантовыми компьютерами занимаются ряд исследовательских команд, в том числе — IBM. В марте 2017 года компания объявила о запуске проекта IBM Q, и к июню представила два процессора: 16-кубитный для работы в научной сфере и 17-кубитный для коммерческого использования. В 2017 году IBM Research разработала 49-кубитный процессор.
В июле 2017 года команда российских и американских учёных из Гарвардского университета, возглавляемая сооснователем Российского квантового центра (РКЦ) Михаилом Лукиным, сообщила о создании 51-кубитного квантового компьютера.
В России в марте 2018 года между Внешэкономбанком, компанией «ВЭБ Инновации», Фондом перспективных исследований (ФПИ), МГУ имени Ломоносова и АНО «Цифровая экономика» было подписано соглашение о разработке 50-кубитного квантового компьютера.
Комментарии (80)
rPman
09.03.2018 23:49Это такой же ненастоящий квантовый процессор как dwave (где действительнро связанными были максимум 8 кубит) или речь идет о полной связности всех 72-ух?
Sychuan
10.03.2018 02:52Это такой же ненастоящий квантовый процессор как dwave (где действительнро связанными были максимум 8 кубит) или речь идет о полной связности всех 72-ух?
Связность здесь ни при чем. Настоящий квантовой процессор может быть и из 2 кубит и такие были. Просто он не очень полезен. У DWave — устройство, которое может решать одну конкретную задачу, а Гугл и остальные хотят создать наподобие универсального процессора в обычных компьютерах. Сейчас по видимому, это устройство по разным параметрам не дотягивает до приемлемого состояния, а то бы они уже продемонстрировали «квантовое превосходство»rPman
10.03.2018 11:53-1я и говорю о спектре доступных задач, чем больше связанных кубит тем он шире.
qw1
10.03.2018 19:19а Гугл и остальные хотят создать наподобие универсального процессора в обычных компьютерах
Интересно, какие физические принципы они планируют использовать?
Во всяких популярных публикациях по квантовым вычислениям нарисованы гейты, соединённые так, как требуется для решения задачи. А как физически планируется достигать таких конфигураций — никто почему-то не пишет.a5b
10.03.2018 19:40+3IBM немного описывал для своих систем (доступных в "облаке" "IBM Quantum Experience"), также построенных на сверхпроводящих кубитах — Superconducting quantum computing
IBM QX5: Albatross — 16 кубитов, 22 соединения (соединены далеко не все пары кубитов)
https://github.com/QISKit/ibmqx-backend-information/tree/master/backends/ibmqx5
Можно также поискать среди публикаций Martinis Group — Josephson Junction Quantum Computing at UCSB, т.к. они активно участвуют (руководят) в квантовых проектах Google https://web.physics.ucsb.edu/~martinisgroup/publications.shtml
https://web.physics.ucsb.edu/~martinisgroup/papers/Neill2017.pdf — 9 кубитов
https://web.physics.ucsb.edu/~martinisgroup/papers/Foxen2017.pdf — о проблемах связи в массивах более чем 2xN
2rage
10.03.2018 07:43+1Компьютеры D-Wave работают на принципе квантовой релаксации и решают крайне узкий спектр задач, в отличии от Google аналогов.
Tyusha
10.03.2018 10:24-1Вы совершенно правильно ставите вопрос: сколько из этих купит реально запутаны. Гугл скромно молчит, т.к. похвастаться, скорее всего, нечем.
Похоже, это просто массив 36 пар кубитов, которые работают одинаково, и коррекция ошибок достигается сравнением работы большого количества дублируются пар кубитов. А это, мягко говоря, совсем не одно и то же, что процессор из 72 связанных кубитов.
Убеждает меня в этом их график, что ошибки снижаются при росте числа "ихних" кубитов. В настоящем квантовой компьютере ошибки будут только нарастать с ростом количества кубитов, что очевидно.
Могу ошибаться, но перед нами 36 процессоров, каждый на двух кубитов, что является вчерашним днём квантовых компьютеров.
Ещё один мой аргумент против Гугл: компьютер, это видно, не криогенный. А большое количество настоящих кубитов сегодня достигается только вблизи нуля кельвинов.
Tyusha
10.03.2018 15:38Те, кто не согласен, можете как-то аргументировать вашу позицию, или слово Google, автоматически выводит их поделки из-под критики.
Sychuan
10.03.2018 16:06Убеждает меня в этом их график, что ошибки снижаются при росте числа «ихних» кубитов. В настоящем квантовой компьютере ошибки будут только нарастать с ростом количества кубитов, что очевидно.
Они используют корректировку ошибок с помощью кубитов, поэтому, чем больше кубитов, тем легче им корректировать ошибки: ". 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-кубитоном варианте)
Ещё один мой аргумент против Гугл: компьютер, это видно, не криогенный. А большое количество настоящих кубитов сегодня достигается только вблизи нуля кельвинов.
Не знаю, что там видно, но компьютер этот использует сверхпроводящие гейты. Что-то я сомневаюсь, что у ГУгла есть сверхпроводники при комнатной температуре.Tyusha
10.03.2018 16:16Они используют корректировку ошибок с помощью кубитов, поэтому, чем больше кубитов, тем легче им корректировать ошибки
Разумеется. Вот только они добавляют кубиты, которые многократно дублируют базовую ячейку. Грубо говоря, если из 36 ячеек 19 посчитали 2х2=4, а 17 ячеек посчитали 2х2=5, то стало быть, правильный ответ 4. В таком случае действительно, если наращивать число ячеек, вероятность ошибки будет падать. О чём они и говорят.
Это ни то же самое, что добавлять кубиты в запутанный набор. Их реально считающий квантовый компьютер состоит, по-видимому, всего из двух кубит. Остальное многократное резервирование для исправления ошибок.Kobalt_x
11.03.2018 09:54+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 логических
linuxover
10.03.2018 07:44-1а я пока не понимаю всей этой восторженной возни с квантовыми компьютерами. то есть пока не понимаю их преимуществ перед традиционными.
если говорить о программинге нейронов, то что такое нейрон? по сути дела — элемент выполняющий
f(x,k), где x — входное воздействие, а k — значение в памяти.
что такое нейронная сеть? это сеть имеющая множество перекрестных связей. То есть условноf(x,k)становитсяf(x1,x2,...xn,k).
В принципе когда надо запрограммировать много нейронов то процессоры быстро упираются в потолок производительности.
Но. Кто мешает выполнять нейроны на околопроцессорной периферии?
процессоры плохо выполняют нейроны. а те же ПЛИС по идее куда лучше к этому приспособлены. То есть на борт современного процессора просится блок с ПЛИС-архитектурой.
В своё время процессоры не умели (или плохо умели) математику. Делали математические сопроцессоры.
Сейчас по идее то же самое. Берем в качестве периферии — процессору ставим скажем варианты:
- сразу N аппаратных (на заранее программированной ПЛИС) нейронов в периферию (самый тяжкий путь).
- просто ПЛИС той или иной ёмкости, на которой можно размещать M сложных нейронов или N упрощенных или вообще что-то еще
- быстрый (N-вычислителей) вычислитель произвольной (в каких-то рамках) функции f(x,y) с DMA доступом в память
- нейроны можно считать на GPU
в общем и целом как бы дорог как программить ИИ на вполне современном железе у нас более чем достаточно. Появится спецпериферия — появятся и языки программирования ее (скажем ПЛИС на борту — программим на VHDL, а управляющую программу на C == тут захочется иметь язык который и то и сё программит).
мне кажется в современное время больше сложностей ЧТО и КАК программить на нейросетках, нежели НА ЧЕМ это делать.
какие задачи порешает тут квантовый комп? объясните на пальцах?
MarazmDed
10.03.2018 08:08-1Прелесть квантового компа в потенциальном преодолении экспоненциального взрыва: квантовый компьютер позволит решать NP-трудные задачи за вменяемое время… Правда для этого нужно количество кубит подтянуть до N. 72 кубита ну никак не порвут классические компы.
linuxover
10.03.2018 10:12-3но ведь и взять на борт современного CPU ПЛИСу, то точно так же это позволит решать NP-трудные задачи за вменяемое время.
вот вспомнить пресловутых майнеров. У них NP-трудная задача, а денег им хочется. Что они делают? берут ПЛИС, решают на ней эту NP-трудную задачу, затем оформляют ПЛИС как относительно недорогую микросхему и начинают копать.
это направление (ПЛИС на борту СPU) копается немного только в контроллерном применении, а в CPU «больших» машинок пока не копали совсем жеMarazmDed
10.03.2018 11:22+2но ведь и взять на борт современного CPU ПЛИСу, то точно так же это позволит решать NP-трудные задачи за вменяемое время.
Не позволит. Возьмем задачу коммивояжера. Ее можно решать точно для размерности N=1000. А вот уже для N=1001 она не решается — время решения уже неприемлемо долгое. И даже если вы при помощи ПЛИСов поднимете размерность до N=1001, то уже N=1002 будет недоступно даже для ПЛИСов. Я уж не говорю про энергозатраты такого мероприятия. В том-то и проблема экспоненциального взрыва, что на классических архитектурах вы упретесь в масштабирование.
вот вспомнить пресловутых майнеров. У них NP-трудная задача, а денег им хочется. Что они делают? берут ПЛИС, решают на ней эту NP-трудную задачу, затем оформляют ПЛИС как относительно недорогую микросхему и начинают копать.
Но никто из майнеров еще не решил проблему таким образом, чтобы для произвольной сложности сети быстро находилось решение.
Квантовые компьютеры, если они будут созданы (в чем есть сомнения), решат проблему экспоненциального роста сложности задач на корню. Не нужно будет для новой задачи строить АЭС и фермы для майнинга решения.linuxover
10.03.2018 14:49Не позволит. Возьмем задачу коммивояжера. Ее можно решать точно для размерности N=1000. А вот уже для N=1001 она не решается — время решения уже неприемлемо долгое. И даже если вы при помощи ПЛИСов поднимете размерность до N=1001, то уже N=1002 будет недоступно даже для ПЛИСов. Я уж не говорю про энергозатраты такого мероприятия. В том-то и проблема экспоненциального взрыва, что на классических архитектурах вы упретесь в масштабирование.
о, вот как раз занимаюсь по роду деятельности той самой задачей комивояжера.
у Вас ошибка: при размерности 1000 точно ее решать невозможно. Ибо у нее количество комбинаций от факториала зависит. Уже при размерности 10 ее решать точно нельзя (правда возможно у нас с Вами разница в терминологии и под "точно" Вы понимаете что-то другое, я имею ввиду — найти РЕАЛЬНЫЙ минимум, а не "что-то близкое к минимуму").
так вот, мы решаем ее следующим образом. Используем метод градиентного спуска с вероятностями выбора пути.
то есть строим маршрут по графу — выбор следующего по принципу "ближайший или с некоторой вероятностью случайный". Далее маршрут обсчитываем по оптимальности и цикл вертится пока маршрутов 10.000 не соберется или одна секунда не истечет. (для N=100 — 200) 10 тыс итераций примерно равно одной секунде.
Думали мы ускорять это на GPU, но из за майнеров хостинг с GPU сейчас очень дорогой, пока считаем кластерами CPU. Так вот: построение маршрута на ПЛИС ложится очень несложно (я уже копал немного эту тему): ПЛИС'а может делать эту задачу за один такт. Средняя современная ПЛИС по ёмкости в макроселлах может параллельно строить где-то 100-200 маршрутов за такт. То есть нужные (достаточные бизнесу) нам 10К итераций она сделает где-то за 100 тактов. Это в принципе очень круто, ускорение к тому что мы сейчас имеем — где-то три порядка.
но пока у нас это в стадии зачаточной находится.
В том-то и проблема экспоненциального взрыва, что на классических архитектурах вы упретесь в масштабирование.
так я и прошу помочь мне понять как квантовый компьютер мне поможет с той же задачей комивояжера?
я пока вижу что квантовый комп дает возможность относительно несложно программить нейроные слои. И тут сразу интересен вопрос: какая теоретическая сложность слоя возможна? нейронный слой это M связей N к 1, если внутри M зависимостей нет, то внутри N она как раз есть.
и простое традиционное программирование на квантовом компе будет доступно?MarazmDed
10.03.2018 16:38у Вас ошибка: при размерности 1000 точно ее решать невозможно
Возможно, методом ветвей и границ. Хотя, конечно, конкретная размерность, какую осилит метод ветвей и границ, сильно зависит от свойств самой задачи. Но N=1000 точно решается.
Уже при размерности 10 ее решать точно нельзя
Метод ветвей и границ а) точный, б) позволяет поднять размерность до 1000.
так вот, мы решаем ее следующим образом. Используем метод градиентного спуска с вероятностями выбора пути.
Есть, кстати, асимптотически точный алгоритм решения задачи коммивояжера. Т.е. вы сами задаете требуемую точность решения, и на выходе получаете соответствующую вычислительную сложность. Хотите точно — получите полный перебор, довольствуетесь 50% погрешности — решите за линейное время.
так я и прошу помочь мне понять как квантовый компьютер мне поможет с той же задачей комивояжера?
Квантовый алгоритм я Вам не напишу. Если не ошибаюсь, для гипотетического квантового компьютера разработали алгоритм, решающий задачу за линейное время. Идея в том, что экспоненциальная сложность не исчезает сама по себе. Просто квантовая природа прячет в себе экспоненту.
я пока вижу что квантовый комп дает возможность относительно несложно программить нейроные слои.
Да на фиг не нужен квантовый компьютер для нейросетей! Там нет вычислительно сложных задач. Нейросети — это как раз та штука, которая или на ПЛИС ложится, или на GPU.rPman
10.03.2018 16:47Да на фиг не нужен квантовый компьютер для нейросетей! Там нет вычислительно сложных задач. Нейросети — это как раз та штука, которая или на ПЛИС ложится, или на GPU.
Нет, если рассматривать процесс обучения в комплексе, он ложится на квантовый компьютер отлично, но к сожалению размерность сети потребует аналогичный порядок количества связных кубит.
Буквально на днях тут была статья-перевод какраз о попытках использования квантовых компьютеров именно для ускорения нейросетей и их обучения.MarazmDed
10.03.2018 18:12Нет, если рассматривать процесс обучения в комплексе, он ложится на квантовый компьютер отлично, но к сожалению размерность сети потребует аналогичный порядок количества связных кубит.
Еще раз: в нейросети нет экспоненциальной вычислительной сложности. алгоритм обучения — линейный (или квадратичный? не спец. Факт, что не экспоненциальный). На хрена использовать квантовые компы для обычных линейных алгоритмов?
Вам никто не запретит умножение двух чисел реализовать полным перебором, но это ведь попахивает идиотизмом? Тоже и с нейросетями.
red75prim
10.03.2018 17:25+1> Если не ошибаюсь, для гипотетического квантового компьютера разработали алгоритм, решающий задачу за линейное время.
Ошибаетесь. Квантовые алгоритмы, решающие NP-полные задачи, неизвестны.MarazmDed
10.03.2018 19:43-1Вы правы. Есть, например, реализация метода ветвей и границ к коммивояжеру, но, говорят, что от экспоненциальной сложности не спасает.
Kobalt_x
11.03.2018 10:54+1>Если не ошибаюсь, для гипотетического квантового компьютера разработали алгоритм, решающий задачу за линейное время. Идея в том, что экспоненциальная сложность не исчезает сама по себе. Просто квантовая природа прячет в себе экспоненту.
Общий случай TSP не BQP так что в общем случае будет вместо факториала, корень из него. Если известно, что веса рёбер имеют нормальное распределение, вот тогда только BQP
Во вторых вы ошибаетесь что на КК можно решать NPC задачи, ни одного алгоритма ускоряющиеся NPC задачи мне не известно. Задача факторизации не является NPC.
linuxover
12.03.2018 07:35> Да на фиг не нужен квантовый компьютер для нейросетей!
нейросеть это же отношение N к M. То есть многие ко многим. Именно поэтому слой из большого количества нейронов забирает мнооого CPU (перебор каждого на пересчет).
я думал квантовый комп эту проблему хорошо порешает, поэтому мне казалось что именно для программинга нейросеток он очень хорошо подходит.
> Там нет вычислительно сложных задач.
первоначально обычные компы задумывались как раз как способ решения вычислительных задач. а потом оказалось что основное применение компов — коммуникация и управление. а вычисления в целом менее нескольких процентов от всего остального :)
qw1
10.03.2018 19:31-1так я и прошу помочь мне понять как квантовый компьютер мне поможет с той же задачей комивояжера?
Если совсем грубо, перебирая варианты классическим компьютером, мы за 1 шаг можем из пункта A пойти в B, а за другой шаг — из A в C.
Используя квантовые вычисления, можно создать состояние суперпозиции, когда за один шаг мы пошли одновременно во все точки, достижимые из A (т.е. сразу в B, C, E, H, ...). За второй шаг — суперпозиция всех возможных маршрутов длины 2 (ABA, ABC, ACD, ADE, AEC, ...). Затем через N шагов происходит редукция и из всех состояний суперпозиции выживает то, которое оптимально. Его считываем как решение.
MarazmDed
11.03.2018 12:13у Вас ошибка: при размерности 1000 точно ее решать невозможно
Возможно, методом ветвей и границ. Хотя, конечно, конкретная размерность, какую осилит метод ветвей и границ, сильно зависит от свойств самой задачи. Но N=1000 точно решается.
Прошу пардону! Я Вас ввел в заблуждение. N=1000 действительно точно не решается. Метод ветвей и границ для точных решений осиливает N=100, т.е. в 10 раз меньше.
Akuma
10.03.2018 10:13Поидее ни один квантовый комп не порвет современные на современных же программах.
Когда-то давно еще читал, что для них и программирование отдельное, несовместимое с обычными ПК. Т.е. интерпретатор написать конечно же можно, но это будет тормозное чудовище как эмулятор PS4 например.
caveeagle
10.03.2018 10:24+1Языки уже давно существуют: Языки программирования для квантового компьютера
MarazmDed
10.03.2018 11:28+2Поидее ни один квантовый комп не порвет современные на современных же программах.
Мгновенно порвет на специфических задачах. NP-трудные задачи не имеют эффективных алгоритмов, а неэффективные алгоритмы могут искать решение дольше, чем существует Вселенная. Квантовые же компьютеры способны выдавать решение таких задач (для которых может потребоваться в миллиарды раз большее время, чем существует Вселенная), за несколько секунд.
Но все это при условии, что квантовые компьютеры будут созданы. Там тоже проблема масштабирования присутствует. Преодолеют — майнинг в прошлое уйдет. Как и вся цифровая экономика и приватность в интернете. Зато задача фолдинга белков будет решена, что круто :)rPman
10.03.2018 12:04Экономика и интернет адаптируются одними из первых еще ДО появления достаточно опасного квантового компьютера, уже сейчас разрабатываются алгоритмы шифрования, защищенные от этого.
MarazmDed
10.03.2018 12:33уже сейчас разрабатываются алгоритмы шифрования, защищенные от этого.
… Для которых как раз и требуются квантовые компьютеры, которые поломают классическую криптографию.rPman
10.03.2018 12:45Разные люди подразумевают под квантовым компьютером разные вещи, обычно считают саму возможность связывания кубитов, но с появления dwave стали называть квантовыми компьютерами системы, ограниченные по задачам и количеству одновременно связных кубит.
Полагаю вот от таких недо-квантовых квомпьютеров можно разрабатывать специализированную защиту, т.е. в этом смысле сначала должен быть создан такой компьютер.
Я же имею в виду что достаточно разработать защиту от универсального квантового компьютера.MarazmDed
10.03.2018 13:28+2Я же имею в виду что достаточно разработать защиту от универсального квантового компьютера.
Видимо, вы плохо представляете себе, на каких принципах работает современная криптография, раз употребляете слова «достаточно разработать».
Есть огромный класс задач, который называется «NP-трудные задачи». Особенность этого класса следующая:
1. На существующих архитектурах не найден эффективный алгоритм решения таких задач. Это не значит, что его не существует, но предполагают, что все же не существует. Иными словами, для таких задач есть один единственный алгоритм решения: полный перебор всех вариантов (подгонка под ответ). Сложность в том, что с ростом размерности задачи (самый важный параметр), количество вариантов для перебора растет очень быстро (экспоненциально быстро). И время решения задачи становится неприемлемо большим. Неприемлемо большим — это в число с тысячами нулями (я не знаю обозначений для таких числел) больше раз, чем существует вселенная.
2. Все задачи из класса NPC сводятся друг к другу за полиномиальное время (часто — за линейное). Это означает, что если хотя бы одна задача из этого класса будет решена (т.е. будет найден эффективный алгоритм, который будет выполняться за приемлемое время, вроде часов или лет, а не сроков существования Вселенной), то это автоматически будет означать, что решены ВСЕ задачи из класса NPC.
3. У вас есть задача и кто-то вам предлагает ответ. Вы можете быстро проверить, является ли ответ решением задачи или нет. Иными словами, для проверки вам не нужно создавать новых Вселенных, проверить вы можете за считанные секунды на обычных компьютерах.
Так вот, ВСЯ современная криптография основана на задачах из класса NPC: вы быстро можете перемножить пару случайно сгенерированных чисел. А вот разложить полученное число на множители вы уже быстро не можете: NP-трудная задача.
… И тут появляются квантовые компьютеры, которые умеют решать NP-трудные задачи за линейное время. Это означает, что ВСЕ АБСОЛЮТНО ЗАДАЧИ из класса NPC решаются за линейное время. Например, взлом 4096-битного шифра будет занимать не кучу времени, а всего-лишь 4096 тактов квантового компьютера.
И никакую защиту на КЛАССИЧЕСКИХ компьютерах вы не сможете придумать даже теоретически. И вот в этот момент и вся криптография и вся экономика, построенная на криптографии — рухнут. Поскольку все подписи, надежно идентифицирующие владельца, можно будет подделывать на здрасьте.
Можно ли разработать криптографию, устойчивую к взлому квантовыми компьютерами? Можно. Но для ее создания нужны квантовые компьютеры.
Ну т.е. представьте себя на месте ракового больного, которому осталось считанные дни жить. И он тут узнает, что появилось новое уникальное лекарство от рака, которое его вылечит. Одна беда. Получить такое лекарство он сможет минимум через 10 лет.
sumanai
10.03.2018 13:51+1И никакую защиту на КЛАССИЧЕСКИХ компьютерах вы не сможете придумать даже теоретически.
А разве алгоритмы на изогенных эллиптических кривых не устойчивы к перебору на квантовых компьютерах? При этом вполне считается на обычных ПК.MarazmDed
10.03.2018 14:06+1Не могу сказать. Да, на хабре была статья, что изогения спасет криптографию при появлении квантовых компьютерах. Так что, похоже, я не прав. Речь я вел про класс задач NPC, к какому классу относится криптография на изогенных эллиптических кривых — я не знаю.
sumanai
10.03.2018 14:19Я тоже не светоч разума в этой области, просто меня задела процитированная мною фраза, тогда как алгоритм Шора существенно ускоряет только один конкретный класс задач.
a5b
10.03.2018 19:48+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)
linuxover
10.03.2018 14:58… И тут появляются квантовые компьютеры, которые умеют решать NP-трудные задачи за линейное время.
вот этот момент я не понимаю совершенно.
почему на квантовом компе задача будет решена за линейное время?
давайте мы эмуляцию кубита запрограммим на обычном компе и будем решать за линейное время? почему нельзя?sumanai
10.03.2018 15:18+2почему на квантовом компе задача будет решена за линейное время?
Алгоритм Шора.
давайте мы эмуляцию кубита запрограммим
Любая эмуляция тормоза, а тут и не факт, что это вообще возможно заэмулировать.
MarazmDed
10.03.2018 16:44почему на квантовом компе задача будет решена за линейное время?
Потому что квантовый мир «прячет в себя» экспоненту. Суперпозиции, квантовая запутанность — это про то самое.
давайте мы эмуляцию кубита запрограммим на обычном компе и будем решать за линейное время? почему нельзя?
Когда вы будете эмулировать квантовую систему на классическом компьютере, ваша физическая «квантовая экспонента» развернется в вычислительную экспоненту. И эмулировать вы будете эту систему ровно столько же, сколько будете решать NP-трудную задачу на классическом компьютере.linuxover
10.03.2018 17:17> Потому что квантовый мир «прячет в себя» экспоненту. Суперпозиции, квантовая запутанность — это про то самое
вот этого «прячет в себя» я и не понимаю.
> Когда вы будете эмулировать квантовую систему на классическом компьютере, ваша физическая «квантовая экспонента» развернется в вычислительную экспоненту.
но тут есть одно интересное Но. Эмулируя кубит мы решаем ОДНУ вычислительную задачу. А решая ОДНУ задачу на обычном компе мы можем поискать способы оптимизации ее решения и выбрать какой-то который будет приемлем для эмуляции.
а потом на кубитах мы сможем решать множество NP-трудных задач.
если условно говоря на кубитах у нас имеется алгоритм решения, а на обычном такового нет, то эмуляция кубита дает алгоритм для обычного компа.
вот ту же задачу комивояжера на современных компах решают же 100500 способами. Да каждый из 100500 имеет свои ограничения, недостатки и в зависимости от обстоятельств кто-то выбирает один способ, кто-то другой…
плюс если бы кто-то написал эмулятор кубита, то во первых широкие массы получили бы доступ к возможности его (кубит) изучать, ну и заодно оптимизировать этот самый эмулятор.
как-то так.
почему в этом направлении работы не ведутся? есть еще неисследованная область какая-то?red75prim
10.03.2018 17:34+1плюс если бы кто-то написал эмулятор кубита, то во первых широкие массы получили бы доступ к возможности его (кубит) изучать, ну и заодно оптимизировать этот самый эмулятор.
Есть все эти эмуляторы. Поищите по "open source quantum computer emulator". Проблема в том, что требуемый объем памяти и время расчетов растет экспоненциально с ростом количества кубитов. Самая большая эмуляция — 51 кубит, кажется.
linuxover
10.03.2018 17:49во это уже интересно
> Самая большая эмуляция — 51 кубит, кажется.
дык вон в новостях — компы сейчас реальные делают на 16-70 кубит всего
MarazmDed
10.03.2018 19:20вот этого «прячет в себя» я и не понимаю.
Подозреваю, что полноценно никто не понимает. Квантовое состояние описывается суперпозицией квантовых состояний отдельных частиц. Ну т.е. про кота Шредингера будет описание вида «кот жив с вероятностью 0.5 и одновременно кот мертв с вероятностью 0.5». Когда количество запутанных частиц растет, описание квантовой системы растет с экспоненциальной сложностью. И при этом продолжает работать в реальном времени. :) Наша Вселенная не тормозит и не подвисает :)
А решая ОДНУ задачу на обычном компе мы можем поискать способы оптимизации ее решения и выбрать какой-то который будет приемлем для эмуляции.
И любой из этих способов будет сильно тормознее физической вселенной. Сильно — это в экспоненту раз.
а потом на кубитах мы сможем решать множество NP-трудных задач.
Исходя из неверной предыдущей посылки, неверны и все последующие рассуждения. Эмулировать Вселенную с достаточной скоростью не получится. Почему и придем к тому, что эмулятор даст только проигрыш по сравнению с классикой.
если условно говоря на кубитах у нас имеется алгоритм решения, а на обычном такового нет, то эмуляция кубита дает алгоритм для обычного компа.
Не так. на кубитах у нас имеется быстрый алгоритм (решает задачу за несколько тактов квантового процессора — времена меньше секунды), то на обычном компе у нас есть медленный алгоритм (для которого требуется в миллиард миллиард миллиард… (и т.д. миллиард раз)… миллиард раз больше времени, чем существует вселенная).
вот ту же задачу комивояжера на современных компах решают же 100500 способами.
И среди этих 100500 способов нет ни одного, который был бы а) быстрым и одновременно б) точным. Есть или точный, но для которого нужно стотыщмильярдов тысячелетий времени или есть быстрый, который даст решение вот прям щас, зато с погрешностью в два раза (что, кстати, круто, потому как ГАРАНТИРУЕТСЯ, что погрешность не хуже).
Иными словами: задача коммивояжера не решена.
На квантовом компьютере можно придумать алгоритм (вроде еще не придуман, но, кажется, что придумать его гораздо проще, чем решить проблему P<>NP). И тогда задача будет решаться за линейное время. (несколько секунд против стотыщмилярдов тысячелетий).
плюс если бы кто-то написал эмулятор кубита, то во первых широкие массы получили бы доступ к возможности его (кубит) изучать, ну и заодно оптимизировать этот самый эмулятор.
Вы правда хотите исследовать ФИЗИЧЕСКИЙ мир по эмуляции? :) Так-то кубиты и иже с ними изучают на ускорителях. Если вы про теорию, то эмуляцию написать нет проблем. На пару-тройку кубит вы эмулировать сможете. На большее у вас мощностей не хватит.
ну и заодно оптимизировать этот самый эмулятор.
Не думайте, что у вас получится оптимизировать эмулятор хоть сколько-нибудь значимо. Хотя бы потому что вы никак не избавитесь от экспоненциальной сложности описания состояния квантового компьютера.
почему в этом направлении работы не ведутся?
В какой именно? Эмуляция кубитов? Потому что тут нечего исследовать. Эмуляция вопросов не вызывает.linuxover
10.03.2018 20:05> Вы правда хотите исследовать ФИЗИЧЕСКИЙ мир по эмуляции? :)
ну исследуем же мы физический мир по виртуальным опытам (глядя на опыты на рисунках в учебнике физики или глядя на видеоопыты). Соответственно — почему нет?
MarazmDed
10.03.2018 20:07ну исследуем же мы физический мир по виртуальным опытам (глядя на опыты на рисунках в учебнике физики или глядя на видеоопыты). Соответственно — почему нет?
Для обучения — нет проблем. Для ученых — такой опыт не несет ничего нового.
tBlackCat
10.03.2018 19:17+1> Можно ли разработать криптографию, устойчивую к взлому квантовыми компьютерами? Можно. Но для ее создания нужны квантовые компьютеры.
А как же шифр Вернама от 1917 года и широко используемые во Второй Мировой одноразовые шифроблокноты?
В лучшем случае квантовый компьютер выдаст столь неудобоваримое количество расшифровок, что явно потребуется неудобное количество времени на анализ. Есть поговорка — гора родила мышь. В нашем случае с точностью до наоборот — мышь наложила кучу с Эверест.
Естественно, для непрерывных потоков данных сложно извратиться с подобным методом, но на то пусть голова болит у гуру. Криптостойкость метода заставит им воспользоваться в своё время.
zomby
10.03.2018 19:56Моего внутреннего параноика всегда напрягало, что во всех курсах, книгах и статьях на тему крипторграфии про шифр Вернама рассказывают в самом начале, в двух абзацах. Заключают, что он неудобен до полной невозможности им пользоваться на практике и вообще не нужен, используйте замечательный AES и забудьте, забудьте, забудьте про одноразовый блокнот. Почему? Выдаешь товарищу самую маленькую флешку со случайными данными — переписываться на всю жизнь хватит. Зато абсолютная теоретическая невскрываемость никем и никогда, это не круто разве?
tBlackCat
10.03.2018 20:40То, что шифр Вернама обходят стороной, вполне объяснимо. И что на него всего два абзаца отведено тоже понятно — он прост до безобразия.
В современной жизни, когда наблюдается засилие вычислительной техники, все стремятся к упрощению своей жизни и во главу угла поставлено пресловутое «баланс цены и качества».
С лёгкой руки математиков (им только дай волю порезвиться, разведут малину) были разработаны симметричные и не очень шифровальные методики, суть которых мы прекрасно знаем — невозможность современными средствами раскрыть зашифрованное в сроки, когда информация является актуальной. И теперь мы подходим к тому, что это изначально неправильное в глобальном масштабе направление подошло к грани теоретического провала.
С шифроблокнотами крайне сложно решить задачу передачи самого блокнота с гарантированным непопаданием его в чужие руки.
Второй неприятный момент — ёмкость блокнота. При современных потоках информации любой шифроблокнот весьма быстро истощится.
Третий момент связан со вторым. При необходимости генерации одноразового кода есть далеко ненулевая опасность повторения последовательности произвольной длины, а это абсолютно недопустимо. В той же Второй Мировой был зафиксирован факт вскрытия сообщения из-за ошибочного повторного использования старого кода. И это в условиях, когда про цифродробилки ни ухом, ни слухом.
> Заключают, что он неудобен до полной невозможности им пользоваться на практике, используйте замечательный AES.
Вот этот хвалёный AES и вкупе с ним и находятся сейчас на последнем издыхании. И современные методы шифрования имеют неустранимый критический недостаток. Провал шифровального механизма, ключей означает, что буквально вся перехваченная за многие лета информация будет прочитана, в отличии от попадания в чужие руки «странички блокнота». Да, одно сообщение будет раскрыто, но не более того. Разница налицо.
Если разобраться, то каждый метод имеет свою область применения.
red75prim
10.03.2018 12:54+2Пока ещё неизвестно могут ли квантовые компьютеры ускорить решение NP-полных задач, так что про NP-трудные задачи говорить рановато. О взаимосвязи класса сложности BQP с другими классами сложности пока мало что известно.
MarazmDed
10.03.2018 13:35Пока ещё неизвестно могут ли квантовые компьютеры ускорить решение NP-полных задач, так что про NP-трудные задачи говорить рановато.
Насколько я помню, есть квантовый алгоритм для факторизации чисел. Рассчитан такой алгоритм на идеальный квантовый компьютер, который выдает достоверные решения, а не с какой-то заданной вероятностью.
Другое дело, что пока что даже реальных квантовых компьютеров нет, не то, что идеальных. И да, есть большие сомнения, что таковые вообще будут созданы. Так что, да, есть подозрения, что классическая криптография еще поживет, вместе с насущными нерешенными проблемами вроде фолдинга белков.red75prim
10.03.2018 14:21+1Не было доказано, что факторизация — NP-полная (NP-complete) задача, то есть пока неизвестно, можно ли любую задачу из класса NP свести к разложению на множители.
Оригинальный алгоритм Шора выдает правильный результат с вероятностью 1/2 (см. arxiv.org/abs/quant-ph/0208183 ) на идеальном квантовом компьютере и это не имеет отношения к классу сложности. Реальные квантовые компьютеры вполне себе есть, например www.nature.com/articles/nature18648
Alex_ME
10.03.2018 11:42+2Если очень в общем виде объяснять (как дилетант дилетанту), то фишка в том, что из-за суперпозиции квантовый комьютер может осуществлять перебор различных вариантов одновременно. Надеюсь, более понимающие люди объяснять более корректно.
Но. Кто мешает выполнять нейроны на околопроцессорной периферии?
Так уже делают.
- GPU
- NVidia Volta с аппаратными "тензор-блоками"
- и не только, тысячи их
А ПЛИС… ПЛИС хорошо работают при конвейеризации вычислений, например, потоковой обработке сигналов. У сферического плиса в вакууме частоты существенно ниже, чем у современных ЦПУ
Alex_Q
10.03.2018 12:54+1У квантового компьютера важно не столько одновременность операций, сколько размерность пространства состояний.
К примеру, три классических бита имеют ОДНО из возможных 8 чисел (000, 001,...,111).
А система из трёх связанных кубит имеет 7 независимых комплексных параметров (один потеряли из-за нормировки).
И чем больше бит/кубит мы сравниваем, тем больше разница. И когда у нас система описывается таким большим количеством переменных, нам нужно больше математики что бы её описывать. НО мы можем пойти наоборот, и заставить систему описывать математические процессы. И тогда эта квантовая система сможет описывать больше математики.
Shkaff
10.03.2018 22:16Традиционный комментарий, лучшее объяснение работы квантового компьютера (то, о чем комментарий Alex_Q выше, чуть более подробно):
If you don't talk to your kids about quantum computing, someone else will.
Заодно категорически советую блог Скота Ааронсона про квантовые вычисления и иже с ним, он один из лучших объяснятелей, что там к чему.
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.Sychuan
11.03.2018 00:47Его книжка Quantum Computing since Democritus — очень мне понравилась. Всем рекомендую
Shkaff
Вы так написали, как будто они его уже построили, а это просто концепт:
Alex_Q
Если цитировать, то предложение целиком.
72 кубита это конечно недостаточно для решения real-world problems. Но тем не менее, эта штука всё таки физически существует. Там в статье даже фото некой Marissa Giustina возле этой микросхемы.
Shkaff
Я не имел ввиду количество кубитов, если там будет реально 72 кубитный компьютер — очень круто. Но пока я вижу набор проводков, громкие слова и никаких экспериментальных данных.
qbertych
Так они сами пишут про nearest neighbor connectivity. Из нового на нем разве что коррекцию ошибок отрабатывать — ну а что поделать, технология еще недалеко ушла от ловушек с двумя ионами.
Shkaff
Ну тут все понятно тоже. Мне просто показалось, что перевод статьи некорректен. В оригинале нигде не идет речь о работающем компьютере, даже для тестов корректировки ошибок.
quverty
Из того что пишут, выходит что реально построили. Просто об ошибках не надо забывать. Вопрос такие ли они «маленькие», чтобы реально что-то делать. Связность там примерно та же, что у Intel. Сам немного повозился только с IBM. Там у 16 кубитов вообще «лесенкой» 8х2. Люди даже на ней что-то делают, но у меня не особо выходило. Слишком быстро всё разваливается.
Shkaff
Ну я не знаю, я читаю их блог:
Из этого я не вижу иной интерпретации, кроме как что компьютер еще не в работе. Пока нет никаких экспериментальных данных, говорить о том, что "построили", смысла нет, так как с момента фабрикации платы до момента работы могут пройти годы.
quverty
Они пишут, что хотят получить тот же малый уровень ошибок. Я так понимаю, значит что-то работает. Иначе это вообще шутка не очень смешная — посмотрите сколько пошло комментариев по разным источникам. На моей памяти один кубит у IBM вдруг стал работать хуже раз в сто, потом через неделю исправили. Тут может что-то похожее.
Shkaff
Нет, ну в целом нормально — они могли представить на конференции концептуальный дизайн и первые идеи, как это должно работать. Это если основываться только на их источнике — блоге, а не заниматься гаданием. Они же не пишут: "мы построили новый компьютер", они пишут: "мы представили прототип и концепт, как он будет когда-нибудь хорошо работать для error correction".
quverty
C error correction не особо понятно — сейчас обычно обсуждаются схемы с сотнями, тысячами на каждый бит. Что там на 72 тестировать. Только Microsoft со своими топологическими кубитами надеется на десятки за счёт другой схемы работы.
Shkaff
Из всех алгоритмов пока в работе со многими кубитами особо ничего не показывали, все эти тысячи — только на бумаге. Кроме того, каждый тип кубитов требует разного подхода к коррекции ошибок. Если гугл работает со сверхпроводящими гейтами, им на них и коррекцию надо делать. Они хотят квантового превосходства от компьютера, т.е. 49 кубитов должны быть в работе, а остальные на коррекцию ошибок. Ну вот и будут тестировать, сколько им нужно понадобится.
quverty
Вот тут цитируют Мартиниса, что мол только что начали его тестировать.
Shkaff
Чтд, спасибо:) Но все равно дело хорошее, посмотрим, куда эта гонка КК нас приведет.