0
$\begingroup$

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$

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Commented Dec 23, 2013 at 13:46
  • $\begingroup$ Which properties exactly are you looking for? $\endgroup$
    – Sidharth Ghoshal
    Commented Dec 23, 2013 at 14:48

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.