# Function on qubits The domain of functions are the computational basis and the range is a subset of the computational basis. without loosing generality, we can look at function $f:\{0,1\}^n\mapsto \{0,1\}$. It maps a tensor of $n$ computational basis to computational basis $|0\rangle,|1\rangle$ . function on qubits must be invertible as only Unitarians operators can be applied on qubits and they are invertible. But general boolean functions might not be invertible e.g.., a constant function $f(0)=0,f(1)=0$ isn't invertible because $0$ is being mapped from 2 different sources. Given a non-invertible $f(x)$, it can be extended to $F$ an invertible function by adding input parameter $t$ and define $F(x,t)=(x,t\oplus f(x))$. $F$ is invertible because $F(F(x,t))=F(x,t\oplus f(x))=(x,t\oplus f(x)\oplus f(x))=(x,t)$. ## Example - Let $f(x,y)=x\land y$ which is not invertible. Extend it to $F(x,y,t)=\big(x,y,t\oplus (x\land y)\big)$. When computing $f$ init $t=0$ and compute $F(x,y,0)=(x,y,x\land y)$. $F$ is invertible as can seen from the table below: | $x$ | $y$ | $t$ | $F(x,y,t)$ | | --- | --- | --- | ---------- | | 0 | 0 | 0 | (0,0,0) | | 0 | 1 | 0 | (0,1,0) | | 1 | 0 | 0 | (1,0,0) | | 1 | 1 | 0 | (1,1,1) | | 0 | 0 | 1 | (0,0,1) | | 0 | 1 | 1 | (0,1,0) | | 1 | 0 | 1 | (1,0,1) | | 1 | 1 | 1 | (1,1,0) | ## From boolean function to unitarian operator For $f(x)$, define $U_f|x,t\rangle:=|x,f(x)\oplus t\rangle$ . $U_f\big(U_f\ket{x,t}\big)=U_f|x,f(x)\oplus t\rangle = |x, t\rangle$ therefore $U_f=U_f^{-1}$ i.e., $U_f$ is invertible. For a fixed $x$ , if $f(x)=0$ then $U_f\ket{x,0}=\ket{x,0}$ and $U_f\ket{x,1}=\ket{x,1}$ and if $f(x)=1$ then $U_f\ket{x,0}=\ket{x,1}$ and $U_f\ket{x,1}=\ket{x,0}$. This means that either $\ket {x,0}$ is mapped to itself or it is swap with $\ket{x,1}$. This true for every $x$ in the computational basis and so $F$ is a permutation on the basis. A permutation matrix is shuffle of rows and column of the identity matrix and so has single 1 in every row and column and so its row and columns are orthogonal. This means that $U_f\cdot U_f^\dagger=I$ and $U_f$ is unitarian. ## Examples - $f(x)=x$ Define $U_f\ket{x,t}=\ket{x,x\oplus t}$. ``` x: ─────●───── │ t: ─────⊕───── ``` - $f(x)=1$ Define $U_f\ket{x,t}=\ket{x,1\oplus t}=\ket {x ,X\ket t}$ . note: $X$ is the X-gate that operate as logical NOT. ``` x: ───────────── t: ─────X────── ``` - $f(x)=\lnot x$ i.e., logic-not. Define $U_f\ket{x,t}=\ket{x,X\ket x\oplus t}$ ``` x: ───X───●───X─── │ y: ───────⊕─────── ``` note: that we appliy X-gate to compute $\lnot x$ and the undo it by re-applying X-gate. ## Construct Unitarian from function? Any boolean function can be represented as a composition of the logic operations: AND, OR, NOT. 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$ ## Example Let $f(a,b,c)=(a∧b)∨¬c$. We construct the unitary operator $U_f∣a,b,c,t⟩=∣a,b,c,t⊕f(a,b,c)⟩$ We use two temporary ancilla $u,v$ initialized to $\ket0$, and an output qubit $t$. #### 1. Compute the AND Compute $u=a\land b$ using a Toffoli gate: $|a,b,0\rangle\xrightarrow{\operatorname{Toffoli}_{a,b\rightarrow u}}|a,b,a\land b\rangle$. #### 2. Compute the NOT Compute $v=\neg c$ by first setting $v=1$, then XORing $c$: $|c,0\rangle\xrightarrow{X_v}|c,1\rangle\xrightarrow{\operatorname{CNOT}_{c\rightarrow v}}|c,1\oplus c\rangle=|c,\neg c\rangle$. The $X$ gate must act on the output ancilla $v$. #### 3. Compute the OR Now $u=a\land b$ and $v=\neg c$. Use $u\lor v=u\oplus v\oplus uv$. Starting with $t=0$: $t\xrightarrow{\operatorname{CNOT}_{u\rightarrow t}}t\oplus u$, $t\oplus u\xrightarrow{\operatorname{CNOT}_{v\rightarrow t}}t\oplus u\oplus v$, $t\oplus u\oplus v\xrightarrow{\operatorname{Toffoli}_{u,v\rightarrow t}}t\oplus u\oplus v\oplus uv$. Therefore, $t\longmapsto t\oplus\big((a\land b)\lor\neg c\big)$. #### Circuit diagram ```text a: ───●────────────────────────────────────────●─── │ │ b: ───●────────────────────────────────────────●─── │ │ u: ───⊕────────────●────────────●──────────────⊕─── │ │ c: ────────●───────┼────────────┼──────●─────────── │ │ │ │ v: ───X────⊕───────┼────●───────●──────⊕────X────── │ │ │ t: ────────────────⊕────⊕───────⊕────────────────── ``` The last gates uncompute $u$ and $v$, returning them to $|0\rangle$. The final transformation is $|a,b,c,0,0,t\rangle\longmapsto|a,b,c,0,0,t\oplus((a\land b)\lor\neg c)\rangle$. Every gate used—$X$, $\operatorname{CNOT}$, and $\operatorname{Toffoli}$—is unitary. Therefore, their composition is also unitary. ## Example - remote state preparation - Remote state preparation (Udi's patent): Let $f:\{0,1\}^n\mapsto\{0,1\}^n$ be one-way, trapdoor permutation. - generate uniform register: $\frac{1}{2^n}\sum_{x=0}^{2^n-1}\ket x$ - tensor with $\ket{0^n}$ : $\frac{1}{2^n}\sum_{x=0}^{2^n-1}\ket x\ket0$ - apply $f$: $\frac{1}{2^n}\sum_{x=0}^{2^n-1}\ket x\ket {f(x)}$ - Measure the 2n register (the one with $f(x)$) and get a classic bit string $y$. The first register collapse to a uniform random value $x_0$ in range $[0,2^n-1]$ s.t. $f(x_0)=y$. The server see $y$ and can't compute $x_0$ efficiently as $f$ is one-way function - send the client $y$ - Client uses $f$-trapdoor to compute $x_0$ - Client knows that the first register in the server is $\ket {x_0}$ and the server does not this. - note: the threat model here is honest but curious in the sense that server execute circuits given by the client without deviation and without measuring. If something is measured in the circuit he can view it. --- ## 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$ Related: [[Unitarian branching on qubits]] ## Created 2026-02-01 12:52