Determining the period of a function is the main step in Shor’s factorization algorithm which is a cornerstone in the theory of quantum computing and a primary motivation for developing quantum computers. This paper investigates whether it is possible to have a universal Turing machine that is able to compute the minimum (or fundamental) period of a given periodic computable continuous function. It is shown that for every periodic computable continuous function, its fundamental period is always a computable number. Therefore, there always exists a specific Turing machine for computing the period of this function. Nevertheless, it is also shown that there exists no universal algorithm that is able to compute the period for all functions having periods that are known to be smaller than a given upper bound.
Periodic functions are of special importance in quantum computing, particularly in applications of Shor's algorithm. We explore methods of creating circuits for periodic functions to better understand their properties. We introduce a method for constructing the circuit for a simple monoperiodic function, that is one-to-one within a single period, of a given period
p. We conjecture that to create a simple periodic function of period
p, where
p is an
n-bit number, one needs at most
n Toffoli gates.
Periodic functions are of special importance in quantum computing, particularly in applications of Shor's algorithm. We explore methods of creating circuits for periodic functions to better understand their properties. We introduce a method for constructing the circuit for a simple monoperiodic function, that is one-to-one within a single period, of a given period p. We conjecture that to create a simples periodic function of period p, where p is an n-bit number, one needs at most n Toffoli gates.