Hello Peter A van der Helm,

If not, why not use the concept of entropy?

I am not a computer scientist, but a physicist, especially in general relativity, thermodynamics, quantum physics and fluid mechanics. I hope my answer can help you.

A simple way would be to use Shannon's entropy (for classical bit information) and Von Neumman's entropy (for quantum information, in qubit). An article shows that his two entropies are the same concept, and that one can switch from one to the other.

RicksBradford (2008), Entropy and Its Concerns, Formulation of Quantum Mechanics QM6

http://rickbradford.co.uk/QM6Entropy.pdf

More precisely :

Shannon's entropy: Use in information theory Entropy is maximum when the events are equiprobable (p = 1 / n). Useful to know the uncertainty transmission of information via a channel; useful in classical cryptography for example.

Von-Neumann entropy: Same utility as Shannon, but used in quantum physics. It is a function of the probability p, or if formulated differently, as a function of the quantum density matrix. It measures uncertainty. Useful for determining the correlation rate between two entangled particles. Or know the uncertainty of receiving information from polarized photons. Widely used in quantum cryptography and the development of quantum computers.

Thanks to certain procedure related to the entropic calculation, one can "compress" data. Doubtless data compression can help minimize "cost" and reduce computing time.

Regards,

BAUDRIMONT Roman

Roman, the definition of information I use in my work is that from modern information theory (think of Kolmogorov complexity) rather than that from Shannon's classical information theory. It quantifies information not by its probability but by its content. So, I don't think the concept of entropy is directly useful to my purposes (although there certainly are some indirect links).

Furthermore, I agree with Fateh that there is a lot of wonderful and smart stuff in classical computing, but I think my question goes further than that.

My question rather is about the existence of deterministic combinatorial algorithms that a) perform a exhaustive search to obtain an optimal result, and b) reduce O(2^N) parts to O(1) parts. This may seem science-fiction (just as quantum computing still is), but in fact, I've already developed such an algorithm to do minimal coding within a modern information theoretical approach to human visual perception.

I see (rightly or wrongly?) the quantum computer as a hardware distributed representation that allows O(2^N) states to be processed in one go. My algorithm employs special software distributed representations (data structures) that also allow O(2^N) states to be processed in one go. In general, whether a problem can benefit from a specific distributed representation depends on the problem at hand, so, it might well be that mine cannot be used to solve the problems quantum computing can solve, and vice versa.

I am still developing/optimizing my algorithm further, but the focus of my question is on its theoretical implications, particularly regarding quantum computing. It challenges but does it also refute the often alleged general superiority of quantum computers over classical computers?

Dear Fateh, minimal coding is all about redundancy elimination -- in my algorithm, the redundancies are visual regularities such symmetry and repetition. My requirement to do this in an optimal way is precisely the cause of a combinatorial explosion, which the algorithm solves by employing those special distributed representations.