<p>Consider a blackbox function</p>

<p>$$f(x): Z \rightarrow \lbrace 0,1 \rbrace  $$</p>

<p>Which inputs an integer and outputs 0 or 1 with bit complexity n.</p>

<p>If the period P of this function satisfies</p>

<p>$$P \in O(2^{n})$$</p>

<p>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?</p>

<p>===========================================================================================</p>

<p>Let me correct this:</p>

<p>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$</p>

CC BY-SA 3.0
2013-12-23T13:46:07.363Z
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 
CC BY-SA 3.0
2013-12-23T14:48:52.063Z
Which properties exactly are you looking for?
Sidharth Ghoshal
<cc.complexity-theory><quantum-computing><fourier-analysis>
Computing the period of a function using a quantum computer
Sidharth Ghoshal
# Computing the period of a function using a quantum computer

(Asked by: username_0 on 2013-12-23)

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$

**Tags:** cc.complexity-theory, quantum-computing, fourier-analysis

> **Comments:**
> **username_1**: 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.  
> **username_0**: Which properties exactly are you looking for?  

---

## 0 answers

