Editing Householder transformation (section)

====Quantum computation====

{{main|Grover's algorithm#Geometric proof of correctness}}

[[File:Grovers algorithm geometry.png|thumb|310px|Picture showing the geometric interpretation of the first iteration of Grover's algorithm. The state vector <math>|s\rang</math> is rotated towards the target vector <math>|\omega\rang</math> as shown.]]

[[quantum_logic_gate#Universal_quantum_gates|As unitary matrices are useful in quantum computation]], and Householder transformations are unitary, they are very useful in quantum computing.  One of the central algorithms where they're useful is Grover's algorithm, where we are trying to solve for a representation of an [[quantum oracle|oracle function]] represented by what turns out to be a Householder transformation:

<math>\begin{cases}
 U_\omega |x\rang = -|x\rang & \text{for } x = \omega \text{, that is, } f(x) = 1, \\
 U_\omega |x\rang = |x\rang & \text{for } x \ne \omega \text{, that is, } f(x) = 0.
\end{cases}</math>

(here the <math>|x\rangle</math> is part of the [[bra-ket notation]] and is analogous to <math>\vec x</math> which we were using previously)

This is done via an algorithm that iterates via the oracle function <math>U_\omega</math> and another operator <math>U_s</math> known as the ''Grover diffusion operator'' defined by

<math>|s\rangle = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle. </math>
and <math>U_s = 2 \left|s\right\rangle\!\! \left\langle s\right| - I</math>.