Как квантовый компьютер может взломать современные системы шифрования и снизить стоимость выработки аммиака?

[alexfedorov_q]

Пока результаты скромные. С помощью алгоритма Шора факторизовано число 15 (https://doi.org/10.1038%2F414883a) и 21 (https://doi.org/10.1038%2Fnphoton.2012.259). Пока это далек ото того, чтобы что-то взламывать. Но это не единственный способ как на квантовом компьютере выполнять задачу факторизации. Например, есть алгоритм вариационной квантовой факторизации, там достижимы большие значения. Прилагаю таблицу :-)

[quverty]

Еще одна подборка «рекордов» есть в ответе здесь. Но в алгоритме Шора для факторизации 56153 потребовалось бы порядка 32 кубитов, а не 4. Вроде, электронный препринт с этой таблицей за 4 года так и не опубликовали в каком-нибудь журнале?

[alexfedorov_q]

Да, поэтому как Вы видите, там написано не Shor, а minimization — реализуется несколько другой алгоритм, которому требуется меньшее число кубитов. Я приводил выше — одним из примеров является вариационная факторизация.

Насколько я видел — не опубликовали.

[alexfedorov_q]

Вариационная факторизация — arxiv.org/abs/1808.08927

[quverty]

Да. Просто до этого табличка была из более ранней статьи с другим подходом, по которой была достаточно неоднозначная реакция. Я и удивился немного.

[cuwHuk]

del

[PQR]

Недавно видел какой-то ролик с центрального телевидения про квантовый телефон для госслужащих/военных, разработанный при МГУ, стоимостью несколько сотен тысяч рублей, который при этом работает максимум на 20км. Вопросы «нафига?» и откуда берётся дополнительная безопасность не покидали всё время. Было полное ощущение традиционной телевизионной лапши и распила бюджета.

Ваша статья прояснила в чём соль всего одним предложением: «Центральная идея заключается в том, чтобы использовать квантово-распределенные ключи в шифре Вернама — одноразовом блокноте.» — идея теперь понятна, спасибо!

[iig]

"раньше требовалось тридцать лет при анализе на квантовом компьютере"

Wat?

[alexfedorov_q]

Имеется ввиду следующее. Несколько лет назад чтобы решить задачу о моделировании молекулы Fe2S2 на квантовой компьюетере (абстрактном, но с фискрованной «мощностью») потребовалось бы 30 лет. Исключительно за счет того, что алгоритм для моделирования был улучшен время выполнения задачи (на том же самом квантовом компьютере) сократилось до двух минут.

[iig]

Я так и не понял, смоделирована ли эта молекула.

[alexfedorov_q]

Нет

[iig]

Но рост производительности впечатляет.

[alexfedorov_q]

За quantum computing скрывается на самом деле теорема о запрете клонирования :-) Один из ключевых результатов квантовой теории информации: произвольное квантовое состояние нельзя скопировать.

Алгоритм Шора работает не самым тривиальный образом. Для конкретного примера потребуется много места и разъяснений, но общая схема в том, чтобы свести задачу к поиску периода некоторой функции. Эту задачу квантовый компьютер может решить эффективно. На вики достаточно подробно описан сам алгоритм.

[quverty]

За quantum computing скрывается на самом деле теорема о запрете клонирования

Не совсем понял — ведь формально, теорема о запрете клонирования следует из линейности квантовой механики. С другой стороны, в нелинейных версиях квантовой механики возможны модели вычислений даже более мощные, чем в линейной. Получается, запрет клонирования даже мешает и сложность с квантовыми алгоритмами заключается ещё и в том, как понять, почему, несмотря на такую помеху, они всё-таки могут превосходить классические.

[quverty]

С физикой можно ещё как-то разобраться на простых операциях с одним и двумя кубитами, а алгоритм Шора достаточно сложный. Там и возведение в степень и дискретное преобразование Фурье.

[a5b]

Только не дискретное фурье, а квантовое http://ru.wikipedia.org/wiki/Квантовое_преобразование_Фурье — Quantum Fourier transform

Неплохое описание основ и алгоритмов (только "логические кубиты" без физических реализаций) — Kaye, Laflamme, Mosca. An Introduction to Quantum Computing
На русском есть краткий видеокурс https://ru.coursera.org/learn/kvantovyye-vychisleniya, или 100 стр. брошюра 2010 года http://old.kpfu.ru/eng/departments/ktk/RESOURCE/posobie.pdf или http://yury.name/modern/09.pdf + http://yury.name/modern/10.pdf

Общие выводы про влияние кв.комп.алг. Шора на криптографию:
https://logic.pdmi.ras.ru/~sergey/teaching/crypto10/12-quantum.pdf

В результате получается квантовое решение задачи дискретного логарифма.
Эллиптические кривые не спасают — для любой коммутативной группы работает, нужно только умножать уметь

Мы взломали всю коммутативную криптографию. Что делать?
Один ответ: строить квантовую криптографию.
Другой ответ: строить некоммутативную криптографию

Физических реализаций одиночных кубитов несколько, но далеко не все из них выполняют критерии DiVincenzo: "Она должна представлять собой массив квантовых объектов с возможностью добавления новых элементов (масштабируемость), квантовое состояние этой системы не должно быстро разрушаться, нужно уметь приводить систему в определенное начальное состояние (инициализация), выполнять логические операции над отдельными кубитами и парами кубитов (универсальные операции) и надежно измерять конечное квантовое состояние системы." (цитата по Бетеров Баулин 2015)

Небольшой обзор физических кубитов, Andrew Daley,2014:
http://quantum.phys.cmu.edu/QCQI/QC_CMU1
http://quantum.phys.cmu.edu/QCQI/QC_CMU2
Сейчас часто используют сверхпроводниковые кубиты (слайд 33 QC_CMU2; Superconducting_quantum_computing): имеют быстрое время срабатывания операции (нс), но декогерируют (теряют квант.состояние) за единицы мкс; есть возможность создания интерфейсов в СВЧ, оптику, ионы. Не очень удобно производить массивы кубитов с развитыми связями между ними (планарный техпроцесс по ниобию — 2-хмерные сетки связей — 9 q. G., 16 q. IBM, 7, 17, 49 q. Intel "Tangle Lake", the magic inside, 72q G.). Пример — сверхпроводящее кольцо с потоковым кубитом — квантовым состоянием является направление тока, измерение через SQUID, управление СВЧ сигналами, связывание магнитными полями. Другой пример — зарядовые кубиты — количество куперовских пар внутри сверхпр. "острова", управление напряжениями, чтение транзистором или СВЧ полем.
Как только возникают буквы СВЧ квантовокомпьютерный чип внезапно обрастает свч разъёмами — https://newsroom.intel.com/news/intel-advances-quantum-neuromorphic-computing-research/ (108 разъёмов для 49 кубитов), к которым требуется подключить столько же СВЧ-сверхпроводников (проводов), которые уже скоро перестанут пролезать в технологические отверстия криогенного холодильника (10 милликельвинов, гелий3, 1млн$ за холодильник). Провода имеют тенденцию перегревать кв.чип и спрос на них превышает предложение. https://www.technologyreview.com/s/612760/quantum-computers-component-shortage/ "We’d have more quantum computers if it weren’t so hard to find the damn cables"

Then there are those superconducting cables that carry the signals used to control qubits. These are specially designed to conduct very little heat so that they don’t disrupt qubits’ delicate quantum state inside the fridges. Johnson says just one main manufacturer supplies them, a Japanese company called Coax Co.

[quverty]

Только не дискретное фурье, а квантовое

Это без особой разницы. Там частный случай обычного дискретного Фурье. Оно является унитарной матрицей, так что применяется без особых изменений. Надо найти период функии, для этого используют её спектр. Квантовость уже в других тонкостях начинает проявляться. Например, возможность эффективной реализации этого преобразования с помощью квантовых вентилей, возможность компактной записи через кубиты и т.д.

[leonidru]

Все носятся с этой ТЕОРИЕЙ как дурень со ступой :). Пока же существует эмуляция этих состояний на стандартном железе. Соответственно со всеми присущими ему ограничениями. Это как говорить о нейронных вычислениях эмулируя работу нейронов на обычном компе.

[blind_oracle]

На 3+ кубитов есть в железе реализованные системы, которые работают по этой ТЕОРИИ. Проблема в том что на практике толку от них не много, а больше кубитов удерживать сложно.

[leonidru]

Эти «кубиты», по факту, разом рандомно меняют состояние которое можно считать? Получили x=RND() ок. Где тут «вычислитель», где связанные (спутанные) состояния и т.д.

[blind_oracle]

Странные какие-то вопросы.

Алгоритм Шора был разработан Питером Шором в 1994 году. Семь лет спустя, в 2001 году, его работоспособность была продемонстрирована группой специалистов IBM. Число 15 было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами.

(с) ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A8%D0%BE%D1%80%D0%B0

[geisha]

Важно отметить, что задача поиска в неупорядоченной базе данных носит универсальный характер — к ней можно свести практически любую другую задачу (в том числе и NP-полную). Однако для её решения потребуется количество запросов, растущее экспоненциально с ростом сложности задачи (в рассмотренном примере, ей соответствовал параметр n). Таким образом, не стоит относиться к квантовому компьютеру как к всемогущему инструменту, способному решать произвольные вычислительные задачи с экспоненциальным ускорением.

Не стоит относиться к NP-полным задачам, как к чему-то нерешаемому. Некоторые NP-полные задачи решаются эвристически: существуют алгоритмы без доказательств, которые подтверждены опытом и работают на практике. Пример: поиск минимума спуском по градиенту.

В академическом сообществе тоже была создана система из 51 кубита — это удалось группе Михаила Лукина (выпускника Физтеха и главы Международного консультативного совета Российского квантового центра) на основе ультрахолодных нейтральных атомов, а также система из 53 кубитов от группы Кристофера Монро из Университета Мэрилэнда, который также является основателем компании IonQ, разрабатывающей коммерческий квантовый компьютер на ионах.

Я не совсем понимаю, почему люди выдирают из контекста именно эти числа. Во-первых, насколько я знаю, логические кубиты — это больше концепция, чем реальность. Во-вторых, Кристофер сумел только 3 кубита с полным набором гейтов. Насколько мне известно, больше чем 3 ещё никто не сумел.

[a5b]

9 и 16 кубитов делали, 49 заявлял интел. IBM давал доступ к своим кв.комп, особенно к младшим:
https://quantumexperience.ng.bluemix.net/
https://www.research.ibm.com/ibm-q/technology/experience/
https://github.com/Qiskit
ТТХ:
5 кубитов https://github.com/Qiskit/ibmq-device-information/tree/master/backends/tenerife/V1
https://github.com/Qiskit/ibmq-device-information/tree/master/backends/yorktown/V1
16 кубитов https://github.com/Qiskit/ibmq-device-information/tree/master/backends/rueschlikon/V1
14 кубитов https://github.com/Qiskit/ibmq-device-information/tree/master/backends/melbourne/V1

Обзор железа и симуляторов в доступе — https://arxiv.org/pdf/1807.02500.pdf
по IBMQX5 (16к) приводят точность однокубитовых гейтов 99,5%, двухкубитовых 95%, длительность 1к гейта 80 нс, 2к гейта около 260+-90нс, длительность существования состояния в 30-90 тыс. нс (мкс, т.е. порядка сотен операций). Ошибки чтения 6%.