Классические компьютеры перенимают квантовые идеи

Это сложности перевода и пересказа научной статьи. Оригинал 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.

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

В ноуте 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 собственных состояния и их суперпозиции. Для большего количества состояний — другое название, кутрит. Изучают (1), но с двоичными лучше проработана "элементная база" и с ними удобнее работать.