Quantum logic as a basis for computations (Q1586480)

Lately, several algorithms have been proposed which use quantum mechanical phenomena to speed up computations. These initial successes make researchers believe that there is a great potential in using quantum effects in computing. To analyze these future potential possibilities, the author starts analyzing the problem of quantum computation from the foundational viewpoint. Traditional (non-classical) computations are based on binary logic; adders and other elements of modern computers are formed from logical ``gates'' which implement basic logical operations. Similarly, quantum mechanics can be described in terms of quantum logic. It is therefore reasonable to analyze what we would be able to compute if we had quantum ``gates'' which implement operations of quantum logic. In particular, an interesting result is related to the implementation of an approximately known number like ``nearly 3''. At first glance, since 3 is usually represented, in a computer, as \(011_2\), it makes sense to implement ``nearly 3'' by using three bits, one ``almost 0'' and two ``almost 1'' 's. The drawback of this approach is that while the intuitive meaning of ``nearly 3'' includes 4 (\(=100_2\)), the probability of changing all three bits to get 4 is extremely small. The author therefore proposes to use, instead of a normal binary representation, special codes (called Gray codes) in which the code for \(n+1\) differs from a code for \(n\) in only one bit. It is worth mentioning that, in contrast to the known algorithms of quantum computing, which are based on -- really or potentially -- physically possible schemes, we do not know neither how to implement quantum logic operations nor whether it is physically possible to implement them. Thus, the author's research is, at present, more foundational than practical.