<p>Consider an arbitrary boolean function</p>

<p>$$f: {\lbrace 0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$$
which we write as:</p>

<p>$$f(x_1, x_2 ... x_n) $$
where each $x_i$ is a boolean variable </p>

<p>We note here that the function in question can be evaluated in constant time (is given by a constant time oracle). </p>

<p>The task is to determine whether this function is constant on all inputs or not.</p>

<p>We can consider the set of integers $Z$ modulo $2^n$ and look at their binary representation: noting that each digit in this binary representation corresponds to a value for one of the functional variables thus we write out $f$ as</p>

<p>$$f((Q \mod 2)_2, \frac{(Q \mod 4)_2}{2_2}, \frac{(Q \mod 8)_2}{4_2} ... \frac{(Q  \mod 2^n)_2}{2^{n-1}_2})) $$</p>

<p>Where $n_2$ means convert n to binary and division is integer division</p>

<p>We note that if this function is periodic with period = 1, then it must be constant. Can a Quantum Fourier Transform be employed to calculate the period of this function or merely test that the period is not equal to 1? </p>

CC BY-SA 3.0
2013-12-25T05:29:36.893Z
The Quantum Fourier transform can't distinguish between a constant function and a function which is constant except for a few isolated points. It can determine whether a function is nearly constant, but that can be done classically using random sampling.
Peter Shor 
CC BY-SA 3.0
2013-12-25T15:27:46.353Z
Agreed. In fact an efficient algorithm for this problem provably cannot exist; this follows from the optimality of Grover search. (More specifically, given $f:\{0,1\}^n \rightarrow \{0,1\}$, a quantum computer requires $\Omega(2^{n/2})$ queries to $f$ to determine if there exists an $x$ such that $f(x)=1$.)
Adam Bouland
<cc.complexity-theory><quantum-computing><sat><boolean-functions><fourier-analysis>
Determining if a function is constant or not using period finding
Sidharth Ghoshal
# Determining if a function is constant or not using period finding

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

Consider an arbitrary boolean function

$$f: {\lbrace 0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$$
which we write as:

$$f(x\_1, x\_2 ... x\_n) $$
where each $x\_i$ is a boolean variable

We note here that the function in question can be evaluated in constant time (is given by a constant time oracle).

The task is to determine whether this function is constant on all inputs or not.

We can consider the set of integers $Z$ modulo $2^n$ and look at their binary representation: noting that each digit in this binary representation corresponds to a value for one of the functional variables thus we write out $f$ as

$$f((Q \mod 2)\_2, \frac{(Q \mod 4)\_2}{2\_2}, \frac{(Q \mod 8)\_2}{4\_2} ... \frac{(Q \mod 2^n)\_2}{2^{n-1}\_2})) $$

Where $n\_2$ means convert n to binary and division is integer division

We note that if this function is periodic with period = 1, then it must be constant. Can a Quantum Fourier Transform be employed to calculate the period of this function or merely test that the period is not equal to 1?

**Tags:** cc.complexity-theory, quantum-computing, sat, boolean-functions, fourier-analysis
> **Comments:**
> **username_1**: The Quantum Fourier transform can't distinguish between a constant function and a function which is constant except for a few isolated points. It can determine whether a function is nearly constant, but that can be done classically using random sampling.  
> **username_2**: Agreed. In fact an efficient algorithm for this problem provably cannot exist; this follows from the optimality of Grover search. (More specifically, given $f:\{0,1\}^n \rightarrow \{0,1\}$, a quantum computer requires $\Omega(2^{n/2})$ queries to $f$ to determine if there exists an $x$ such that $f(x)=1$.)  

---

## 0 answers

