Why can you check for entanglement using the quantum Fourier transform?

Question

I'm reading this paper on quantum random oracles, and I have some fundamental questions about certain statements that seem to be intuitive (but I can't seem to figure it out). My goal is to have a deeper understanding of the QFT and it's uses.

My question has to do with an example from the paper. Here, $h_0:\{0,1\}^{2n}\to\{0,1\}^n$ is just some compression function.

(page 4)[The adversary] sets up the uniform superposition $\sum_{x,y}|x,u\rangle$ and queries. In the case where $h_0$ Is a classical function, then this state becomes $$\sum_{x,u}|x,u\oplus h_0(x)\rangle=\sum_{x,u}|x,u\rangle.$$ Namely, the state is unaffected by making the query. In contrast, the simulated query would result in $$\sum_{x,u}|x,u\oplus y\rangle\otimes|x,y\rangle.$$ Here, the adversary's state is now entangled with the simulator's. It is straightforward to detect this entanglement by applying the QFT to the adversary's $x$ registers, and then measuring the result.

What does it mean for the quantum adversary to query a classical function? Why does it have no effect? Next, why is it easy to see that you can check for entanglement using the QFT on the $x$ registers? My understanding is that applying the QFT would just give you some kind of frequency information, so if the $x$ registers were in the uniform superposition I'd think you'd always get $|0\rangle$

Answer 1

To answer your question, it is required to give a bit of context on this paper.

---

In cryptography, the random oracle is a technique in which you assume that when the adversary queries the oracle for $h(x)$, two cases could happen:

1. The adversary never asked the oracle the value of $h(x)$ before. In this case, the oracle picks a random value $y$, sets $h(x)=y$ and returns $y$ to the adversary.
2. The adversary already asked the oracle the value of $h(x)$, in which case the oracle returns the value it returned the first time.

This technique has been used in numerous proofs, and a quantum equivalent is desired to make some security proofs work. Note that in this case, it is completely equivalent to work with a random function $h$.

However, something inherently classical is part of the definition of a random oracle: the oracle must know whether the adversary already queried $h(x)$ once to return the value. But when the query is a superposition one, what is the oracle supposed to do? The adversary must not know that the oracle records their queries. In fact, the adversary must not be able to differentiate between interacting with the quantum random oracle and interacting with an oracle implementing a random function.

---

The example that your question is about describes a naive strategy for the oracle, and shows that such a strategy doesn't work, as the adversary can know whether they interact with a random oracle applying this strategy or with an oracle implementing a random function.

Let $h_0$ be our random classical function. Let $\mathcal{O}$ be the quantum random oracle and let $\mathcal{O}_{h_0}$ be the oracle implementing $h_0$. In this strategy, $\mathcal{O}$ applies a C-NOT between the adversary's query and a local register before choosing a random value $y$: $$\sum_{x,u}\alpha_{x,u}|x,u\rangle\to\sum_{x,u}\alpha_{x,u}|x,u\oplus y\rangle_{\text{A}}|x,y\rangle_{\text{O}}$$ I've denoted with a subscript $\text{A}$ the registers returned to the adversary and with $\text{O}$ the ones the oracle keeps. The intuition is that when the adversary measures their registers, they will get a random value $y$ associated to the measure of the register containing $x$. Since this also collapsed the oracle's database, the oracle knows that $h(x)=y$ from now on and can act accordingly.

As a recall, when the adversary interacts with $\mathcal{O}_{h_0}$, the following happens: $$\sum_{x,u}\alpha_{x,u}|x,u\rangle\to\sum_{x,u}\alpha_{x,u}\left|x,u\oplus h_0(x)\right\rangle$$ Now, what happens if the adversary's query is the uniform superposition? If the adversary interacts with $\mathcal{O}_{h_0}$, then the state of the system is: $$\sum_{x,u}\left|x,u\oplus h_0(x)\right\rangle$$ You can convince yourself that this state is exactly the uniform superposition. Indeed, that's more easily seen when writing this state as: $$|0\rangle\sum_u\left|u\oplus h_0(0)\right\rangle+|1\rangle\sum_u\left|u\oplus h_0(1)\right\rangle+\cdots$$ For each $i$, $h_0(i)$ is a random but fixed bitstring. As such, $\sum_u\left|u\oplus h_0(i)\right\rangle$ contains exactly each basis state once, since the function $x\mapsto x\oplus h_0(i)$ is bijective. The state can thus be written as: $$|0\rangle\sum_u\left|u\right\rangle+|1\rangle\sum_u\left|u\right\rangle+\cdots=\sum_{x}|x\rangle\sum_u|u\rangle=\sum_{x,u}|x,u\rangle$$ Hence, if the adversary applies a QFT gate on this system and measure it, it will result in state $|0,0\rangle$ with probability $1$.

However, if the adversary interacts with the quantum random oracle, the state of the system is: $$\sum_{x,u}|x,u\oplus y\rangle_{\text{A}}|x,y\rangle_{\text{O}}$$ In this case, the adversary's registers are entangled with the oracle's. If the adversary applies a QFT gate on these registers and measure them, it will result in state $|0,0\rangle$ with negligible probability ($\frac{1}{2^{n}}$ if I'm not mistaken, with $n$ being the size of the adversary's $x$ register).

Thus, this strategy cannot be used to simulate a quantum random oracle, since an adversary is able to distinguish between this quantum random oracle and an oracle implementing a classical random function. The whole point of Zhandry's paper is to describe a technique that the quantum random oracle can apply to be indistinguishable from an oracle implementing a random function.