Комментарии 26
Насколько я видел — не опубликовали.
Ваша статья прояснила в чём соль всего одним предложением: «Центральная идея заключается в том, чтобы использовать квантово-распределенные ключи в шифре Вернама — одноразовом блокноте.» — идея теперь понятна, спасибо!
"раньше требовалось тридцать лет при анализе на квантовом компьютере"
Wat?
Алгоритм Шора работает не самым тривиальный образом. Для конкретного примера потребуется много места и разъяснений, но общая схема в том, чтобы свести задачу к поиску периода некоторой функции. Эту задачу квантовый компьютер может решить эффективно. На вики достаточно подробно описан сам алгоритм.
За quantum computing скрывается на самом деле теорема о запрете клонированияНе совсем понял — ведь формально, теорема о запрете клонирования следует из линейности квантовой механики. С другой стороны, в нелинейных версиях квантовой механики возможны модели вычислений даже более мощные, чем в линейной. Получается, запрет клонирования даже мешает и сложность с квантовыми алгоритмами заключается ещё и в том, как понять, почему, несмотря на такую помеху, они всё-таки могут превосходить классические.
Только не дискретное фурье, а квантовое 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.
Только не дискретное фурье, а квантовоеЭто без особой разницы. Там частный случай обычного дискретного Фурье. Оно является унитарной матрицей, так что применяется без особых изменений. Надо найти период функии, для этого используют её спектр. Квантовость уже в других тонкостях начинает проявляться. Например, возможность эффективной реализации этого преобразования с помощью квантовых вентилей, возможность компактной записи через кубиты и т.д.
Алгоритм Шора был разработан Питером Шором в 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
Важно отметить, что задача поиска в неупорядоченной базе данных носит универсальный характер — к ней можно свести практически любую другую задачу (в том числе и NP-полную). Однако для её решения потребуется количество запросов, растущее экспоненциально с ростом сложности задачи (в рассмотренном примере, ей соответствовал параметр n). Таким образом, не стоит относиться к квантовому компьютеру как к всемогущему инструменту, способному решать произвольные вычислительные задачи с экспоненциальным ускорением.
Не стоит относиться к NP-полным задачам, как к чему-то нерешаемому. Некоторые NP-полные задачи решаются эвристически: существуют алгоритмы без доказательств, которые подтверждены опытом и работают на практике. Пример: поиск минимума спуском по градиенту.
В академическом сообществе тоже была создана система из 51 кубита — это удалось группе Михаила Лукина (выпускника Физтеха и главы Международного консультативного совета Российского квантового центра) на основе ультрахолодных нейтральных атомов, а также система из 53 кубитов от группы Кристофера Монро из Университета Мэрилэнда, который также является основателем компании IonQ, разрабатывающей коммерческий квантовый компьютер на ионах.
Я не совсем понимаю, почему люди выдирают из контекста именно эти числа. Во-первых, насколько я знаю, логические кубиты — это больше концепция, чем реальность. Во-вторых, Кристофер сумел только 3 кубита с полным набором гейтов. Насколько мне известно, больше чем 3 ещё никто не сумел.
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%.
Как квантовый компьютер может взломать современные системы шифрования и снизить стоимость выработки аммиака?