COMPUTATIONS USING THE QUANTUM TURING MACHINE
Date
1995-06-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Recent investigations into a new model of computation, the quantum
Turing Machine, suggest that this model exhibits characteristics that
may admit an efficient computation of functions conjectured to be hard
otherwise. This report contains a detailed discussion of the quantum
Turing Machine and its relationship to the classical Turing Machines.
A result by Daniel Simon highlighting the potential promise of the
quantum Turing Machine is presented, followed by algorithms for
efficiently solving the Discrete Log and Integer Factorization problems
on the new model. Lastly, we consider some of the limitations inherent in
the quantum Turing Machine.
Description
Keywords
Computer Science