CLASSICAL AND QUANTUM COMPUTATION WITH SMALL SPACE BOUNDS

John P. Preskill

Adriano Barenco

H.E. Caicedo-Ortiz, Elizabeth Santiago-Cortes

Rodney Van Meter

Modular exponentiation is the most expensive portion of Shor’s algorithm. We show that it is possible to reduce the number of quantum modular multiplications necessary by a factor of , at a cost of adding temporary storage space and associated machinery for a table of entries, and performing times as many classical modular multiplications. The storage space may be a quantum-addressable classical memory, or pure quantum memory. With classical computation as much as times as fast as quantum computation, values of from 2 to 30 seem attractive; physically feasible values depend on the implementation of the memory.

Daniel Gottesman, Alexei Kitaev, Alexander Khanievich Shen' +1 more

Diederik Aerts, Bart D’Hooghe

Using the ‘between quantum and classical ’ models that have been constructed explicitly within the hidden measurement approach of quantum mechanics we investigate the possibility to construct a ‘between quantum and classical ’ computer. In this view, the pure quantum computer and the classical Turing machine can be seen as two special cases of our general computer. We have shown in earlier research that the intermediate ‘between quantum and classical ’ systems cannot be described within standard quantum theory. We argue that the general categoral approach of state property systems might provide a unified framework for the study of these ‘between quantum and classical’ models, and hence also for the study of classical and quantum computers as special cases. 1