# QFHE (Quantum-FHE)
## Content
- QFHE for Pauli gates
- QFHE for Clifford gates (includes $H, CNOT$)
- QFHE for Toffoli gate: reduction of Toffoli to $CNOT^s$ for $s\in\{0,1\}$ is encrypted.
- Computing $CNOT^s$
- Trapdoor-claw-free functions and FHE for QC
## FHE in the context of QC
- [[Pauli one-time pad (Quantum one-time pad)]] and Pauli keys.
- The general idea of QFHE : For any unitarian operator $U$ on a qubit $|\psi\rangle$ which is encrypted with Pauli-pad $(x,z)$: $U\big(X^xZ^z|\psi\rangle\big)$, find $x',z'\in\{0,1\}$ s.t. $X^{x'}Z^{z'}\big(U|\psi\rangle\big)$. This is simply extended to n-qubit system. The exponents of $X,Z$ are encrypted with FHE scheme and the values of $x',z'$ are computed homomorphically. The FHE has bit as plaintext space and operations are XOR and AND of bits. Decryption of the computation result is done as follows: the server compute a logic result $|\psi_{out}\rangle$ i.e., it holds $Z^{z'}X^{x'}|\psi_{out}\rangle$. When measured, $Z^{z'}X^{x'}|\psi_{out}\rangle$ collapses to a string of classic bits $m$ , which is equal to the bit list $m'$ when $|\psi_{out}\rangle$ is measured XORed with decryption of $x'$ . The server will send $m'=m\oplus x'$ and $\text{Enc}(x')$ to the client. The client will decrypt $x'$ via HE scheme and compute classically $m'\oplus x'=m$.
- [[Quantum universal set]] .since it is a universal set. Any operator $U$ can be represent as $U=U_n\circ\cdots\circ U_1$ where $U_i\in$ {[[Hadamard Gate (H-gate)|H]],[[CNOT gate|CNOT]], [[Toffoli gate|Toffoli]]}. If we show for each $i$ , $U_i(X^{x_i}Z^{z_i}|\psi_i\rangle)=X^{x'_i}Z^{z'_i}(U_i|\psi_i\rangle)$ then we get $U_n\circ\cdots\circ U_1(X^{x_1}Z^{z_1}|\psi\rangle)=X^{x'_n}Z^{z'_n}(U_n\circ\cdots\circ U_1|\psi\rangle)$Therefore, it is enough to show how to compute QFHE for any $U\in${[[Hadamard Gate (H-gate)|H]],[[CNOT gate|CNOT]], [[Toffoli gate|Toffoli]]}
---
## QFHE for Pauli gates
Every [[Pauli operators(gates) and Pauli group|Pauli gate]] is equal to $X^xZ^z$ for some $x,z\in\{0,1\}$. So, for Pauli gate we do not need to actual compute it over the qubit but we can just update the Pauli keys homomorphically. $P\big(X^xZ^z|\psi\rangle\big)=X^{x'}Z^{z'}|\psi\rangle$
> Example 1: $X\big(X^xZ^z|\psi\rangle\big)=X^{x}XZ^{z}|\psi\rangle=X^x(-1)^zZ^zX|\psi\rangle=(-1)^zX^xZ^z(X|\psi\rangle)=X^xZ^z(X|\psi\rangle)$
> Example 2:
> $X\big(X^xZ^z|\psi\rangle\big)=X^{x}XZ^{z}|\psi\rangle=X^x(-1)^zZ^zX|\psi\rangle=(-1)^zX^xZ^z(X|\psi\rangle)=X^xZ^z(X|\psi\rangle)$
note: we remove the $(-1)^z$ as it is a [[Global phase]]
## QFHE for Clifford gates
We are interested in Clifford gates for the case Hadamard and CNOT gates.
[[Clifford group (quantum gates)|Clifford]] gates stabilize the Pauli group i.e., $CPC^\dagger\in Pauli$
$C\big(X^xZ^z|\psi\rangle\big)=(CX^xC^\dagger)(CZ^zC^\dagger\big) C|\psi\rangle = (X^{x'}Z^{z'})(X^{x''}Z^{z''})C|\psi\rangle=X^{x'''}Z^{z'''}C|\psi\rangle$
> Example: for $H\big(X^xZ^z|\psi\rangle\big)$ compute Pauli keys $x',z'$ s.t. $X^{x'}Z^{z'}H|\psi\rangle$ .
As $H\big(X^xZ^z|\psi\rangle\big)=\big(HX^xZ^zH^\dagger \big)H|\psi\rangle$ , we want to express $HX^xZ^zH^\dagger$ as $X^{x'}Z^{z'}$.
Using $HXH=Z$, $HZH=X$ and $H^\dagger=H$ we get
$HX^xZ^zH^\dagger=(HXH)^x(HZH)^z=Z^xX^z=(-1)^{xz}X^zZ^x$
where $(-1)^{xz}$ can be dropped as global phase and we get $\boxed{x'=z,z'=x}$.
## QFHE for Toffoli gates
Background
1) CNOT on computational basis. $CNOT|a,b\rangle=|a,a\oplus b\rangle$ and $CNOT^s|a,b\rangle$ means activate CNOT if $s=1$ and do nothing if $s=0$ which is equivalent to $CNOT^s|a,b\rangle=|b\oplus (a\cdot s)\rangle$ note: $CNOT^2=I$ . --- remove the power 2 and write cnot*cnot as it confuse
2) Conditioned-Z: $\hat Z|a\rangle\otimes|b\rangle:=\cases{|a\rangle\otimes|b\rangle, a=0 \text{ or } b=0\\ (-1)|a\rangle\otimes|b\rangle, a=1 \text{ and } b=1}$ or equivalently, $\hat Z|a\rangle\otimes|b\rangle=(-1)^{ab}|a,b\rangle$
3) $\hat Z|a\rangle\otimes|b\rangle=(I\otimes H)CNOT(I\otimes H)|a\rangle\otimes|b\rangle$ . To see that this is true, we can check that it is equal on all computational basis. For example the case $|11\rangle$ : $\hat Z|11\rangle=-|11\rangle$,
$
\begin{align}
(I\otimes H)CNOT(I\otimes H)|11\rangle &=(I\otimes H)CNOT\big(|1\rangle\otimes |-\rangle\big) \\
&=(I\otimes H) |1\rangle\otimes(\frac{1}{\sqrt2}|0\oplus 1\rangle-\frac{1}{\sqrt2}|1\oplus 1\rangle) =\\
&=(I\otimes H)|1\rangle\otimes (-1)|-\rangle\\
&=-|11\rangle
\end{align}
$
same is true for all inputs in computational basis.
4) $\hat Z^x = (I\otimes H^x)CNOT^x(I\otimes H^x)= (I\otimes H)CNOT^x(I\otimes H)$ where the rightmost equality is true since $H^2=I$ . This means that if $x=1$ compute $(I\otimes H)CNOT(I\otimes H)$ and do nothing if $x=0$. The bottomline: $\hat Z^x$ can be represented as $CNOT^x$ and Hadamard gates.
To complete the universal set we repeat the above computation for [[Toffoli gate]] .
The input to the gate is encrypted by Pauli-pad i.e., $Z^{z_1}X^{x_1}|a\rangle\otimes Z^{z_2}X^{x_2}|b\rangle\otimes Z^{z_3}X^{x_3}|c\rangle$. activating Toffoli on this input:
$
\begin{align}
T(Z^{z_1}X^{x_1}|a\rangle\otimes Z^{z_2}X^{x_2}|b\rangle\otimes Z^{z_3}X^{x_3}|c\rangle&) =T\big(Z^{z_1}X^{x_1}\otimes Z^{z_2}X^{x_2}\otimes Z^{z_3}X^{x_3})|a,b,c\rangle \big) \\
&=\big(T(Z^{z_1}X^{x_1}\otimes Z^{z_2}X^{x_2}\otimes Z^{z_3}X^{x_3}) T^\dagger\big) T|a,b,c\rangle
\end{align}
$
Similar to previous cases (Pauli and Clifford gates), we compute $T(Z^{z_1}X^{x_1}\otimes Z^{z_2}X^{x_2}\otimes Z^{z_3}X^{x_3})T^\dagger$ : $\boxed{T(Z^{z_1}X^{x_1}\otimes Z^{z_2}X^{x_2}\otimes Z^{z_3}X^{x_3})T^\dagger=CNOT^{x_2}_{1,3}CNOT_{2,3}^{x_1} \hat Z_{1,2}^{z_3}\bigg( Z_1^{z_2+x_2z_3}X_1^{x_1}\otimes Z_2^{z_2+x_1z_3}X_2^{x_2}\otimes Z_3^{z_3}X_3^{x_1x_2+x_3}\bigg)}$
To give some intuition why this equality true and where CNOT is coming from
$
\begin{align}
T(Z^{z_1}X^{x_1}\otimes Z^{z_2}X^{x_2}\otimes Z^{z_3}X^{x_3})T^\dagger&=T(Z^{z_1}\otimes I\otimes I)(X^{x_1}\otimes I\otimes I)\cdots)T^\dagger\\
&=T(Z^{z_1}\otimes I\otimes I)T^\dagger T(X^{x_1}\otimes I\otimes I)T^\dagger T\cdots)T^\dagger
\end{align}
$
We will use the notation $TZ_1^{z_1}T^\dagger$ for $T(Z^{z_1}\otimes I\otimes I)T^\dagger$ for simplification.
Toffoli gate operation: $T|a,b,c\rangle=|a,b,c\oplus ab\rangle$ and $T^\dagger=T$.
$X_1:=(X\otimes I\otimes I)$ .
Example 1: $TX_1T^\dagger=X_1CNOT_{2,3}$ because :
$
\begin{align}
TX_1T^\dagger|a,b,c\rangle&=TX_1|a,b,c\oplus ab\rangle=T|a\oplus 1,b,c\oplus ab\rangle \\
&= |a\oplus 1,b,c\oplus ab\oplus((a\oplus1)b)\rangle=|a\oplus 1,b,c\oplus b\rangle\\
&=X_1CNOT_{2,3}|a,b,c\rangle
\end{align}
$
Example: $TX_1^{x_1}T^\dagger=X_1^{x_1}CNOT^{x_1}_{2,3}$ because :
$
\begin{align}
TX_1^{x_1}T^\dagger|a,b,c\rangle & =
\begin{cases}
X_1CNOT_{2,3}|a,b,c\rangle , &, x_1=1\\
|a,b,c\rangle & ,x_1=0
\end{cases}\\
&= X_1^{x_1}CNOT_{2,3}^{x_1}|a,b,c\rangle
\end{align}
$
Example 2: $TZ_1T^\dagger=Z_1$ because:
$
\begin{align}
TZ_1T^\dagger|a,b,c\rangle&=TZ_1|a,b,c\oplus ab\rangle\\
&=T|(-1)^aa,b,c\oplus ab\rangle \\
&=(-1)^a T| a,b,c\oplus ab\rangle \\
& =(-1)^a|a,b,c\rangle =|(-1)^aa,b,c\rangle = Z_1|a,b,c\rangle \\
\end{align}
$
Example 3: $TZ_3T^\dagger=\hat Z_{1,2}Z_3$ where $\hat Z_{1,2}|a,b\rangle=(-1)^{ab}|a,b\rangle$ because:
$
\begin{align}
TZ_3T^\dagger|a,b,c\rangle&=TZ_3|a,b,c\oplus ab\rangle=(-1)^{c\oplus ab} T| a,b,c\oplus ab\rangle \\
& =(-1)^{c\oplus ab}|a,b,c\rangle =(-1)^c(-1)^{ab}|a,b,c\rangle=\hat Z_{1,2}Z_3|a,b,c\rangle \\
\end{align}
$
Therefore,
$
\begin{align}
&T(Z^{z_1}X^{x_1}\otimes Z^{z_2}X^{x_2}\otimes Z^{z_3}X^{x_3})=\bigg(T(Z^{z_1}X^{x_1}\otimes Z^{z_2}X^{x_2}\otimes Z^{z_3}X^{x_3})T^\dagger\bigg)T= \\
&=\bigg(CNOT^{x_2}_{1,3}CNOT_{2,3}^{x_1} \hat Z_{1,2}^{z_3} (Z_1^{z_2+x_2z_3}X_1^{x_1}\otimes Z_2^{z_2+x_1z_3}X_2^{x_2}\otimes Z_3^{z_3}X_3^{x_1x_2+x_3})\bigg)T
\end{align}
$
Similar to the Pauli and Clifford cases - we wish to have a Pauli-pad for Toffoli gate i.e., $(Z^{z'_1}X^{x_1}\otimes Z^{z'_2}X^{x'_2}\otimes Z^{z'_3}X^{x'_3})T$ but unfortunately we have a prefix of multiple $CNOT^x$ gates. note that $\hat Z_{1,2}^{z_3}$ can be represented as one $CNOT$ and two Hadamard gates.
The trick to remove the $CNOT