Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 18
Если учесть, что ключи шифрования в 64 бита уже давно считаются крайне ненадежными без всяких квантовых вычислений, то гугловские 53 кубита не выглядят превосходством.
Давеча переводил я тут FAQ, где разбирается довольно подробно, почему это все же превосходство.
В Вашем же переводе в последнем вопросе отвечающий всё ещё не уверен, что это превосходство:
Я же лишь говорю, что в моём понимании это превосходством не выглядит. Я так считаю потому, что не показано ничего, чего не может показать классический вычислитель уже давно и за меньшие деньги. Собственно, и комментируемая статья — об этом же. Это действительно движение в сторону превосходства, но ещё не само оно.
Если это действительно достигнутое квантовое превосходство, то, я думаю...Тут всё зависит от определения «превосходства», если кто-то определит своё превосходство похожестью на себя, то да — он будет всегда превосходить всех.
Я же лишь говорю, что в моём понимании это превосходством не выглядит. Я так считаю потому, что не показано ничего, чего не может показать классический вычислитель уже давно и за меньшие деньги. Собственно, и комментируемая статья — об этом же. Это действительно движение в сторону превосходства, но ещё не само оно.
В Вашем же переводе в последнем вопросе отвечающий всё ещё не уверен, что это превосходство:Просто на тот момент еще не было официального объявления о достижении гугла, поэтому автор был аккуратен в формулировках. Возможно, мой перевод неудачен, т.к. в оригинале это довольно явно.
Тут всё зависит от определения «превосходства», если кто-то определит своё превосходство похожестью на себя, то да — он будет всегда превосходить всех.квантовое превосходство — это термин с конкретным определением:
quantum supremacy is the goal of demonstrating that a programmable quantum device can solve a problem that no classical computer can feasibly solve (irrespective of the usefulness of the problem).
квантовое превосходство — это термин с конкретным определениемСогласен. Но разве ж я упоминал где-то слово «квантовое»?
Тогда извиняйте. Статья обсуждает квантовое превосходство, и ваш комментарий выглядел как относящийся к превосходству, описанному в статье. Квантовые компьютеры достигли квантового превосходства, но это, конечно, не делает их полезными пока.
Квантовые компьютеры достигли квантового превосходства …Не сказал бы, что именно это утверждается в данной статье. Уже в самом начале пишут, что мол это зависит от точки зрения. Ещё обратите внимание на параграф, где написано:
… Я, правда, не уверен в том, что не существует пока ещё неизвестного нам классического алгоритма, который позволил бы нам воспроизвести их эксперимент, или даже ещё более крупную его версию, на реалистичном классическом устройстве. …
Не сказал бы, что именно это утверждается в данной статье.В данной статье не утверждается, это мои слова. Вы правы, нет однозначного доказательства, что классический компьютер никогда не сможет достичь такой же мощности. Может быть, P=NP, и тогда КК вообще не может дать выигрыша в принципе. Однако, в рамках нынешнего понимания, это маловероятно. Собственно, Ааронсон конкретно этот случай разбирает в статье тут, где объясняется, почему это можно считать квантовым превосходством.
То есть, мне кажется, тут может быть два уровня обсуждения: базовый и узко-специальный. На базовом уровне во всех смыслах КК достигли квантового превосходства, и именно на этом уровне ведутся обсуждения в научно-популярных статьях. На узко-специальном уровне можно говорить об условиях, которые для этого должны выполняться в природе (условно, P≠NP), и какова вероятность того, что они не выполняются. Но на этом уровне нужно и вести обсуждение с учетом всех трудностей сравнения классов сложности.
Если посмотреть ту публикацию, по поводу которой был разговор, то там уже в аннотации написано о том, что они подразумевают P≠NP без всякой “экзотики”. То есть “базовый уровень” по такой терминологии. Правда, об эксперименте Google сказаны только общие слова, раздел 5.2. Если я правильно понял, то они считают, что 53 кубита пока до превосходства не дотягивают, хотя и близко. Вроде, общая идея как раз та, что написана и тут в самом конце:
«При отсутствии шума аргументы в пользу квантового вычислительного превосходства выглядят убедительно, — говорит Далзел. – Но добавьте шум – и тогда у классического алгоритма появится нечто, чем он может воспользоваться».То есть тут разговор не о каких-то необычных предположениях типа P=NP, так как в этом случае и без шума бы были проблемы.
То есть “базовый уровень” по такой терминологии.Я про категории говорил относительно научно-популярного текста выше, а не научной публикации. Мой посыл такой: в первом приближении это квантовое превосходство. И без подробностей физики не имеет смысла идти дальше первого приближения. Во втором приближении, уже можно обсуждать, в каком смысле это КП. Но обсуждения на этом уровне — это уже научная дискуссия, в которой нужные четкие аргументы в виде вычислений и статей и подготовки, которой, например, у меня нет.
Далее, эта статья — вообще не аргумент в обсуждении КП гугла: они сами прямо пишут об этом: «RCS (т.е. алгоритм гугла) does notfit nicely into our analysis». Дальше они пишут о разнице в подходах к определению КП. Они не пишут, что гугл не достиг КП, а только что в их подходе они дают оценку на большее количество необходимых для КП кубитов. Но при этом эта оценка довольно специальная, и они не могут точно сделать какое-либо заключение о гугле. Но это детали. Очевидно, эта аргументация гораздо глубже, чем та, с чего начался тред тут.
Мой посыл такой: в первом приближении это квантовое превосходство. И без подробностей физики не имеет смысла идти дальше первого приближения. Во втором приближении, уже можно обсуждать, в каком смысле это КП.
Тут может быть некая проблема с терминами. Судя по всему, понятие КП (quantum supremacy) изначально подразумевало, что ситуация, в которой оно будет достигнуто, не должна вызывать особых разногласий. Джон Прескилл даже специально разъяснял, почему другие термины вроде преимущества (advantage) не очень подходят для описания его идеи. Мол, нежелательно оказаться в ситуации, подобной результату скачек, когда лошади пришли к финишу с минимальным отрывом и нельзя говорить о безусловной победе.
Так что при таком КП не должны были бы возникать проблемы с необходимостью рассмотрения разных подробностей и приближений. Однако, в случае с Google не похоже, что получилось именно это. Вспомнить хотя бы отношение IBM ко всей этой истории. Вот в IBM как раз о “квантовом преимуществе” любят рассуждать.
Используя аналогию со скачками, можно сравнить такие исследования с ситуацией, когда участники соревнования вообще идут к финишу по разным дорогам. Что собой представляет “квантовая дорога” не вполне понятно, а “классическая дорога” – это алгоритм, который был использован при оценке времени выполнения на суперкомпьютере. Но раз по самому определению КП задача не обязательно должна быть в чём-то полезной, то возможно никто и не пытался разрабатывать для неё оптимальные классические алгоритмы.
Сейчас задача привлекла дополнительное внимание и вполне могут появиться новые идеи по поводу возможности ускорения её выполнения на обычных компьютерах. Так что я бы не торопился с заявлениями о том, достигнуто КП или нет.
Далее, эта статья — вообще не аргумент в обсуждении КП гугла: они сами прямо пишут об этом: «RCS (т.е. алгоритм гугла) does notfit nicely into our analysis».Вот, кстати, появилась более поздняя работа с частично перекрывающимся коллективом авторов (включая и Далзела) уже и по моделированию RCS.
Однако, в случае с Google не похоже, что получилось именно это.В случае с гуглом получилось, что они не знали про другой вариант классического алгоритма, который теоретически позволил бы посчитать то же на самом мощном суперкомпьютере в мире. Что характерно, если бы гугл имел на 1 кубит больше, уже без шансов было бы.
Тут может быть некая проблема с терминами.Проблема в том, что термин не определен точно. Квантовое превосходство по идее должно было стать точкой невозврата во времени: вот до нее КК были слабее классических, а после — сильнее, и дальше этот разрыв только наращивался бы. В этом смысле превосходство, конечно, наступило: если самый мощный классический компьютер размерном с несколько футбольных полей за несколько дней считает то, что один из первых КК за несколько минут — это вполне превосходство.
В статье выше авторы пытаются зайти с другой стороны и строго математически доказать квантовое превосходство для конкретной задачи в конкретном смысле превосходства. Только с их позиции нельзя точно сказать насчет достижения превосходства гуглом — алгоритм не позволяет (насколько я понял).
Вспомнить хотя бы отношение IBM ко всей этой истории.Отношение IBM понятно — они прямые конкуренты гугла, и у них из-под носа вырвали победу, причем немного не «чисто». Вот они и бухтят.
Но раз по самому определению КП задача не обязательно должна быть в чём-то полезной, то возможно никто и не пытался разрабатывать для неё оптимальные классические алгоритмы.Идея в том, что выбирается такая задача, у которой есть только один подход — брутфорс. Либо квантовый, либо классический. Ааронсон по ссылке выше разбирает, что для этих алгоритмов при определенных предположениях можно точно показать, что не может быть классического алгоритма, который справится быстрее. Точного доказательства в самом общем случае нет, конечно, но это общая проблема для всех этих алгоритмов.
Вот, кстати, появилась более поздняя работа с частично перекрывающимся коллективом авторов (включая и Далзела) уже и по моделированию RCS.Но у них там вроде тоже другой подход немного (shallow vs deep), как я понял:
«Can one approximately simulate random 2D circuits of arbitrary depth? This is the rele-vant case for Google’s quantum computational supremacy experiment [Aru+19]. AssumingConjecture 2, our algorithms are not efficient once the depth exceeds some constant, but itis not clear if this difference in apparent complexity for shallow vs. deep circuits is simplyan artifact of our simulation method, or if it is inherent to the problem itself.»
В этом смысле превосходство, конечно, наступило: если самый мощный классический компьютер размерном с несколько футбольных полей за несколько дней считает то, что один из первых КК за несколько минут — это вполне превосходство.Несколько футбольных полей получается, если классический компьютер ставится в заведомо неравное положение – он должен посчитать, да ещё и сохранить в памяти 2^n комплексных амплитуд, а квантовое устройство N раз выдать строчку из n битов. А представьте, если бы от квантового компьютера потребовалось произвести полную томографию данного состояния для получения всех этих амплитуд или хотя бы квадратов их модулей соответствующих вероятностям. Для этого надо было бы сделать N много больше 2^n и тогда уже и КК пришлось бы затратить огромное время, который и классический компьютер должен затратить если использовать другой метод расчёта без требования держать все амплитуды в памяти, упомянутый в частности в работах Ааронсона.
Ладно, действительно, это всё скорее предмет серьёзной профессиональной дискуссии.
Да, я тут точно выхожу за пределы своей компетенции. Собственно, мой-то посыл в другом несколько вообще, он не столько о науке, сколько о научпопе. Вокруг КК и так слишком много хайпа и непонимания. Объяснение результатов гугла должно вестись на общем уровне так, чтобы оно не усугубляло положение. Поэтому если меня спросят ответить одним словом на вопрос, было ли достигнуто квантовое превосходство, я отвечу «да». На мой взгляд, тут хотя бы разобраться с базовыми вещами. С другой стороны, в профессиональном разговоре вполне уместно обсуждать все детали. Так как все началось с вопроса явно довольно общего, я подошел к этому с общих позиций.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сколько кубитов нужно для квантового превосходства?