On the Quantum Complexity of Classical Words
Published on Nov 30, 20072662 Views
We show that classical and quantum Kolmogorov complexity of binary words agree up to an additive constant.Both complexities are defined as the minimal length of any (classical resp. quantum) computer