« Maths, Informatique, Jeux »

Prerequisites

Unless otherwise specified, we use the notations described in this section as well as other classical ones not mentioned below. We assume basic knowledge of quantum computing: an excellent introduction is the book of Nielsen and Chuang [NieChu2007]. The paper of Lomont [Lom2004] also contains a presentation of the main ideas as well as a good overview of the Hidden Subgroup Problem and its status as of 2004. Some advanced mathematical concepts will also be required and sometimes recalled as needed.

$\log$ (binary logarithm), $φ (n)$ (Euler's totient function), $∣ S ∣$ (cardinality).
numbers: $ⅈ$ (imaginary unit), $ⅇ$ (euler's number), $c^{*}$ (conjugate), $⌊ c ⌋$ and $⌈ f ⌉$ (ceiling and floor).
limit and asymptotic approximation: $f \to c$ ( $f$ has limit $c$ ), $f = O (g)$ ( $f$ bounded above by a constant times $g$ ), $f = Ω (g)$ ( $f$ bounded below by a constant times $g$ ), $f = Θ (g)$ (the two previous equalities hold), $f = o (g)$ ( $f$ bounded above by $ε g$ with $ε \to 0$ ), $f \sim g$ ( $f$ and $g$ are equivalent), $comp (f)$ means the worse-case complexity of $f$ , $poly (x)$ means $O (P (x))$ for polynomial $P$ of $x$ . Recall that $n! \sim \sqrt{2 π n} {(\frac{n}{ⅇ})}^{n}$ (Stirling formula) and $\frac{φ (n)}{n} = Ω (\frac{1}{\log (\log (n))})$ .
Group laws are noted + for abelian groups and by a multiplication for general groups. $ℤ_{2}^{n}$ may be seen as $n$ -bits numbers, so in that case ⊕ is sometimes used instead of +.
algebraic structures: $G_{1} \oplus G_{2}$ (direct sum), $G_{1} \times G_{2}$ (direct product), $G_{1} ⋊_{φ} G_{2}$ (semi-direct product), $G_{1} ≀ G_{2}$ (wreath product), $\frac{G}{H}$ (quotient), $H ⊲ G$ (normality), $Ker f$ (kernel), $Imf$ (image), $G_{1} ≅ G_{2}$ (isomorphy), $g H$ and $H g$ (left and right coset), $⟨ S ⟩$ (group generated by $S$ ), $N (S) = {g \in G, S = g S g^{- 1}}$ (normalizer of $S$ ), $[G_{1}, G_{2}] =$ $⟨ \{g_{1}^{- 1} g_{2}^{- 1} g_{1} g_{2}| (g_{1}, g_{2}) \in G_{1} \times G_{2}\} ⟩$ , $[G, G]$ (derived or commutator subgroup), $Φ (G) = ⋂_{H proper maximal subgroup G} H$ (Frattini subgroup), $Z (G)$ (center of $G$ ). We also simply use the term "Coset" for left coset. We also define the normal subgroup $M_{G} = ⋂_{H subgroup of G} N (H)$ .
some algebraic structures: $ℤ_{k}$ (cyclic group $\frac{ℤ}{k ℤ}$ ), $ℤ_{p}^{*}$ with $p$ prime (multiplicative group of invertible elements of $ℤ_{p}$ ), $ℚ_{8}$ (quaternion group), $D_{N}$ (dihedral group), $S_{N}$ (symmetric group), $A_{N}$ (alternating group), ${GL}_{n} (K)$ (general linear group of degree $n$ over a field $K$ ). $F_{q}$ is the finite field of order $q$ . $GL (n, q) = {GL}_{n} (F_{q})$ .
vectors and matrices: $x . y = \sum_{i = 1}^{n} x_{i} y_{i}$ , $0^{n}$ (zero vector of length $n$ ), $A^{†} = {(A^{*})}^{t} = {(A^{t})}^{*}$ (hermitian conjugate), ${⟨ A, B ⟩}_{F}$ (Frobenius hermitian product), ${‖ A ‖}_{F} = \sqrt{tr (A^{†} A)}$ (Frobenius norm). Recall that if $U, V$ are unitary, ${‖ U A V ‖}_{F} = {‖ A ‖}_{F}$ .
quantum mechanics: $∣ x ⟩$ , $⟨ x ∣$ , $⟨ x ∣ y ⟩$ , $∣ x ⟩ ∣ y ⟩$ (bra-ket notations).
quantum circuit: (measurement), $H$ (hadamard gate), $U \otimes V$ and $U^{\otimes n}$ (tensor product of unitary transforms). For any function $f : {ℤ_{2}}^{n} \to {ℤ_{2}}^{m}$ , we define the gate $U_{f}$ by $\forall (x, y) \in ℤ_{2}^{n} \times ℤ_{2}^{m}, U_{f} (∣ x ⟩ ∣ y ⟩) = ∣ x ⟩ ∣ f (x) \oplus y ⟩$ . If $f$ can be implemented using a $poly (n)$ complexity then it is also the case for the quantum version $U_{f}$ .
probability theory: $P (X)$ (probability of an event $X$ ), $P (\frac{X}{Y})$ (conditional probability of $X$ given $Y$ ), $E (X)$ (mean). To bound probabilities, we use variants of Hoeffding's inequality: if we have independent bounded variables $X_{k} \in [0, 1]$ then their sum $S = \sum_{k = 1}^{n} X_{k}$ satisfies $P (S - E (S) \geq t) \leq \exp (- \frac{2 t^{2}}{n})$ .
number theory: let $p$ be an odd prime, the Legendre symbol $(\frac{a}{p})$ is 0 if $a$ is a multiple of $p$ and $a^{\frac{(p - 1)}{2}} \mod (p) = \pm 1$ otherwise.

back to index

This page is W3C-compliant - Author: Frédéric WANG