The Permanent and planar graphs

Computational Complexity is a really fascinating area of research. One particular surprising fact that i learned years ago is the discrepancy between the computational effort to compute the determinant of a matrix and the permanent of a matrix. The determinant is defined as:
\begin{equation}
\text{det}(\text{A}) = \sum_{\sigma \in S_n}\text{sign}(\sigma)\prod^n_{i=1}a_{i,\sigma_i}
\end{equation} and the permanent is
\begin{equation}
\text{perm}(\text{A}) = \sum_{\sigma \in S_n}\prod^n_{i=1}a_{i,\sigma_i}
\end{equation} The difference in notation is minimal. The determinant considers the sign of the permutations $\sigma$ whereof the permanent does not. This little difference is responsible for the huge gap between the necessary resources that are needed in order to compute the actual value of these functions. The determinant can be evaluated in time that is polynomial in the dimension $n$, whereof the permanent is only computable in time that is exponential in $n$, e.g., using the $\mathcal{O}(n2^n)$ algorithm of Ryser. In the year 1979 Leslie Valiant [1,2] showed that the permanent is even #P-complete and he shows the same for any computation of $\text{perm}(\text{A}) \mod{p}$ for $p > 2$. To proof this, Valiant created a graph that encodes a boolean formula $f$. Due to his clever construction, the permanent of the graph's adjacency matrix is equal to the number of satisfying solution of the boolean formula $f$. It is a beutiful result and shows clearly that the computation of the permanent can probably not be done in an efficient way, i.e., polynomial in the matrix dimension. Note that if someone could compute the number of satisfying solutions of a formula $f$, such an algorithm can also be used to:

1. Decide if a given formula $f$ satisfiable, i.e. to solve the $\text{SAT}$ problem
2. If $f$ is satisfiable, to give a satisfying assignment of its variables. (Can be used to factorize integers)

Simon's problem for n = 4

To show that quantum computers are indeed able to solve some problems more efficiently than classical computers, one of the first problems that were published was Simon's problem.

Definition [Simon's problem] Let $f:\{0,1\}^n \rightarrow \{0,1\}^n$ with the property that for $x,y \in \{0,1\}^n$ it is $f(x) = f(y)$ if and only if $x = y \oplus a$, for some fix value $a \in \{0,1\}^n$. Given $f$, the task is to find $a$.

As usual the $\oplus$ is the bitwise XOR-function. On a classical computer, Simon's problem can only be solved in time that is exponential in $n$, whereof on a QC already $\mathcal{O}(n)$ queries are enough.

Simon's problem can also be seen as some kind of period finding problem. Assume you have a function $f$ and for $f$ it holds that:
\begin{align}
f(1) &= e_1 \\
f(2) &= e_2 \\
... &\\
f(a-1) &= e_{a-1}\\
f(a) &= e_a = 1\\
f(a+1) &= f(1) = e_1\\
f(a+2) &= f(2) = e_2 \\
 ... &
\end{align}
A non-trivial function that behaves like this is, e.g., the function $f_{p,g}(x) = g^x \pmod{p}$, if $a$ is the order of $g$ in $\mathbb{F}^*_p$ and whenever $x \oplus a = x+a$. This is a very special setup and is almost always not fulfilled for random primes $p$. But, e.g., whenever $a = 2^t$ and $p-1=2^{t+1}$ this holds. For example $p=17$ and $g=2$. Then $f_{17,2}(x)$ has the described property and is a valid function according to Simon's problem definition.