Biến đổi Fourier lượng tử là một phép biến đổi tuyến tính trên các qubit (đơn vị cơ bản của thông tin lượng tử), phép biến đổi này tương tự như biến đổi Fourier rời rạc . Biến đổi Fourier lượng tử là một trong những thuật toán lượng tử quan trọng nhất, nó thường là một phần của các thuật toán lượng tử khác, đặc biệt là thuật toán Shor để phân tích thừa số nguyên tố và tính toán các logarit rời rạc.
Biến đổi Fourier lượng tử dựa trên thuật toán biến đổi Fourier nhanh của James Cooley và John Tukey . Nó có thể được thực hiện hiệu quả trên máy tính lượng tử , bởi nó có thể triệt tiêu các thành phần bằng cách nhân với các ma trận unita (áp dụng toán tử U ^ ( Q F T ) {\displaystyle {\hat {U}}^{(QFT)}} mạch lượng tử .
Biến đổi Fourier rời rạc "cổ điển" được định nghĩa như sau:
Dãy của N số phức : x 0 , x 1 , . . . , x N − 1 {\displaystyle x_{0},x_{1},...,x_{N-1}} N số phức y 0 , y 1 , . . . , y N − 1 {\displaystyle y_{0},y_{1},...,y_{N-1}}
y k = ∑ l = 0 N − 1 e − 2 π i N k l x l k = 0 , 1 , … , N − 1 ( 1 ) {\displaystyle y_{k}=\sum _{l=0}^{N-1}e^{-{\frac {2\pi i}{N}}kl}x_{l}\quad \quad k=0,1,\dots ,N-1\quad \quad \quad \quad (1)} với e là cơ số của lôgarit tự nhiên , i {\displaystyle i\,} đơn vị ảo ( i 2 = − 1 {\displaystyle i^{2}=-1} π {\displaystyle \pi } pi .
Đặt ω = e 2 π i N {\displaystyle \omega =e^{\frac {2\pi i}{N}}}
y k = 1 N ∑ j = 0 N − 1 x j ω j k {\displaystyle y_{k}={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}x_{j}\omega ^{jk}}
Như vậy, ta có thể xây dựng phép biến đổi Fourier thành ma trận unita F N {\displaystyle F_{N}}
F N = 1 N [ 1 1 1 1 ⋯ 1 1 ω ω 2 ω 3 ⋯ ω N − 1 1 ω 2 ω 4 ω 6 ⋯ ω 2 ( N − 1 ) 1 ω 3 ω 6 ω 9 ⋯ ω 3 ( N − 1 ) ⋮ ⋮ ⋮ ⋮ ⋮ 1 ω N − 1 ω 2 ( N − 1 ) ω 3 ( N − 1 ) ⋯ ω ( N − 1 ) ( N − 1 ) ] {\displaystyle F_{N}={\frac {1}{\sqrt {N}}}{\begin{bmatrix}1&1&1&1&\cdots &1\\1&\omega &\omega ^{2}&\omega ^{3}&\cdots &\omega ^{N-1}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&\cdots &\omega ^{2(N-1)}\\1&\omega ^{3}&\omega ^{6}&\omega ^{9}&\cdots &\omega ^{3(N-1)}\\\vdots &\vdots &\vdots &\vdots &&\vdots \\1&\omega ^{N-1}&\omega ^{2(N-1)}&\omega ^{3(N-1)}&\cdots &\omega ^{(N-1)(N-1)}\\\end{bmatrix}}} Tương tự với "cổ điển" , ta dùng các vector biểu diễn trạng thái lượng tử rồi áp dụng toán tử U ^ ( Q F T ) {\displaystyle {\hat {U}}^{(QFT)}}
Khi áp dụng cho một xâu n-qubit , ta được:
U ^ ( Q F T ) | b n − 1 b n − 2 . . . b 0 ⟩ = 1 2 n { | 0 ⟩ + e 2 π i [ . b 0 ] | 1 ⟩ } { | 0 ⟩ + e 2 π i [ . b 1 b 0 ] | 1 ⟩ } { | 0 ⟩ + e 2 π i [ . b n − 1 b n − 2 . . . b 0 ] | 1 ⟩ } ( 2 ) {\displaystyle {\hat {U}}^{(QFT)}|b_{n-1}b_{n-2}...b_{0}\rangle ={\frac {1}{\sqrt {2^{n}}}}\{|0\rangle \ +\ e^{2\pi i[.b_{0}]}\ |1\rangle \}\ \{|0\rangle \ +\ e^{2\pi i[.b_{1}b_{0}]}\ |1\rangle \}\ \{|0\rangle \ +\ e^{2\pi i[.b_{n-1}b_{n-2}...b_{0}]}\ |1\rangle \}\quad \quad \quad \quad (2)}
Xét với biến đổi Fourier "cổ điển":
Đặt 2 vector x T = ( x 0 , x 1 , . . . , x N − 1 ) {\displaystyle x^{T}=(x_{0},x_{1},...,x_{N-1})} y T = ( y 0 , y 1 , . . . , y N − 1 ) {\displaystyle y^{T}=(y_{0},y_{1},...,y_{N-1})} ( 1 ) {\displaystyle (1)}
y = U ( F T ) x {\displaystyle y=U^{(FT)}x}
Với U ( F T ) {\displaystyle U^{(FT)}} ma trận biến đổi tuyến tính của ma trận có các phần tử là:
U k l ( F T ) = 1 N e 2 π i k l N k , l = 0 , 1 , … , N − 1 ( 3 ) {\displaystyle U_{kl}^{(FT)}={\frac {1}{\sqrt {N}}}e^{\frac {2\pi ikl}{N}}\quad \quad k,l=0,1,\dots ,N-1\quad \quad \quad \quad (3)}
Từ công thức ( 3 ) {\displaystyle (3)}
U k l ( F T ) = U l k ( F T ) {\displaystyle U_{kl}^{(FT)}=U_{lk}^{(FT)}}
Hay nói cách khác, U ( F T ) {\displaystyle U^{(FT)}} ma trận đối xứng .
Tương tự, ở biến đổi Fourier lượng tử, ta xét trạng thái | l ⟩ {\displaystyle |l\rangle }
Sử dụng toán tử U ^ ( Q F T ) {\displaystyle {\hat {U}}^{(QFT)}} | l ⟩ {\displaystyle |l\rangle } | k ⟩ {\displaystyle |k\rangle }
U ^ ( Q F T ) | k ⟩ = 1 N ∑ l = 0 N − 1 e 2 π i k l N | l ⟩ {\displaystyle {\hat {U}}^{(QFT)}|k\rangle ={\frac {1}{\sqrt {N}}}\sum _{l=0}^{N-1}e^{\frac {2\pi ikl}{N}}|l\rangle }
Từ đó, ta thấy các phần tử ma trận của toán tử U ^ ( Q F T ) {\displaystyle {\hat {U}}^{(QFT)}}
U l k ( Q F T ) = ⟨ l | U ^ ( Q F T ) | k ⟩ = 1 N e 2 π i k l N = U l k ( F T ) = U k l ( F T ) = U k l ( Q F T ) {\displaystyle U_{lk}^{(QFT)}=\langle l|{\hat {U}}^{(QFT)}|k\rangle ={\frac {1}{\sqrt {N}}}e^{\frac {2\pi ikl}{N}}=U_{lk}^{(FT)}=U_{kl}^{(FT)}=U_{kl}^{(QFT)}}
Như vậy, U ^ ( Q F T ) {\displaystyle {\hat {U}}^{(QFT)}}
Để chứng minh tính unita của biến đổi Fourier lượng tử, ta cần biết đến hai công thức sau:
Đầu tiên, ta cần biết đến tổng hình học :
S = 1 + q + q 2 + q 3 + . . . + q N − 1 = ∑ l = 0 N − 1 q l = 1 − q N 1 − q ( 4 ) {\displaystyle S=1+q+q^{2}+q^{3}+...+q^{N-1}=\sum _{l=0}^{N-1}q^{l}={\frac {1-q^{N}}{1-q}}\quad \quad \quad \quad (4)}
Tiếp theo là:
T = 1 N ∑ l = 0 N − 1 e 2 π i M l N = { 1 , khi M = 0 0 , khi 0 < | M | < N ( 5 ) {\displaystyle T={\frac {1}{N}}\sum _{l=0}^{N-1}e^{\frac {2\pi iMl}{N}}={\begin{cases}1,&{\mbox{khi }}M=0\\0,&{\mbox{khi }}0<|M|<N\end{cases}}\quad \quad \quad \quad \quad (5)}
Chứng minh công thức này như sau:
1) Xét M = 0 {\displaystyle M=0} T = 1 N ∑ l = 0 N − 1 e 0 = 1 N ∑ l = 0 N − 1 1 = 1 N N = 1 {\displaystyle T={\frac {1}{N}}\sum _{l=0}^{N-1}e^{0}={\frac {1}{N}}\sum _{l=0}^{N-1}1={\frac {1}{N}}N=1} 2) Xét 0 < | M | < N {\displaystyle 0<\left|M\right|<N} tổng hình học T = 1 N ∑ l = 0 N − 1 e 2 π i M l N = 1 N ∑ l = 0 N − 1 [ e 2 π i l M N ] l = 1 N 1 − e 2 π i M 1 − e 2 π i M N = 0 {\displaystyle T={\frac {1}{N}}\sum _{l=0}^{N-1}e^{\frac {2\pi iMl}{N}}={\frac {1}{N}}\sum _{l=0}^{N-1}[e^{\frac {2\pi ilM}{N}}]^{l}={\frac {1}{N}}{\frac {1-e^{2\pi iM}}{1-e^{\frac {2\pi iM}{N}}}}=0} Do e 2 π i M = 1 {\displaystyle e^{2\pi iM}=1} 1 − e 2 π i M N ≠ 0 {\displaystyle 1-e^{\frac {2\pi iM}{N}}\neq 0} 0 < | M | < N {\displaystyle 0<\left|M\right|<N}
Áp dụng 2 công thức ( 4 ) {\displaystyle (4)} ( 5 ) {\displaystyle (5)}
[ U ( F T ) † U ( F T ) ] m n = ∑ l = 0 N − 1 U l m ( F T ) ∗ U l n ( F T ) {\displaystyle [U^{(FT)\dagger }U^{(FT)}]_{mn}=\sum _{l=0}^{N-1}U_{lm}^{(FT)^{*}}U_{ln}^{(FT)}}
= ∑ l = 0 N − 1 1 N e − 2 π i l m N e 2 π i l n N = 1 N ∑ l = 0 N − 1 e 2 π i ( n − m ) l N = δ m n {\displaystyle =\sum _{l=0}^{N-1}{\frac {1}{\sqrt {N}}}e^{-{\frac {2\pi ilm}{N}}}e^{\frac {2\pi iln}{N}}={\frac {1}{N}}\sum _{l=0}^{N-1}e^{\frac {2\pi i(n-m)l}{N}}=\delta _{mn}} Như vậy ta đã chứng minh biến đổi Fourier lượng tử có tính Unita
Biểu diễn mạch lượng tử cho biến đổi Fourier lượng tử cho 1,2,3 qubit trên wolfram[2] Xét một vài trường hợp đơn giản.
Với trường hợp chỉ có 1 qubit , ta có n = 1 {\displaystyle n=1} N = 2 n = 2 {\displaystyle N=2^{n}=2} trạng thái lượng tử cơ bản. Biến đổi Fourier lượng tử trong trường hợp này như sau:
U ^ ( Q F T ) | 0 ⟩ = 1 N ∑ l = 0 N − 1 e 2 π i 0 l N | l ⟩ = 1 2 { | 0 ⟩ + | 1 ⟩ } {\displaystyle {\hat {U}}^{(QFT)}|0\rangle ={\frac {1}{\sqrt {N}}}\sum _{l=0}^{N-1}e^{\frac {2\pi i0l}{N}}|l\rangle ={\frac {1}{\sqrt {2}}}\{|0\rangle +|1\rangle \}}
U ^ ( Q F T ) | 1 ⟩ = 1 N ∑ l = 0 N − 1 e 2 π i 1 l N | l ⟩ = 1 2 { | 0 ⟩ − | 1 ⟩ } {\displaystyle {\hat {U}}^{(QFT)}|1\rangle ={\frac {1}{\sqrt {N}}}\sum _{l=0}^{N-1}e^{\frac {2\pi i1l}{N}}|l\rangle ={\frac {1}{\sqrt {2}}}\{|0\rangle -|1\rangle \}}
Trong trường hợp này ta dễ thấy ma trận biến đổi của phép biến đổi Fourier lượng tử là:
F 2 1 = 1 2 [ 1 1 1 − 1 ] {\displaystyle \operatorname {F_{2^{1}}} ={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}} Ma trận trên tương tự như ma trận của cổng Hadamard . Vì thế, mạch lượng tử được sử dụng trong việc biến đổi Fourier lượng tử cho 1 qubit chỉ dùng 1 cổng Hadamard .
Xét trong trường hợp 2 qubit , ta có n = 2 {\displaystyle n=2} N = 2 n = 4 {\displaystyle N=2^{n}=4} trạng thái lượng tử cơ bản. Ta quy định | 00 ⟩ ≡ | 0 ⟩ {\displaystyle |00\rangle \equiv |0\rangle } | 01 ⟩ ≡ | 1 ⟩ {\displaystyle |01\rangle \equiv |1\rangle } | 10 ⟩ ≡ | 2 ⟩ {\displaystyle |10\rangle \equiv |2\rangle } | 11 ⟩ ≡ | 3 ⟩ {\displaystyle |11\rangle \equiv |3\rangle }
U ^ ( Q F T ) | 00 ⟩ = 1 4 ∑ l = 0 3 e 2 π i 0 l 4 | l ⟩ = 1 2 ( | 0 ⟩ + | 1 ⟩ + | 2 ⟩ + | 3 ⟩ ) {\displaystyle {\hat {U}}^{(QFT)}|00\rangle \ ={\frac {1}{\sqrt {4}}}\sum _{l=0}^{3}e^{\frac {2\pi i0l}{4}}|l\rangle ={\frac {1}{2}}(|0\rangle +|1\rangle +|2\rangle +|3\rangle )}
= 1 2 ( | 00 ⟩ + | 01 ⟩ + | 10 ⟩ + | 11 ⟩ ) = 1 2 ( | 0 ⟩ + | 1 ⟩ ) ( | 0 ⟩ + | 1 ⟩ ) , {\displaystyle ={\frac {1}{2}}(|00\rangle +|01\rangle +|10\rangle +|11\rangle )={\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle ),} U ^ ( Q F T ) | 01 ⟩ = 1 4 ∑ l = 0 3 e 2 π i 1 l 4 | l ⟩ = 1 2 ( | 0 ⟩ + i | 1 ⟩ − | 2 ⟩ − i | 3 ⟩ ) {\displaystyle {\hat {U}}^{(QFT)}|01\rangle \ ={\frac {1}{\sqrt {4}}}\sum _{l=0}^{3}e^{\frac {2\pi i1l}{4}}|l\rangle ={\frac {1}{2}}(|0\rangle +i|1\rangle -|2\rangle -i|3\rangle )}
= 1 2 ( | 00 ⟩ + i | 01 ⟩ − | 10 ⟩ − i | 11 ⟩ ) = 1 2 ( | 0 ⟩ − | 1 ⟩ ) ( | 0 ⟩ + i | 1 ⟩ ) , {\displaystyle ={\frac {1}{2}}(|00\rangle +i|01\rangle -|10\rangle -i|11\rangle )={\frac {1}{2}}(|0\rangle -|1\rangle )(|0\rangle +i|1\rangle ),} U ^ ( Q F T ) | 10 ⟩ = 1 4 ∑ l = 0 3 e 2 π i 2 l 4 | l ⟩ = 1 2 ( | 0 ⟩ − | 1 ⟩ + | 2 ⟩ − | 3 ⟩ ) {\displaystyle {\hat {U}}^{(QFT)}|10\rangle \ ={\frac {1}{\sqrt {4}}}\sum _{l=0}^{3}e^{\frac {2\pi i2l}{4}}|l\rangle ={\frac {1}{2}}(|0\rangle -|1\rangle +|2\rangle -|3\rangle )}
= 1 2 ( | 00 ⟩ − | 01 ⟩ + | 10 ⟩ − | 11 ⟩ ) = 1 2 ( | 0 ⟩ + | 1 ⟩ ) ( | 0 ⟩ − | 1 ⟩ ) , {\displaystyle ={\frac {1}{2}}(|00\rangle -|01\rangle +|10\rangle -|11\rangle )={\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ),} U ^ ( Q F T ) | 11 ⟩ = 1 4 ∑ l = 0 3 e 2 π i 3 l 4 | l ⟩ = 1 2 ( | 0 ⟩ − i | 1 ⟩ − | 2 ⟩ + i | 3 ⟩ ) {\displaystyle {\hat {U}}^{(QFT)}|11\rangle \ ={\frac {1}{\sqrt {4}}}\sum _{l=0}^{3}e^{\frac {2\pi i3l}{4}}|l\rangle ={\frac {1}{2}}(|0\rangle -i|1\rangle -|2\rangle +i|3\rangle )}
= 1 2 ( | 00 ⟩ − i | 01 ⟩ − | 10 ⟩ + i | 11 ⟩ ) = 1 2 ( | 0 ⟩ − | 1 ⟩ ) ( | 0 ⟩ − i | 1 ⟩ ) , {\displaystyle ={\frac {1}{2}}(|00\rangle -i|01\rangle -|10\rangle +i|11\rangle )={\frac {1}{2}}(|0\rangle -|1\rangle )(|0\rangle -i|1\rangle ),} Ma trận của phép biến đổi:
F 2 2 = 1 2 2 [ 1 1 1 1 1 i − 1 − i 1 − 1 1 − 1 1 − i − 1 i ] {\displaystyle \operatorname {F_{2^{2}}} ={\frac {1}{\sqrt {2^{2}}}}{\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix}}} Với trường hợp này, mạch lượng tử của biến đổi Fourier lượng tử ngoài các cổng Hadamard , còn cần sử dụng thêm một cổng điều khiển xoay pha R π 2 {\displaystyle R_{\frac {\pi }{2}}}
Mạch lượng tử của trường hợp 1, 2 và 3 qubit đầu vào được mô hình trình diễn trên wolfram[2]
Mạch lượng tử cho biến đổi Fourier lượng tử trên n qubits Như đã nói ở trên, biến đổi Fourier lượng tử là một thuật toán lượng tử nên có thể được cài đặt và thực hiện nhờ một mạch lượng tử.
Với một hệ cơ sở trực chuẩn là các vector :
| 0 ⟩ , | 1 ⟩ , . . . , | 2 n − 1 ⟩ {\displaystyle |0\rangle ,|1\rangle ,...,|2^{n}-1\rangle } Ta có thể biểu diễn một số x dưới dạng sau:
| x ⟩ = | x 1 , x 2 , . . . , x n ⟩ = | x 1 ⟩ | x 2 ⟩ . . . | x n ⟩ {\displaystyle |x\rangle =|x_{1},x_{2},...,x_{n}\rangle =|x_{1}\rangle |x_{2}\rangle ...|x_{n}\rangle }
với x = x 1 2 n − 1 + x 2 2 n − 2 + . . . + x n 2 0 {\displaystyle x=x_{1}2^{n-1}+x_{2}2^{n-2}+...+x_{n}2^{0}\quad }
Theo công thức ( 2 ) {\displaystyle (2)}
| x 1 , x 2 , . . . , x n ⟩ ↦ 1 2 n ( | 0 ⟩ + e 2 π i [ 0. x n ] | 1 ⟩ ) ( | 0 ⟩ + e 2 π i [ 0. x n − 1 x n ] | 1 ⟩ ) . . . ( | 0 ⟩ + e 2 π i [ 0. x 1 x 2 … x n ] | 1 ⟩ ) {\displaystyle |x_{1},x_{2},...,x_{n}\rangle \mapsto {\frac {1}{\sqrt {2^{n}}}}\ \left(|0\rangle +e^{2\pi i\,[0.x_{n}]}|1\rangle \right)\left(|0\rangle +e^{2\pi i\,[0.x_{n-1}x_{n}]}|1\rangle \right)...\left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}\ldots x_{n}]}|1\rangle \right)} Như vậy, biến đổi Fourier rời rạc trên trạng thái lượng tử của n qubit (để biểu diễn số N {\displaystyle N} cổng Hadamard và cổng điều khiển xoay pha . Tổng số lượng cổng sử dụng là 1 + 2 + . . . + n = n ( n + 1 ) / 2 = O ( n 2 ) {\displaystyle 1+2+...+n=n(n+1)/2=O(n^{2})}
Như các ví dụ trên và mạch lượng tử tổng quát, ta dễ thấy để triệt tiêu các thành phần, các phép biến đổi Fourier rời rạc được thực hiện qua O ( n 2 ) {\displaystyle O(n^{2})} cổng Hadamard và các cổng điều khiển xoay pha R π 2 k {\displaystyle R_{{\frac {\pi }{2}}^{k}}} n {\displaystyle n} k = 0 , 1 , . . . , n − 1 {\displaystyle k=0,1,...,n-1} [3] biến đổi Fourier rời rạc "cổ điển" cần dùng O ( n 2 n ) {\displaystyle O(n2^{n})} n {\displaystyle n} độ phức tạp thuật toán trong thời gian đa thức . Tuy nhiên, biến đổi Fourier lượng tử áp dụng trên một trạng thái lượng tử còn biến đổi Fourier rời rạc "cổ điển" lại áp dụng trên một vector, nên không phải tất cả công việc sử dụng biến đổi Fourier rời rạc "cổ điển" có thể tận dụng mức độ tăng độ phức tạp cấp số nhân này.
Ngày nay, trường hợp tốt nhất của thuật toán biến đổi Fourier lượng tử, chỉ sử dụng O ( n log n ) {\displaystyle O(n\log n)} cổng lượng tử , đã đạt được hiệu quả tốt.[4]
Biến đổi Fourier lượng tử là một thuật toán lượng tử quan trọng, nó thường là một phần của các thuật toán lượng tử khác, đặc biệt là thuật toán Shor để phân tích thừa số nguyên tố và tính toán các logarit rời rạc , thuật toán dự đoán pha lượng tử để ước tính giá trị riêng của các toán tử unita , và các thuật toán về vấn đề phân nhóm ẩn .
^ a b Reinhold, Blumel (2009). “Foundations of Quantum Mechanics: From Photons to Quantum Computers, chương 10” . ^ a b http://demonstrations.wolfram.com/QuantumFourierTransformCircuit/ Biểu diễn mạch lượng tử 1,2,3 qubit trên wolfram ^ Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information . Cambridge: Cambridge University Press. ISBN 0-521-63503-9 OCLC 174527496 .^ L. Hales, S. Hallgren, An improved quantum Fourier transform algorithm and applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.515, November 12–14, 2000 
![{\displaystyle {\hat {U}}^{(QFT)}|b_{n-1}b_{n-2}...b_{0}\rangle ={\frac {1}{\sqrt {2^{n}}}}\{|0\rangle \ +\ e^{2\pi i[.b_{0}]}\ |1\rangle \}\ \{|0\rangle \ +\ e^{2\pi i[.b_{1}b_{0}]}\ |1\rangle \}\ \{|0\rangle \ +\ e^{2\pi i[.b_{n-1}b_{n-2}...b_{0}]}\ |1\rangle \}\quad \quad \quad \quad (2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1205ac84149fa9cc87c5d23f0700521cf65aa2e6)
![{\displaystyle T={\frac {1}{N}}\sum _{l=0}^{N-1}e^{\frac {2\pi iMl}{N}}={\frac {1}{N}}\sum _{l=0}^{N-1}[e^{\frac {2\pi ilM}{N}}]^{l}={\frac {1}{N}}{\frac {1-e^{2\pi iM}}{1-e^{\frac {2\pi iM}{N}}}}=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6b80027a693336329490683fc48759667624bbb)
![{\displaystyle [U^{(FT)\dagger }U^{(FT)}]_{mn}=\sum _{l=0}^{N-1}U_{lm}^{(FT)^{*}}U_{ln}^{(FT)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c533b080eac33d4f5b786d3183d21d73b73c9d53)
![{\displaystyle |x_{1},x_{2},...,x_{n}\rangle \mapsto {\frac {1}{\sqrt {2^{n}}}}\ \left(|0\rangle +e^{2\pi i\,[0.x_{n}]}|1\rangle \right)\left(|0\rangle +e^{2\pi i\,[0.x_{n-1}x_{n}]}|1\rangle \right)...\left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}\ldots x_{n}]}|1\rangle \right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca465eccfaa4eede13984aaaba405b723690a9e5)
