Как стать автором
Обновить

Комментарии 17

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

А разве это не давно решённая задача?

Это сложности перевода и пересказа научной статьи. Оригинал https://www.quantamagazine.org/20121218-classical-computing-embraces-quantum-ideas/
"A quantum computing proof also led to a formula for the minimum length of error-correcting codes, which are safeguards against data corruption."


Указана ссылка на статью: http://homepages.cwi.nl/~rdewolf/publ/qc/qldc.pdf Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument


A locally decodable code encodes n-bit strings x in m-bit codewords C(x), in such a way that one can recover any bit x_i from a corrupted codeword by querying only a few bits of that word. We use a quantum argument to prove that LDCs with 2 classical queries need exponential length: m = 2^\Omega(n). Previously this was known only for linear codes (Goldreich et al. 02). Our proof shows that a 2-query LDC can be decoded with only 1 quantum query, and then proves an exponential lower bound for such 1-query locally quantumdecodable codes. We also show that q quantum queries allow more succinct LDCs than the best known LDCs with q classical queries. Finally, we give new classical lower bounds and quantum upper bounds for the setting of private information retrieval. In particular, we exhibit a quantum 2-server PIR scheme with O(n ^ (3/10) ) qubits of communication, improving upon the O(n (1/3)) bits of communication of the best known classical 2-server PIR.
Из статьи непонятно, то ли чип правда содержит 3 кубита, то ли там оптимизированная аппаратная эмуляция кубитов на базе традиционных технологий.

Если второе — то не понятно, зачем.


В ноуте 16 гигов оперативки, в чиселках вида complex<double> (2*8 байт) это 2^30.


Если эмулировать честно и считать в матрицах плотности, то в ноут влезет 14 кубит (15 уже заняло бы всю память одной матрицей, а нам надо как минимум три матрицы + система), с матрицами по 4 ГиБ.


Если хотеть считать быстро — то чуть меньше, надо считать производительность. Но даже если взять 10 — это надо будет перемножать матрицы 2^10 на 2^10, то есть всего 1024*1024, по 16 МиБ каждая.


Но один момент — для того, что называется квантовыми вычислениями (и собственно квантовым компьютером) матрицы плотности нам не нужны, достаточно векторов состояний. Там количество доступных кубит условно в два раза больше на ту же память, да и вектора надо хранить два всего. То есть с 20 кубитами на любом обычном ноуте вообще проблем никаких не будет, займёт это всё 32 МиБ в оперативке + код, и работать будет быстро. 28 кубит впихнуть по памяти в ноут реально, каждый из двух векторов займёт всё те же самые 4 ГиБ, но работать это будет медленно.


3 кубита моделируются матрицей 8*8 или вектором длины 8, в зависимости от того, что мы хотим. Смысла делать новость из эмуляции 3 кубитов нет никакого, поэтому логично предположить, что тут таки правда честные 3 кубита. Интерес к «честным» кубитам тоже вызван не там, чтобы 3 шт пихать в современные чипы, а ожиданием того, что в будущем, возможно, получится строить вычисления на большем количестве кубит, и за счёт этого обойти текущие вычислительные устройства.


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

Это чип c 3 кубитами и 2-х кубитным вентилем CNOT из новостей 2012 года — http://www.extremetech.com/extreme/120229-ibm-shows-off-quantum-computing-breakthroughs-says-qubit-computers-are-close "IBM shows off quantum computing advances, says practical qubit computers are close" February 28, 2012
http://www-03.ibm.com/press/us/en/pressrelease/36901.wss "IBM Research Advances Device Performance for Quantum Computing", 28 Feb 2012


In separate experiments, the group at IBM also demonstrated a more traditional “two-dimensional” qubit (2D qubit) device and implemented a two-qubit logic operation – a controlled-NOT (CNOT) operation, which is a fundamental building block of a larger quantum computing system. Their operation showed a 95 percent success rate, enabled in part due to the long coherence time of nearly 10 microseconds. These numbers are on the cusp of effective error correction schemes and greatly facilitate future multi-qubit experiments.
A picture of the Silicon chip housing a total of three qubits. The chip is back-mounted on a PC board and connects to I/O coaxial lines via wire bonds (scale: 8mm x 4mm). A larger assembly of such qubits and resonators are envisioned to be used for a scalable architecture.
Пара кубитов может быть комбинацией их всех


Кого «их всех»? Поясните пожалуйста.
Видимо, состояний, которые перечислены в предыдущем предложении.
Двухбитный контур классического компьютера может находиться в одном из четырёх состояний (0,0; 0,1; 1,0; 1,1). Пара кубитов может быть комбинацией их всех.


Если я правильно понял, то тут имеется в виду, что классический компьютер в конкретный момент времени может принимать одно из состояний, в то время как квантовый может принимать их все одновременно.
Состояний же. Состояние системы кубитов является в некотором смысле комбинацией всех возможных состояний системы из такого же количества битов.
квантовые компьютеры могут работать с любыми числами (положительными, отрицательными, действительными, мнимыми), в то время как классические компьютеры используют только действительные положительные числа.

Даже учитывая то, что текст упрощён и пытается быть ближе к людям, это какая-то ересь.


Где вы видели действительные положительные числа в компьютере? Если иметь ввиду «любыми» — то нет, не может. Если не любыми — то ограничение проведено некорректно. А вот почему «положительными» — не ясно. Чем положительные отличаются от отрицательных? Что мешает классическим работать со мнимыми? Причём тут это вообще?

подозреваю что речь идет о физической реализации и «действительные положительные числа» надо читать как «положительные целые числа», остальные числа в «классических компьютерах» эмулируются соглашениями через них, например отрицательные целые через соглашение — такой-то бит отвечает за знак числа.
> кубиты нужно разнести примерно на сантиметр друг от друга, чтобы операции с одним из них не влияли на остальные

А можно чуть подробнее про этот момент? Как они влияют и почему именно на сантиметр?
Очень интересный вопрос — почему кубиты рассматривают с точки зрения бинарной логики? Ведь у объектов квантового мира можно выделить много разных критериев, т.е. вместо двух состояний можно формально выделить 2^x состояний у одного кубита, со всеми вытекающими бонусами.

или это создает проблемы для запутывания? запутать можно только по одному свойству?

Потому что кубит — использует 2 собственных состояния и их суперпозиции. Для большего количества состояний — другое название, кутрит. Изучают (1), но с двоичными лучше проработана "элементная база" и с ними удобнее работать.

Двухбитный контур классического компьютера может находиться в одном из четырёх состояний (0,0; 0,1; 1,0; 1,1). Пара кубитов может быть комбинацией их всех.
Хотелось бы взглянуть на схему, что значит
комбинировать их все
?
В последнее время квантовые идеи помогли исследователям доказать безопасность многообещающих технологий шифрования под названием «криптография на решётках»


А вот например тут некоторые утверждают, что:
… британские криптографы уже давно, с начала 2000-х годов, занимаются разработкой квантово-безопасных алгоритмов, но и в подробностях описал одну из особо удачных, как казалось, схем такого рода – построенную в 2007 году на основе так называемых числовых циклических решеток. К сожалению, затем выяснилось, что данный криптоалгоритм – получивший от авторов имя Soliloquy – далеко не так силен, как предполагалось. В течение 2010-2013 годов для его эффективного взлома была придумана теоретическая атака с помощью квантового компьютера, а потому в итоге от алгоритма пришлось полностью отказаться.
При этом важно, что решение о полном отказе – а не об усилении-модернизации красивой конструкции – было в основном принято спецслужбой из-за очень мощной и сильно впечатлившей англичан атаки, разработанной в 2013 году группой исследователей открытого академического сообщества. В работе этих авторов (K. Eisentraeger, S. Hallgren, A. Kitaev, and F. Song. «A quantum algorithm for computing the unit group of an arbitrary degree number field». In STOC ACM, 2014) описывается существенно новая квантовая атака весьма общего типа, накрывающая, в частности, широкий круг «постквантовых» криптосхем, включая и никому неведомый в ту пору Soliloquy…

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