# Quantum algorithms to implement polynomial oracles

Let $$N = 2^n$$, and suppose $$x = (x_0, x_1,\dots,x_{N-1}) \in \mathbb{C}^N$$, such that $$||x||_2 = 1$$.

Suppose we are given the $$n$$-qubit quantum state $$\lvert x \rangle = \sum_{i=0}^{N-1} x_i \lvert i \rangle$$. Are there quantum algorithms to implement the non-linear map: $$\lvert x \rangle \mapsto \lvert y \rangle$$, where $$\lvert y \rangle = \frac{1}{K}\sum_{i=0}^{N-1} x_i^m \lvert i \rangle$$, where $$K$$ is a normalization constant, and $$m \in \mathbb{R}^+$$.

You are allowed to use ancillas.

If some references exist in the literature for this problem, it would be great if you can let me know.

• You've already said it - your map is nonlinear? Commented Jun 25 at 20:39
• @MarkSpinelli I have seen quite a few quantum algorithms papers where assumption of oracles performing $\lvert x \rangle \lvert 0 \rangle \mapsto \lvert x \rangle \lvert f(x) \rangle$ is assumed, for example in papers claiming quantum advantage for convex & nearly-convex optimization problems. In those cases, $f$ is far from being linear. Commented Jun 25 at 21:20
• Thanks. But also in those cases the first register is entangled with the second. Here, you only have one register. When you so that ancillae are allowed, the presumption is that those ancillae need to revert back to $|0\rangle$ after uncomputing. Commented Jun 25 at 23:38
• Is there an answer if we dont make this presumption? Lets say we are allowed to measure and discard some of the ancillas, and are allowed to use repeat until success schemes (as an example of operations that can introduce non-linearity). Commented Jun 26 at 3:34
• I guess the HHL algorithm kinda counts. When we rotate the ancilla we post-select on the ancilla to make sure it's $|1\rangle$. Commented Jun 26 at 19:07