Наличие КК не является прямым доказательством невозможности создать классический алгоритм.
Если вернуться к книге `т Хоофта, то в разделе 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 годе.
— идеальный квантовый компьютер обратим и поэтому не греется вообще. Про неидеальный сложно что-то говорить, но по крайней мере для обратимых вычислений нет проблемы с принципом Ландауэра к которому современные системы, вроде, уже подошли почти вплотную.
Ну, Ааронсон пишет о том, что в сфере его научных интересов. Посмотрел вот у Нильсена и Чанга — в их книге эта тема занимает всего несколько страниц из 800+, то есть процент или около того. Да и сам подход с такой оценкой сложности полученной минимальной модификацией теории используемой для обычных компьютеров вызывает вопросы.
Если даже более активно искать, всё равно не факт, что получится найти по этой теме что-то более-менее внятно изложенное. Но по поводу предыдущего комментария – там, наверное, не совсем про то. Всё таки “квантовое превосходство” – это попытка найти и предъявить хоть что-нибудь квантовое, что выполняется быстрее, даже не обязательно полноценные квантовые вычисления. С другой стороны, как раз по поводу формального превосходства квантового компьютера по всяким классам сложности, тот же Gil Kalai из “скептиков” вроде не спорит – по крайней мере, в комментариях к своему недавнему посту в Facebook он на вопрос по этому поводу ответил
I am certainly willing [...] to take for granted that that BQP is larger than BPP.
Проблема в том, что это формальные модели, по физике сложно всё это соотносить с реальными системами.
Я бы не сказал, что данная работа сильно помогает разобраться. Вообще, если пытаться использовать подход с точки зрения всяких классов вычислительной сложности, то приходится вспомнить, что там нет точного доказательства превосходства квантового компьютера над классическим, если уж пускаться во всякие формальности:
Quantum Computers have been proved to be more powerful than classical.Wrong.
This has been repeated many times and is often claimed in the literature. But there is no mathematical proof that a quantum computer that runs in polynomial quantum time cannot be simulated in polynomial classic time. None. Let me repeat that. There is no such proof. [...]
В первом случае еще написано (я по пре-принту статьи в arXiv), что та самая анцилла приготовляется вероятностно и запоминается в квантовой памяти. А во втором случае, тот самый «one-way» — то есть с детерминизмом не вполне понятно, так как измерение всегда вероятностно. Так что надо либо очень много разбираться, либо просто ждать результата хотя бы с 3-5 кубитами как было с ИБМ.
Тут надо всю книгу внимательно прочитать, чтобы дискутировать идеи `т Хоофта, но так как известно, что квантовые КА не входят в противоречие с КК, получается что модели, которые он подразумевает, это не они, а классические КА. Тогда всё это возвращает нас к вопросу о “квантовом превосходстве”, который не так давно обсуждался в связи с другим постом.
Тут может быть некая проблема с терминами. Судя по всему, понятие КП (quantum supremacy) изначально подразумевало, что ситуация, в которой оно будет достигнуто, не должна вызывать особых разногласий. Джон Прескилл даже специально разъяснял, почему другие термины вроде преимущества (advantage) не очень подходят для описания его идеи. Мол, нежелательно оказаться в ситуации, подобной результату скачек, когда лошади пришли к финишу с минимальным отрывом и нельзя говорить о безусловной победе.
Так что при таком КП не должны были бы возникать проблемы с необходимостью рассмотрения разных подробностей и приближений. Однако, в случае с Google не похоже, что получилось именно это. Вспомнить хотя бы отношение IBM ко всей этой истории. Вот в IBM как раз о “квантовом преимуществе” любят рассуждать.
Используя аналогию со скачками, можно сравнить такие исследования с ситуацией, когда участники соревнования вообще идут к финишу по разным дорогам. Что собой представляет “квантовая дорога” не вполне понятно, а “классическая дорога” – это алгоритм, который был использован при оценке времени выполнения на суперкомпьютере. Но раз по самому определению КП задача не обязательно должна быть в чём-то полезной, то возможно никто и не пытался разрабатывать для неё оптимальные классические алгоритмы.
Сейчас задача привлекла дополнительное внимание и вполне могут появиться новые идеи по поводу возможности ускорения её выполнения на обычных компьютерах. Так что я бы не торопился с заявлениями о том, достигнуто КП или нет.
Вот, кстати, появилась более поздняя работа с частично перекрывающимся коллективом авторов (включая и Далзела) уже и по моделированию RCS.
Я имею в виду, что обраттимые вычисления, как там Франк и другие пишут, просто позволяют повысить тактовую частоту (что, как уже написал, вообще не учитывается во всяких классах).
В зависимости от определения можно говорить и «уже давно» (ДНК — не по теме правда, если вспомнить определение логического кубита) или «вообще никогда» (точными они никогда не будут). На всякий случай, я про теорию только писал.
Сколько до лимита Ландауэра осталось, действительно оценки разные, я когда-то смотрел, сейчас нашёл только прошлогоднюю статью Франка, который активно продвигает обратимые вычисления, где он говорит о десяти годах, правда как-то очень косвенно упоминая этот принцип, хотя в той-же википедии пишут о 2050 годе.
Проблема в том, что это формальные модели, по физике сложно всё это соотносить с реальными системами.