# Function on qubits Let $f:\{0,1\}^n\mapsto \{0,1\}$. It can be used to map a tensor of $n$ computational basis to computational basis $|0\rangle,|1\rangle$ . function on qubits are invertible as they are composition of Unitarians operators. Any function $f$ can be changed to invertible function by adding an extra parameter for storing the result. This way the output is composed of the input parameter plus the result parameter and so it is simple to invert: simple return the input parameters from the result. The trick is to add an auxiliary qubit $y$ (ancilla) which store the output qubit. For $f(x_1,...,x_n)$, define $U_f|x_0...x_n,y\rangle:=|x_0...x_n,f(x_0...x_n)\oplus y\rangle$ . It is invertible: $U_f\big(U_f|x_0...x_n,y)\big)=U_f|x_0...x_n,f(x_0,...,x_n)\oplus y\rangle = |x_0...x_n, y\rangle$ i.e., $U_f=U_f^{-1}$ and $U_f$ is unitary more accurate it is Hermitian and Unitary. For computing $|f(x_1,...,x_n)\rangle$ set $y=0$ and compute $U_f|x_0...x_n,y\rangle$. ## Apply $U_f$ on $|0\rangle$ Using ancilla of $|0\rangle$ we get: $U_f|x_0...x_n,0\rangle = \bigg|x_0...x_n,f(x_0...x_n)\oplus 0\bigg\rangle=\bigg|x_0...x_n,f(x_0...x_n)\bigg\rangle$ So the output is $|f(x_0...x_n)\rangle$ . ## Examples: #### f(x)=x |x⟩: ───●──── │ |y⟩: ───X──── #### f(x)=1 |x⟩: ───────── |y⟩: ───X───── #### f(x)=not(x) |x⟩: ───X───●───X─── │ |y⟩: ───────X─────── ## Apply $U_f$ on $|-\rangle$ - compute on "phase" Using ancilla of $|-\rangle$ we get: $ \begin{align} U_f|x\rangle|-\rangle&=\frac{1}{\sqrt{2}}\big(U_f|x\rangle|0\rangle-U_f|x\rangle|1\rangle\big) \\ &=\frac{1}{\sqrt 2}\bigg(|x\rangle|f(x)\rangle-|x\rangle|1 \oplus f(x)\rangle \bigg) \\ &= \frac{1}{\sqrt 2}|x\rangle\bigg(|f(x)\rangle-|1\oplus f(x)\rangle \bigg) \end{align}$ 1) The case $f(x)=0$, $U_f|x\rangle|-\rangle=|x\rangle|-\rangle$ 2) The case $f(x)=1$, $U_f|x\rangle|-\rangle=-|x\rangle |-\rangle$ In both cases, $U_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle$ . we ignore drop the ancilla and enjoy the change in the amplitude signs. This is why we write $\boxed{U_f|x\rangle=(-1)^{f(x)}|x\rangle}$ when computing in phase. ## Apply $U_f$ on $|-\rangle$ for $f:\{0,1\}^n\mapsto\{0,1\}$ This is similar to the case $f:\{0,1\}\mapsto\{0,1\}$ because all computation stays the same. ## Defining $|f\rangle$ $|f\rangle:=\frac{1}{\sqrt N}\sum_{x\in\{0,1\}^n}(-1)^{f(x)}|x\rangle$ Or $|f\rangle:=\frac{1}{\sqrt N}\sum_{x\in\{0,1\}^n}f(x)|x\rangle$ ## How boolean function is computed on ancilla $|0\rangle$? AND operation This is implemented with Toffoli gate: $f|a,b,0\rangle=\text{Toffoli}|a,b,0\rangle=|a,b,0\oplus ab\rangle=|a,b,ab\rangle $ OR operation First, note the equality: $a\text{ OR } b=a\oplus b\oplus ab$ 1) add $a$ to the ancilla: $CNOT_{1,3}|a,b,0\rangle=|a,b,0\oplus a\rangle=|a,b,a\rangle$ 2) $CNOT_{2,3}|a,b,a\rangle=|a,b,a\oplus b\rangle$ 3) $\text{Toffoli}|a,b,a\oplus b\rangle = |a,b,a\oplus b\oplus ab\rangle$ NOT operation 1) add $a$ to the ancilla: $CNOT_{1,3}|a,b,0\rangle=|a,b,0\oplus a\rangle=|a,b,a\rangle$ 2) $I\otimes X\otimes I|a,b,a\rangle =|a,b,\overline a\rangle$ Related: [[Unitarian branching on qubits]] ## Created 2026-02-01 12:52