Given a function $f : \{0,1\}^n \longrightarrow \{0,1\}^m$ and a function $g : \{0,1\}^m \longrightarrow \{0,1\}^n$ that both can be computed by polynomial-size classical circuits such that $g(f(x))=x$ for all $x\in\{0,1\}^n$, how can I build a quantum circuit that maps $|x,0\rangle$ to $|f(x),0\rangle$ ?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
I assume you know how to turn a classical circuit that computes $f$ into a quantum circuit that computes $|x,\,y\oplus f(x)\rangle$ from $|x,y\rangle$, since that should be covered in any introduction to quantum computing.
Given $|x,0\rangle$ and quantum circuits of that kind for $f$ and $g$, you can simply compute $|x,f(x)\rangle$, then rearrange to $|f(x),x\rangle$, then compute $|f(x),x\oplus g(f(x))\rangle = |f(x),0\rangle$.
