Hyperdense Coding Modulo 6 with Filter-Machines
| dc.creator | Grolmusz, Vince | |
| dc.date | 2003-06-11 | |
| dc.date.accessioned | 2026-07-07T03:19:48Z | |
| dc.date.available | 2026-07-07T03:19:48Z | |
| dc.description | We show how one can encode $n$ bits with $n^{o(1)}$ ``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 $\lceil{n/2}\rceil$ 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^{o(1)}$ 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\times n$ matrices with $n^{2+o(1)}$ 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^{2.376}$ multiplications. | |
| dc.identifier | https://arxiv.org/abs/cs/0306049 | |
| dc.identifier | http://arxiv.org/abs/cs/0306049 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31613 | |
| dc.subject | Computational Complexity | |
| dc.subject | Databases | |
| dc.subject | F.1.1 | |
| dc.title | Hyperdense Coding Modulo 6 with Filter-Machines | |
| dc.type | text |