Hyperdense Coding Modulo 6 with Filter-Machines

Original · EN

We show how one can encode n bits with nᵒ⁽¹⁾ ``wave-bits'' using still hypothetical filter-machines (here o(1) denotes a positive quantity which goes to 0 as n goes to infity). Our present result - in a completely different computational model - significantly improves on the quantum superdense-coding breakthrough of Bennet and Wiesner (1992) which encoded n bits by n/2 quantum-bits. We also show that our earlier algorithm (Tech. Rep. TR03-001, ECCC, See ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/2003/TR03-001/index.html) which used nᵒ⁽¹⁾ muliplication for computing a representation of the dot-product of two n-bit sequences modulo 6, and, similarly, an algorithm for computing a representation of the multiplication of two n× n matrices with n²⁺ᵒ⁽¹⁾ multiplications can be turned to algorithms computing the exact dot-product or the exact matrix-product with the same number of multiplications with filter-machines. With classical computation, computing the dot-product needs Ω(n) multiplications and the best known algorithm for matrix multiplication (D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput., 9(3):251--280, 1990) uses n².³⁷⁶ multiplications.