Question is about techniques from this paper. Essentially the paper provides a way to record what queries were asked to a quantum-accessible oracle. We have the oracles: \begin{aligned} &\text { Standard oracle }(\mathrm{StO}):|x\rangle_{X}|y\rangle_{Y} \mapsto|x\rangle_{X}|y \oplus f(x)\rangle_{Y}\\ &\text { Phase oracle (PhO): } \quad|x\rangle_{X}|\eta\rangle_{Y} \mapsto(-1)^{\eta \cdot f(x)}|x\rangle_{X}|\eta\rangle_{Y} \end{aligned}

The fourier oracle is defined as:

$\text { Fourier Oracle }(\mathrm{FO}): F O:=H^{F} \circ P h O \circ H^{F}$ (where $H^F$ stands for $QFT$)

The problem is decoding what happens in the last step here:

\begin{array}{l} |x\rangle|\eta\rangle\left|0^{n} \cdots 0^{n}\right\rangle \stackrel{H^{F}}{\rightarrow} \sum_{f}|x\rangle|\eta\rangle|f\rangle \stackrel{P h O}{\longrightarrow} \sum_{f}(-1)^{\eta \cdot f(x)}|x\rangle|\eta\rangle|f\rangle \\ \stackrel{H^{F}}{\rightarrow} \sum_{f, \phi}(-1)^{\phi \cdot f}(-1)^{\eta \cdot f(x)}|x\rangle|\eta\rangle|\phi\rangle=\ldots \\ =|x\rangle|\eta\rangle\left|0^{n} \cdots 0^{n} \eta 0^{n} \cdots 0^{n}\right\rangle \end{array}

$|f\rangle$ is the superposition of all possible $f$ in the corresponding domain and range. The claim is that after the last step at the $x$'th position you get $\eta$. Which indicates at which point the oracle was queried. How does the register containing $f$ transform to the register with $\eta$ in the $x$'th position?

  • $\begingroup$ are you asking about the step corresponding to the arrow with label "$PhO$"? It seems they are simply applying the phase oracle with second and third registers as input $\endgroup$ – glS Jul 13 at 15:47
  • $\begingroup$ I'm asking how $H^F$ transforms the last register. How to go from the step before the $\dots$ to the step after them. $\endgroup$ – Pratyush Ranjan Tiwari Jul 13 at 18:13
  • $\begingroup$ I don't understand the notation. What does the sum over $f$ mean? Isn't $f$ the function determining the action of the oracles? I think something is missing $\endgroup$ – glS Jul 14 at 6:45
  • $\begingroup$ $f: \{0, 1\}^m \rightarrow \{0, 1\}^n$ represents all the possible functions from $m$-bit to $n$-bit strings, hence $|f\rangle$ represents the superposition of all truth tables of $f$. You are right this does cause some confusion. When it says $f(x)$ it refers to one such function, so I guess replacing $f(x)$ with $g(x)$ should give clarity. Let me know what you think. $\endgroup$ – Pratyush Ranjan Tiwari Jul 14 at 13:46
  • $\begingroup$ I guess it's fine but you should put this information into the post. I still don't get it though. What does "superposition of truth tables" mean exactly? And then what does $\sum_f |f\rangle$ mean? A superposition of superpositions of truth tables? You should explicit these definitions in the post. Also it is probably going to be useful to write the explicit form of the gate $FO$ $\endgroup$ – glS Jul 14 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.