I know this is supposed to be in cryptography but I think this question is appropriate to be asked here. I am reading the Learning with Errors paper of Oded Regev and I am confused with the uncomputation part in his proof of reduction that states an oracle for the closest vector problem yields a quantum algorithm for solving the discrete Gaussian sampling problem. So here is the setup of my question:

Let $L$ be a lattice in $\mathbb{R}^n$ with fundamental parallelepiped $\mathcal{P}(L)$ relative to some fixed basis of $L$ and $\rho$ be the Gaussian measure on $\mathbb{R}^n$. Consider that state $\displaystyle\sum_{x\in \mathbb{R}^n} \rho (x) |x, x\pmod{\mathcal{P}(L)}\rangle$. Then he said that supposed we have an oracle for CVP, we can recover $x$ from $x\pmod{\mathcal{P}(L)}$, hence we can uncompute the first register, that is we arrive at the state $\displaystyle\sum_{x\in \mathbb{R}^n} \rho (x) |x\pmod{\mathcal{P}(L)}\rangle$ (I know summing over the entire Euclidean space is absurd but he was able to give a valid state exponentially close to the 'state' over $\mathbb{R}^n$). How does this uncomputing the first register works?


1 Answer 1


The 'standard' interface of a quantum oracle for a function $f$ is $\newcommand{\ket}[1]{\left|{#1}\right\rangle}\newcommand{\+}{\oplus}\ket{x}\ket{y}\mapsto\ket{x}\ket{y\+f(x)}$.

(When $f$ is something actually implementable, then we can implement it in that form (well, together with some ancillae) using reversible computing. So usually oracles are given using this interface.)

So, when we have an oracle getting $x$ from $x\bmod P(L)$, that would be $$ \ket{x\bmod P(L)}\ket{y}\mapsto\ket{x\bmod P(L)}\ket{y\+x}. $$

When we initialize $y=x$, then this mapping would satisfy $$ \ket{x\bmod P(L)}\ket{x}\mapsto\ket{x\bmod P(L)}\ket{x\+x}=\ket{x\bmod P(L)}\ket{0}. $$

The extra, unentangled qubits $\ket{0}$ can be notationally suppressed since it is unused later.

In Regev's paper the order of $\ket{x}$ and $\ket{x\bmod P(L)}$ is reversed, but it is not important since we may use many swap gates.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.