Editing Hadamard transform (section)

==Quantum computing applications==
The Hadamard transform is used extensively in [[quantum computing]]. The 2&nbsp;×&nbsp;2 Hadamard transform <math>H_1</math> is the [[quantum logic gate]] known as the Hadamard gate, and the application of a Hadamard gate to each qubit of an {{nowrap|<math>n</math>-qubit}} register in parallel is equivalent to the Hadamard transform {{nowrap|<math>H_n</math>.}}

===Hadamard gate===
{{further|Quantum gate#Hadamard gate}}
In quantum computing, the Hadamard gate is a one-[[qubit]] [[rotation]], mapping the qubit-basis states <math>|0 \rangle </math> and <math>|1 \rangle </math> to two superposition states with equal weight of the computational [[Basis (linear algebra)|basis]] states <math>|0 \rangle </math> and <math>|1 \rangle </math>. Usually the phases are chosen so that
<math display="block">H=\frac{|0\rangle+|1\rangle}{\sqrt{2}}\langle0|+\frac{|0\rangle-|1\rangle}{\sqrt{2}}\langle1|</math>

in [[Dirac notation]]. This corresponds to the [[transformation matrix]]
<math display="block">H_1=\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}</math>
in the <math>|0 \rangle , |1 \rangle </math> basis, also known as the [[computational basis]]. The states <math display="inline"> \frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt{2}}</math> and <math display="inline">\frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt{2}}</math> are known as <math>\left|\boldsymbol{+}\right\rangle</math> and <math>\left|\boldsymbol{-}\right\rangle</math> respectively, and together constitute the [[polar basis]] in [[quantum computing]].

===Hadamard gate operations===

<math display="block">\begin{align}
  H(|0\rangle) &= \frac{1}{\sqrt 2}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle =: |+\rangle\\
  H(|1\rangle) &= \frac{1}{\sqrt 2}|0\rangle - \frac{1}{\sqrt{2}}|1\rangle =: |-\rangle\\
  H(|+\rangle) &= H\left( \frac{1}{\sqrt 2}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle \right) = \frac{1}{2}\Big( |0\rangle + |1\rangle\Big) + \frac{1}{2}\Big(|0\rangle - |1\rangle\Big) = |0\rangle\\
  H(|-\rangle) &= H\left( \frac{1}{\sqrt 2}|0\rangle - \frac{1}{\sqrt{2}}|1\rangle \right) = \frac{1}{2}\Big( |0\rangle + |1\rangle\Big) - \frac{1}{2}\Big(|0\rangle - |1\rangle\Big) = |1\rangle
\end{align}</math>

One application of the Hadamard gate to either a 0 or 1 qubit will produce a [[quantum state]] that, if observed, will be a 0 or 1 with equal probability (as seen in the first two operations). This is exactly like flipping a fair coin in the standard [[Probabilistic Turing machine|probabilistic model of computation]].  However, if the Hadamard gate is applied twice in succession (as is effectively being done in the last two operations), then the final state is always the same as the initial state.

===Hadamard transform in quantum algorithms===

Computing the quantum Hadamard transform is simply the application of a Hadamard gate to each qubit individually because of the tensor product structure of the Hadamard transform. This simple result means the quantum Hadamard transform requires <math>\log_2 N </math> operations, compared to the classical case of <math>N \log_2 N</math> operations.


For an <math>n</math>-qubit system, [[Hadamard gates]] acting on each of the <math>n</math> qubits (each initialized to the <math>|0\rangle</math>) can be used to prepare uniform [[quantum superposition]] states 
when <math>N</math> is of the form <math>N = 2^n</math>.
In this case case with <math>n</math> qubits, the combined Hadamard gate <math>H_n</math> is expressed as the tensor product of <math>n</math> Hadamard gates:
<math>H_n = \underbrace{H \otimes H \otimes \ldots \otimes H}_{n \text{ times}}</math>

The resulting uniform quantum superposition state is then:
<math> H_{n} |0\rangle^{\otimes n} =  \frac{1}{\sqrt{2^n}} \sum_{j=0}^{2^n-1} |j\rangle</math>
This generalizes the preparation of uniform quantum states using Hadamard gates for any <math>N = 2^n</math>.<ref name="Nielsen-Chuang">{{Cite book|title=Quantum Computation and Quantum Information|last1=Nielsen|first1=Michael A.|last2=Chuang|first2=Isaac|date=2010|publisher=[[Cambridge University Press]]|isbn=978-1-10700-217-3|location=Cambridge|oclc=43641333|author-link=Michael Nielsen|author-link2=Isaac Chuang|url=https://www.cambridge.org/9781107002173}}</ref>

[[#Measurement|Measurement]] of this uniform quantum state results in a [[Random number generation|random]] state between <math>|0\rangle</math> and {{nowrap|<math>|N-1\rangle</math>.}}

Many [[quantum algorithm]]s use the Hadamard transform as an initial step, since as explained earlier, it maps ''n'' qubits initialized with <math>|0 \rangle</math> to a superposition of all 2<sup>''n''</sup> orthogonal states in the <math> |0 \rangle , |1 \rangle </math> basis with equal weight. For example, this is used in the [[Deutsch–Jozsa algorithm]], [[Simon's algorithm]], the [[Bernstein–Vazirani algorithm]], and in [[Grover's algorithm]]. Note that [[Shor's algorithm]] uses both an initial Hadamard transform, as well as the [[quantum Fourier transform]], which are both types of [[Fourier transform on finite groups|Fourier transforms on finite groups]]; the first on <math>(\Z / 2 \Z)^n</math> and the second on <math>\Z /2^n \Z</math>.

Preparation of uniform quantum superposition states in the general case, when <math>N </math> ≠  <math>2^n</math> is non-trivial and requires more work. 
An efficient and deterministic approach for preparing the superposition state 
<math 
display="block">  |\Psi\rangle = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} |j\rangle  </math>
with a gate complexity and circuit depth of only <math> O(\log_2 N)</math> for all <math>N</math> was recently presented.<ref name="shukla2024efficient">
{{cite journal
  | author = Alok Shukla and Prakash Vedula
  | title = An efficient quantum algorithm for preparation of uniform quantum superposition states
  | journal = Quantum Information Processing
  | volume = 23:38
  | issue = 1
  | year = 2024
  | page = 38
 | doi = 10.1007/s11128-024-04258-4
  | arxiv = 2306.11747
  | bibcode = 2024QuIP...23...38S
 }}
</ref>  This approach requires only 
<math> n = \lceil \log_2 N \rceil</math> 
qubits. Importantly, neither ancilla qubits nor any quantum gates with multiple controls are needed in this approach for creating the uniform superposition state  <math> |\Psi\rangle </math>.