# How would I theorise a quantum query algorithm in O(1)?

I am currently attempting to solve a problem from Nielsen-Chuang, and I can't seem to figure out how I would do this;

I'm trying to implement Grover's algorithm to solve the problem of differentiating between the two functions with 99% probability in O(1),

$$f_0:\{0,1\}^n → \{-1,1\} \; s.t. \; \hat{f}(00...0)=\sqrt{2/3}\\ f_1:\{0,1\}^n → \{-1,1\} \; s.t. \; \hat{f}(11...1)=\sqrt{2/3}$$

Does anyone know how I would do this?

• what is $\hat f$ here? – glS Mar 16 at 16:00
• @glS $\hat{f}$ is a function such that $\hat{f}=<f | \chi_x>$ where $\chi_x$ is a Fourier basis or Boolean function – lambda Mar 16 at 17:30
• @MarkS thanks for the response, how would I resolve it using the Deutsch-Josza? I'm still getting to grips with quantum query algorithms so any help would be appreciated – lambda Mar 16 at 19:31

I hunted around for this for a little bit and couldn't find it in my copy of N&C, but nonetheless I think that the setup is more akin to the Deutsch-Jozsa algorithm than to Grover's algorithm.

TL/DR, much as the Deutsch-Jozsa algorithm uses the Hadamard transform to distinguish a constant function from a balanced function with the promise that the function is constant or balanced, a quantum Fourier transform can distinguish an almost-constant function from a high frequency function with the promise that the function is almost-constant or is high-frequency. Repeating a small number of times amplifies the success probability.

For example, the Deutsch-Jozsa algorithm uses the Hadamard transform to distinguish a constant function from a balanced function. Similarly as described in the question it appears that we have oracle access to a Boolean function $$f$$:

$$f:\{0,1\}^n \mapsto \{0,1\}$$

with a promise on the coefficients of the Fourier transform, that either:

$$\hat{f}(00...0)=\sqrt{2/3},$$

e.g. $$f$$ is nearly constant on its codomain, or

$$\hat{f}(11...1)=\sqrt{2/3},$$

e.g. $$f$$ has a high frequency. There is no promise on other Fourier coefficients. Our task is to determine whether $$f$$ is constant or is high frequency.

Similar to the Deutsch-Jozsa where we prepare a uniform superposition on the input register, evaluate the oracle function, perform a Hadamard transform on the first register, and measure the first register, here we can prepare a uniform superposition on our input register, evaluate the oracle function, perform a quantum Fourier transform on the first register, and measure the first register.

If our oracle is nearly constant, we measure the first register as $$\vert 00\cdots0\rangle$$ with probability $$(\sqrt{2/3})^2=2/3$$. If our oracle is high-frequency, we measure the first register as $$\vert 11\cdots 1\rangle$$ with probability $$(\sqrt{2/3})^2=2/3$$. Either way with probability $$1/3$$ we might get junk by measuring some other string (say $$\vert101001\cdots0\rangle$$) corresponding to another Fourier coefficient.

Nonetheless we can repeat the procedure, say, $$4$$ times, and quickly get a high probability, $$\gt 99\%$$, of faithfully determining whether $$f$$ is constant or high-frequency, simply based on taking the majority and relying on Chernoff's bound.