# Recording Quantum Queries

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?

• 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 – glS Jul 13 at 15:47
• I'm asking how $H^F$ transforms the last register. How to go from the step before the $\dots$ to the step after them. – Pratyush Ranjan Tiwari Jul 13 at 18:13
• 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 – glS Jul 14 at 6:45
• $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. – Pratyush Ranjan Tiwari Jul 14 at 13:46
• 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$ – glS Jul 14 at 13:50