Я сильно не вникал, но как я понимаю, это принципиально другой способ перебора, а не принципиально другой алгоритм. Если вы распараллелите перебор на K ядер, то временная сложность тоже будет не просто N, а N/K.
Чисто формально, там используются так называемые асимптотические оценки сложности (“О большое”, кстати, на всякий случай, бесплатная версия статьи есть в виде препринта arxiv.org/abs/1611.09347 ), так что “константы” вроде K на них не влияют.
Но в принципе, в этой работе действительно идея квантовых алгоритмов используется скорее формально, когда они просто вставляются для ускорения в традиционные классические методики. Но вообще, для примера, посмотрите хотя бы на алгоритм Гровера, который используется как основа для “медленных” квантовых алгоритмов (с корнем) и увидите, что там вообще никакого перебора нет, вообще сам подход другой. Просто это оказывается спрятанным в изначально классических методиках машинного обучения.
Но ускорение перебора это не принципиально другой способ решения задачи, это тот же самый перебор, то есть используется тот же самый алгоритм.
Посмотрите Box 1 Table — если бы использовался перебор, там бы в графе «speedup» корни и тем более логарифмы от N не стояли бы, а был бы просто N. Так что решается именно «принципиально другим способом», хотя это не обязательно должно иметь отношение к вопросу о сознании, которому данная работа действительно и не посвящена.
В этом смысле превосходство, конечно, наступило: если самый мощный классический компьютер размерном с несколько футбольных полей за несколько дней считает то, что один из первых КК за несколько минут — это вполне превосходство.
Несколько футбольных полей получается, если классический компьютер ставится в заведомо неравное положение – он должен посчитать, да ещё и сохранить в памяти 2^n комплексных амплитуд, а квантовое устройство N раз выдать строчку из n битов. А представьте, если бы от квантового компьютера потребовалось произвести полную томографию данного состояния для получения всех этих амплитуд или хотя бы квадратов их модулей соответствующих вероятностям. Для этого надо было бы сделать N много больше 2^n и тогда уже и КК пришлось бы затратить огромное время, который и классический компьютер должен затратить если использовать другой метод расчёта без требования держать все амплитуды в памяти, упомянутый в частности в работах Ааронсона.
Ладно, действительно, это всё скорее предмет серьёзной профессиональной дискуссии.
Наличие КК не является прямым доказательством невозможности создать классический алгоритм.
Если вернуться к книге `т Хоофта, то в разделе 5.8 посвящённом квантовому компьютеру он пишет, что КК может опровергнуть (фальсифицировать) те модели КА которые он рассматривает. Он закончил главу так:
If engineers ever succeed in making such quantum computers, it seems to me that the CAT is falsified; no classical theory can explain perfect quantum computers.
Тут надо всю книгу внимательно прочитать, чтобы дискутировать идеи `т Хоофта, но так как известно, что квантовые КА не входят в противоречие с КК, получается что модели, которые он подразумевает, это не они, а классические КА. Тогда всё это возвращает нас к вопросу о “квантовом превосходстве”, который не так давно обсуждался в связи с другим постом.
Мой посыл такой: в первом приближении это квантовое превосходство. И без подробностей физики не имеет смысла идти дальше первого приближения. Во втором приближении, уже можно обсуждать, в каком смысле это КП.
Тут может быть некая проблема с терминами. Судя по всему, понятие КП (quantum supremacy) изначально подразумевало, что ситуация, в которой оно будет достигнуто, не должна вызывать особых разногласий. Джон Прескилл даже специально разъяснял, почему другие термины вроде преимущества (advantage) не очень подходят для описания его идеи. Мол, нежелательно оказаться в ситуации, подобной результату скачек, когда лошади пришли к финишу с минимальным отрывом и нельзя говорить о безусловной победе.
Так что при таком КП не должны были бы возникать проблемы с необходимостью рассмотрения разных подробностей и приближений. Однако, в случае с Google не похоже, что получилось именно это. Вспомнить хотя бы отношение IBM ко всей этой истории. Вот в IBM как раз о “квантовом преимуществе” любят рассуждать.
Используя аналогию со скачками, можно сравнить такие исследования с ситуацией, когда участники соревнования вообще идут к финишу по разным дорогам. Что собой представляет “квантовая дорога” не вполне понятно, а “классическая дорога” – это алгоритм, который был использован при оценке времени выполнения на суперкомпьютере. Но раз по самому определению КП задача не обязательно должна быть в чём-то полезной, то возможно никто и не пытался разрабатывать для неё оптимальные классические алгоритмы.
Сейчас задача привлекла дополнительное внимание и вполне могут появиться новые идеи по поводу возможности ускорения её выполнения на обычных компьютерах. Так что я бы не торопился с заявлениями о том, достигнуто КП или нет.
Далее, эта статья — вообще не аргумент в обсуждении КП гугла: они сами прямо пишут об этом: «RCS (т.е. алгоритм гугла) does notfit nicely into our analysis».
Вот, кстати, появилась более поздняя работа с частично перекрывающимся коллективом авторов (включая и Далзела) уже и по моделированию RCS.
Если посмотреть ту публикацию, по поводу которой был разговор, то там уже в аннотации написано о том, что они подразумевают P≠NP без всякой “экзотики”. То есть “базовый уровень” по такой терминологии. Правда, об эксперименте Google сказаны только общие слова, раздел 5.2. Если я правильно понял, то они считают, что 53 кубита пока до превосходства не дотягивают, хотя и близко. Вроде, общая идея как раз та, что написана и тут в самом конце:
«При отсутствии шума аргументы в пользу квантового вычислительного превосходства выглядят убедительно, — говорит Далзел. – Но добавьте шум – и тогда у классического алгоритма появится нечто, чем он может воспользоваться».
То есть тут разговор не о каких-то необычных предположениях типа P=NP, так как в этом случае и без шума бы были проблемы.
Не сказал бы, что именно это утверждается в данной статье. Уже в самом начале пишут, что мол это зависит от точки зрения. Ещё обратите внимание на параграф, где написано:
… Я, правда, не уверен в том, что не существует пока ещё неизвестного нам классического алгоритма, который позволил бы нам воспроизвести их эксперимент, или даже ещё более крупную его версию, на реалистичном классическом устройстве. …
Была идея изучить Julia на «базовых задачках» из области квантовой информации (квантовые вычисления — слишком громко сказано), так как Qiskit на Python или там Q#, на которых пытался что-то делать не всегда устраивают. Да и проекты есть, но пока вроде никто не собирается их финансировать. Но я так и не понял, может ли Julia вообще «взлететь» именно в этой области? Вроде мало прецедентов, если сравнивать с тем же Python, да и некоторыми другими языками.
Тоже смотрел этот проект в своё время. Но не особо преуспел в попытках применения. Со всякими квантовыми вычислениями и «около них» на Julia ещё вот тут уже длительное время что-то пытаются делать. Как раз на днях пытался разобраться.
Вы, случайно, не разобрались ещё, откуда у Google это специфическое распределение берётся и при чём там лазеры «XEB is based on the observation that the measurement probabilities of a random quantum state have a similar pattern to laser „speckles“, ...»
Разве несколько недель? В «пропавшем отчёте» было написано: «On Google Cloud servers, we estimate that performing the same task for m = 20 with 0.1% fidelity using the SFA algorithm would cost 50 trillion core-hours and consume 1 petawatt hour of energy.»
Там этот кусок представляет достаточно естественную часть текста, так как текст скорее не про «квантовое превосходство» вообще, а про новость о проверке «превосходства» тем способом, которым сделал Google и в непереведённом куске есть полезная информация по истории вопроса.
Кто их знает — пытался в своё время доступ получить, не ответили пока. Monroe через 8 дней будет в Москве выступать в рамках дня бесплатных лекций, может запись потом выложат.
С другой стороны я не понимаю как можно распараллеливать гровера
Гровер работает на задачах прямого перебора, так что если у вас есть n квантовых компьютеров, то каждому передаётся своя часть задачи и вся задача решается в n раз быстрее. Такое распараллеливание, как и скорость работы вообще не рассматривается в оценках с O большое, они же специально делаются для возможности оценить сам алгоритм, а не железо.
Обратимость вычислений мне казалось лишь мешает ускорению операций.
Я имею в виду, что обраттимые вычисления, как там Франк и другие пишут, просто позволяют повысить тактовую частоту (что, как уже написал, вообще не учитывается во всяких классах).
Когда ожидать реализаций кв.комп с временем существования более 1 миллисекунды и размером в тысячи логических (точных) кубитов?
В зависимости от определения можно говорить и «уже давно» (ДНК — не по теме правда, если вспомнить определение логического кубита) или «вообще никогда» (точными они никогда не будут). На всякий случай, я про теорию только писал.
Про отсутствие практических применений — это смотря каких. Гровер при фиксированном быстродействии даёт возможность квадратичного увеличения количества вариантов перебора. Пример с ключами в этом отношении просто для использования Гровера не особо удачен. Наример, вместо 2^64 квантовый компьютер может перебрать 2^128 вариантов какой-то переборной задачи, то есть классическому с таким же быстродействием на это потребовалось бы в 2^64 раз больше времени. В миллиарды миллиардов раз. Да ещё обратимость может помочь скорость как таковую увеличить. Просто для перебора ключей и это не помогает.
Сколько до лимита Ландауэра осталось, действительно оценки разные, я когда-то смотрел, сейчас нашёл только прошлогоднюю статью Франка, который активно продвигает обратимые вычисления, где он говорит о десяти годах, правда как-то очень косвенно упоминая этот принцип, хотя в той-же википедии пишут о 2050 годе.
— идеальный квантовый компьютер обратим и поэтому не греется вообще. Про неидеальный сложно что-то говорить, но по крайней мере для обратимых вычислений нет проблемы с принципом Ландауэра к которому современные системы, вроде, уже подошли почти вплотную.
Но в принципе, в этой работе действительно идея квантовых алгоритмов используется скорее формально, когда они просто вставляются для ускорения в традиционные классические методики. Но вообще, для примера, посмотрите хотя бы на алгоритм Гровера, который используется как основа для “медленных” квантовых алгоритмов (с корнем) и увидите, что там вообще никакого перебора нет, вообще сам подход другой. Просто это оказывается спрятанным в изначально классических методиках машинного обучения.
Ладно, действительно, это всё скорее предмет серьёзной профессиональной дискуссии.
Тут надо всю книгу внимательно прочитать, чтобы дискутировать идеи `т Хоофта, но так как известно, что квантовые КА не входят в противоречие с КК, получается что модели, которые он подразумевает, это не они, а классические КА. Тогда всё это возвращает нас к вопросу о “квантовом превосходстве”, который не так давно обсуждался в связи с другим постом.
Тут может быть некая проблема с терминами. Судя по всему, понятие КП (quantum supremacy) изначально подразумевало, что ситуация, в которой оно будет достигнуто, не должна вызывать особых разногласий. Джон Прескилл даже специально разъяснял, почему другие термины вроде преимущества (advantage) не очень подходят для описания его идеи. Мол, нежелательно оказаться в ситуации, подобной результату скачек, когда лошади пришли к финишу с минимальным отрывом и нельзя говорить о безусловной победе.
Так что при таком КП не должны были бы возникать проблемы с необходимостью рассмотрения разных подробностей и приближений. Однако, в случае с Google не похоже, что получилось именно это. Вспомнить хотя бы отношение IBM ко всей этой истории. Вот в IBM как раз о “квантовом преимуществе” любят рассуждать.
Используя аналогию со скачками, можно сравнить такие исследования с ситуацией, когда участники соревнования вообще идут к финишу по разным дорогам. Что собой представляет “квантовая дорога” не вполне понятно, а “классическая дорога” – это алгоритм, который был использован при оценке времени выполнения на суперкомпьютере. Но раз по самому определению КП задача не обязательно должна быть в чём-то полезной, то возможно никто и не пытался разрабатывать для неё оптимальные классические алгоритмы.
Сейчас задача привлекла дополнительное внимание и вполне могут появиться новые идеи по поводу возможности ускорения её выполнения на обычных компьютерах. Так что я бы не торопился с заявлениями о том, достигнуто КП или нет.
Вот, кстати, появилась более поздняя работа с частично перекрывающимся коллективом авторов (включая и Далзела) уже и по моделированию RCS.
Я имею в виду, что обраттимые вычисления, как там Франк и другие пишут, просто позволяют повысить тактовую частоту (что, как уже написал, вообще не учитывается во всяких классах).
В зависимости от определения можно говорить и «уже давно» (ДНК — не по теме правда, если вспомнить определение логического кубита) или «вообще никогда» (точными они никогда не будут). На всякий случай, я про теорию только писал.
Сколько до лимита Ландауэра осталось, действительно оценки разные, я когда-то смотрел, сейчас нашёл только прошлогоднюю статью Франка, который активно продвигает обратимые вычисления, где он говорит о десяти годах, правда как-то очень косвенно упоминая этот принцип, хотя в той-же википедии пишут о 2050 годе.