Computer Science – Computational Complexity
Scientific paper
2003-06-11
Computer Science
Computational Complexity
Scientific paper
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 $\Omega(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.
No associations
LandOfFree
Hyperdense Coding Modulo 6 with Filter-Machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Hyperdense Coding Modulo 6 with Filter-Machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hyperdense Coding Modulo 6 with Filter-Machines will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-408094