# Computing the period of a function using a quantum computer

Consider a blackbox function

$$f(x): Z \rightarrow \lbrace 0,1 \rbrace$$

Which inputs an integer and outputs 0 or 1 with bit complexity n.

If the period P of this function satisfies

$$P \in O(2^{n})$$

Can a quantum computer determine the period of this function within $\frac{2}{3}$ probability of correctness in polynomial in $n$ time using polynomial in $n$ space?

===========================================================================================

Let me correct this:

the problem is equivalent to asking if Simon's Algorithm or some variant of it can be used to find the period of a function $f: {\lbrace 0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$

• First: these two questions are not equivalent. The first has a domain of ${\mathbb{Z}}$; the second of $\{0,2^n-1\}$. This can make a difference. Second, I can't give you a "yes" or "no" answer, because it depends on properties of the function you haven't included in your question, but period-finding is a very important quantum algorithm that is used as a subroutine in discrete log and factoring and you should be able to find a good survey on it somewhere. – Peter Shor Dec 23 '13 at 13:46
• Which properties exactly are you looking for? – frogeyedpeas Dec 23 '13 at 14:48