Вы, случайно, не разобрались ещё, откуда у 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 кубитами как было с ИБМ.
Зато там «measurement-induced» схема для «non-Clifford gate». Опять вероятностная, более того, практически аналогичный подход применяется для классической симуляции квантового компьютера тут, так что достигая универсальности они при этом не обязательно будут считать быстрее классического симулятора. Но, на самом деле, это тоже было бы неплохо.
Я про обзорную и спросил — они пишут, мол вероятность успеха возрастает при использовании телепортации и приводят две ссылки. Во второй действительно можно найти что-то по теме, но это именно так называемая телепротация гейта и я о нём и писал. Просто хочется понять, откуда в принципе у них вдруг всё заработает. Правда они ещё и об «one-way» квантовых вычислениях пишут. Но это вообще отдельная тема.
В статье, которую вы процитировали выше, Фурусава с коллегой, похоже, пишут о телепортации квантовых вентилей, предложенной в 1999. Когда одного из её авторов спросили, зачем это, он ответил, что это может быть полезно для переноса вентиля на архитектуру, где его проще выполнить. Так что, подразумевается использовать наряду с фотонами и ещё что-то другое?
насколько я помню, с фотонами некоторые «гейты», необходимые для универсальности, «просто» можно реализовать только вероятностным (non-deterministic) образом, то есть потери идут после каждого и получается экспоненциальное затухание пропорционально количеству таких «гейтов».
Если для 50 «идеальных» кубитов требуется суперкомпьютер, страшно представить, что будет, когда туда все алгоритмы регистрации и коррекции добавить.
Недавний прогноз, обсуждаемый в MIT Technology Review около месяца назад ссылался на электронный препринт How To Factor 2048 Bit RSA Integers In 8 Hours Using 20 Million Noisy Qubits и вызвал даже некий оптимизм, так как до этого были оценки с миллиардами и более. Но при этом, даже если принять обещание ИБМ об удвоении числа кубитов каждый год, то получится что с их 20 более-менее нормально работающими кубитами надо ждать 20 лет. Но возможно, Microsoft со своим Q# надеется на топологические кубиты и на то, что коррекция ошибок на них требует меньших издержек.
Не совсем понял ваш комментарий по поводу отсутствия arXiv в подборке. Мою тематику он хорошо перекрывает, так что очень часто им пользуюсь. Когда читал, надеялся найти что-то похожее по возможностям — то есть, помимо названий и аннотаций нужны и сами тексты, причём нормального качества. Но, насколько я понял, в списке либо библиографические базы, которые содержат ссылки на статьи (а те уже, в основном, платные), либо, как вы сами верно подметили академические социальные сети, где можно почти что угодно выкладывать.
Я имею в виду, что обраттимые вычисления, как там Франк и другие пишут, просто позволяют повысить тактовую частоту (что, как уже написал, вообще не учитывается во всяких классах).
В зависимости от определения можно говорить и «уже давно» (ДНК — не по теме правда, если вспомнить определение логического кубита) или «вообще никогда» (точными они никогда не будут). На всякий случай, я про теорию только писал.
Сколько до лимита Ландауэра осталось, действительно оценки разные, я когда-то смотрел, сейчас нашёл только прошлогоднюю статью Франка, который активно продвигает обратимые вычисления, где он говорит о десяти годах, правда как-то очень косвенно упоминая этот принцип, хотя в той-же википедии пишут о 2050 годе.
Проблема в том, что это формальные модели, по физике сложно всё это соотносить с реальными системами.
Недавний прогноз, обсуждаемый в MIT Technology Review около месяца назад ссылался на электронный препринт How To Factor 2048 Bit RSA Integers In 8 Hours Using 20 Million Noisy Qubits и вызвал даже некий оптимизм, так как до этого были оценки с миллиардами и более. Но при этом, даже если принять обещание ИБМ об удвоении числа кубитов каждый год, то получится что с их 20 более-менее нормально работающими кубитами надо ждать 20 лет. Но возможно, Microsoft со своим Q# надеется на топологические кубиты и на то, что коррекция ошибок на них требует меньших издержек.