Editing Hadamard transform (section)

===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>.