Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata

Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma +1

We consider the possibility of encoding m classical bits into much fewer n quantum bits so that an arbitrary bit from the original m bits can be recovered with a good probability,…