How to build a quantum circuit of a given reversible function?

Question

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$ ?

Answer 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$.