Search All Applications in Quantum Computing
Application US20050216544
Published 2005-09-29
Dense And Randomized Storage And Coding Of Information
We describe a method for dense encoding of information. Bennet and Wiesner (Phys. Rev. Lett. 69:2881-2884, 1992), using EPR-pairs, showed that n bits can be encoded by n/2 quantum-bits, from which the original bits can be retrieved. Here, in a completely different (non-quantum) setting, we give a method for more dense encoding: In our method n bits x1,x2, . . . ,xn are mapped by a linear transform B over the 6-element ring Z6 to numbers z1,z2, . . . ,zt from ring Z6 with t=no(1)(i.e., much fewer numbers) (Quantity o(1) here denotes a positive number which goes to 0 as n goes to infinity), then, by applying another linear transform C to these zi's, we will get back n elements of ring Z6, x′1,x′2, . . . ,x′n, where, e.g., x′1 may have the form x′1=x1+3x2+4x3. One can get back x1 simply by running through the values of xi on the set 0,1,2,3,4,5, and noticing that only x1 has period 6, (3x2 has period 2, 4x3 has period 3). Our results generalize for any non-prime-power composite number m instead of 6. We also apply this method for fast computation of matrix multiplication and for compacting and extending matrices with linear transforms.
Much More than Average Length Specification
View the Patent Matrix® Diagram to Explore the Claim Relationships
USPTO Full Text Publication >
- 1. A method for dense encoding and retrieving of information represented in electronic computers, the method comprising
(a) choosing an appropriate modulus m, positive integer n, corresponding to the number of bits to be encoding, and generating n×n matrix A with integer elements where the diagonal elements of A differs modulo m from all the other elements of their column, and where A can be written as matrix product BC where B is an n×t matrix, C is a t×n matrix, where t is less than n; (b) encoding the length-n vector x to the length-t vector xB, by vector-matrix product modulo m; (c) storing the length-t vector xB in physical computational devices; (d) retrieving the stored vector by computing xBC=xA by vector-matrix product modulo m; (e) for every coordinate of vector xBC=xA, filtering out the terms added as the linear combination of other coordinates of vector x.
- 6. A system for dense encoding and retrieving of information represented in electronic computers or other physical devices, the system comprising
(a) choosing a modulus m to be a non-prime-power composite positive integer, positive integer n corresponding to the number of bits to be encoded, and generating n×n matrix A with the diagonal elements being non-zero modulo any prime-divisors of m, and each non-diagonal elements of matrix A are zero modulo for at least one prime divisor of m, and where A can be written as matrix product BC where B is an n×t matrix, C is a t×n matrix, where t is less than n; (b) choosing step-functions s1,s2, . . . ,sn on the [a,b] real interval, corresponding to time, such that the following properties hold: (b1) function si has finitely many, but at least one non-zero steps modulo m, for i=1,2, . . . ,n; (b2) step of function si is either 0 modulo m or it is non-zero modulo all individual prime-divisors of number m, for i=1,2, . . . ,n; (b3) no two different functions si and sk have non-zero steps in the same point r in the real interval [a,b]; (c) by denoting the n bits to be stored by h1,h2, . . . ,hn, bit hi is encoded first as xi=hisi, for i=1,2, . . . ,n; (d) with matrix B, z=xB is computed; (e) step functions z1,z2, . . . ,zt are stored; (f) x′=zC=xBC modulo m is computed; (g) by observing the change of the values of the piecewise constant function xi′, we conclude that if all the steps of function xi′ are 0 modulo at least one prime divisor of m, then hi=0, otherwise, hi=1.
- 10. A method for computing the product of the n×n matrix X and the n×n matrix Y, the method comprising:
(a) the column compacting of matrix X is done by computing BTX; (b) the row compacting of matrix Y is done by computing YB; (c) from the t×n matrix BTX={uij} and from the n×t matrix YB={vkl} the t×t matrix W={wil} is computed as:
wil={circumflex over (l)}£tj=1({circumflex over (l)}£nk=1bkjuik)({circumflex over (l)}£nk=1cjkvkl);
(d) the column expanding process is done by computing CTW; (e) the row expanding process is done by computing CTWC; (f) a filtering process is done for retrieving the values of the product matrix.
