Problems and prospects for quantum computational speed-up

Krishnamurthy, E. V. (2003) Problems and prospects for quantum computational speed-up Lecture Notes in Computer Science, 2660/2003 . p. 708. ISSN 0302-9743

Full text not available from this repository.

Official URL:

Related URL:


This paper studies the problems involved in the speed-up of the classical computational algorithms using the quantum computational paradigm. In particular, we relate the primitive recursive function approach used in computability theory with the harmonic oscillator basis used in quantum physics. Also, we raise some basic issues concerning quantum computational paradigm: these include failures in programmability and scalability, limitation on the size of the decoherence - free space available and lack of methods for proving quantum programs correct. In computer science, time is discrete and has a well-founded structure. But in physics, time is a real number, continuous and is infinitely divisible; also time can have a fractal dimension. As a result, the time complexity measures for conventional and quantum computation are incomparable. Proving properties of programs and termination rest heavily on the well-founded properties, and the transfinite induction principle. Hence transfinite induction is not applicable to reason about quantum programs.

Item Type:Article
Source:Copyright of this article belongs to Springer.
ID Code:85885
Deposited On:06 Mar 2012 13:57
Last Modified:06 Mar 2012 13:57

Repository Staff Only: item control page