Content deleted Content added
Petr Matas (talk | contribs) →Unitarity: definition of F† |
m Added some notes for clarity and flow, mostly to help distinguish full basis states from qubit states. |
||
Line 43:
:<math> |0\rangle, \ldots , |2^n - 1\rangle. </math>
The basis states enumerate all the possible states of the qubits:
:<math> | x \rangle = | x_1 x_2 \ldots x_n \rangle = | x_1 \rangle \otimes | x_2 \rangle \otimes \cdots \otimes | x_n \rangle</math>
where, with tensor product notation <math>\otimes</math>, <math>|x_j\rangle</math> indicates that qubit <math>j</math> is in state <math>x_j</math>, with <math>x_j</math> either 0 or 1. By convention, the basis state index <math>x</math> orders the possible states of the qubits lexicographically, i.e., by converting from binary to decimal in this way:
:<math> x = x_1 2^{n-1} + x_2 2^{n-2} +\cdots + x_n 2^0.\quad </math>
It is also useful to borrow fractional binary notation:
:<math> [0. x_1 \ldots x_m] = \sum_{k = 1}^m x_k 2^{-k}.</math>
For instance, <math>[0.x_1] = \frac{x_1}{2}</math> and <math>[0.x_1 x_2] = \frac{x_1}{2}+\frac{x_2}{2^2}.</math>
With this notation, the action of the quantum Fourier transform can be expressed as:
:<math>|x_1 x_2 \ldots x_n \rangle \mapsto \frac{1}{\sqrt{N}} \ \left(|0\rangle + e^{2 \pi i \, [0.x_n] }|1\rangle\right) \otimes \left(|0\rangle + e^{2 \pi i \, [0.x_{n-1} x_n] }|1\rangle\right) \otimes \cdots \otimes \left(|0\rangle + e^{2 \pi i \, [0.x_1 x_2 \ldots x_n] }|1\rangle\right)
where the output qubit 1 is in a superposition of state <math>|0\rangle</math> and <math>e^{2 \pi i \, [0.x_n] }|1\rangle</math>, and so on for the other qubits.
In other words, the discrete Fourier transform, an operation on ''n''-qubits, can be factored into the tensor product of ''n'' single-qubit operations, suggesting it is easily represented as a [[quantum circuit]]. In fact, each of those single-qubit operations can be implemented efficiently using a [[Hadamard gate]] and [[Quantum_gate#Controlled_gates|controlled]] [[Quantum_gate#Phase_shift_gates|phase gate]]s. The first term requires one Hadamard gate, the next one requires a Hadamard gate and a controlled phase gate, and each following term requires an additional controlled phase gate. Summing up the number of gates gives <math>1 + 2 + \cdots + n = n(n+1)/2 = O(n^2)</math> gates, which is polynomial in the number of qubits.
| |||