Mengapa Transformasi Fourier Transform dapat diimplementasikan secara efisien sebagai sirkuit kuantum?

Ini adalah hasil yang terkenal bahwa Discrete Fourier Transform (DFT) dari $N=2^n$ bilangan memiliki kompleksitas $\mathcal O(n2^n)$ dengan algoritma yang paling dikenal , sementara melakukan transformasi Fourier dari amplitudo keadaan kuantum, dengan klasik Algoritma QFT , hanya membutuhkan gerbang dasar $\mathcal O(n^2)$ .

Adakah alasan yang diketahui mengapa hal ini terjadi? Maksud saya apakah ada karakteristik DFT yang diketahui yang memungkinkan untuk mengimplementasikan "versi kuantum" yang efisien.

Memang, DFT lebih dari $N$ -dimensi vektor dapat dianggap sebagai operasi linear

$$\vec y=\operatorname{DFT} \vec x, \qquad \text{DFT}_{jk}\equiv \frac{1}{\sqrt N}\exp\left(\frac{2\pi i}{N}jk\right).$$

"Versi kuantum" dari masalah ini adalah tugas, mengingat status kuantum $|\boldsymbol x\rangle\equiv\sum_{k=1}^N x_k|k\rangle$ , memperoleh keadaan keluaran $|\boldsymbol y\rangle\equiv\sum_{k=1}^N y_k |k\rangle$ sehingga

$$|\boldsymbol y\rangle=\operatorname{DFT}|\boldsymbol x\rangle=\operatorname{QFT}|\boldsymbol x\rangle.$$

1. Penyederhanaan pertama tampaknya berasal dari fakta bahwa, karena linearitas QM, kita dapat fokus pada dasar keadaan $|j\rangle, \,\,j=1,...,N$ , dengan evolusi vektor umum$|\boldsymbol x\rangle$ kemudian datang secara gratis.
2. Jika $N=2^n$ , seseorang dapat mengekspresikan $|j\rangle$ dalam basis dua, memiliki $|j\rangle=|j_1,...,j_n\rangle$ .
3. Dalam algoritma QFT standar seseorang kemudian mengeksploitasi fakta bahwa transformasi dapat ditulis sebagai $$|j_1,...,j_n\rangle\to2^{-n/2}\bigotimes_{l=1}^n\big[|0\rangle+\exp(2\pi i (0.j_{n-l+1}\cdots j_{n}))|1\rangle\big],$$ yang kemudian dapat diimplementasikan sebagai rangkaian kuantum dari bentuk $$\operatorname{QFT}|j_1,...,j_n\rangle=\Big(\prod_{k=1}^n \mathcal U_k\Big)|j_1,...,j_n\rangle,$$ di mana $\mathcal U_k$ diimplementasikan dengan $\mathcal O(n)$ gerbang SD.

Misalkan kita sekarang memiliki beberapa transformasi kesatuan , dan kami ingin menemukan rangkaian yang mengimplementasikan secara efisien transformasi kuantum yang ekivalen | y ⟩ = A | x ⟩ . Dua trik pertama yang disebutkan di atas selalu dapat diterapkan, tetapi kemudian tidak penting kapan dan bagaimana poin lainnya dapat digunakan untuk mendapatkan hasil efisiensi seperti yang kami miliki untuk QFT.$A$

$$|\boldsymbol y\rangle=A|\boldsymbol x\rangle.$$

Adakah kriteria yang diketahui untuk hal ini benar? Atau dengan kata lain, apakah mungkin untuk secara tepat menjabarkan apa karakteristik DFT yang memungkinkan untuk mengimplementasikan transformasi kuantum yang terkait secara efisien?

Pengantar Transformasi Fourier Diskrit Klasik:

DFT mengubah urutan bilangan kompleks { x n } : = x 0 , x 1 , x 2 , . . . , X N - 1 ke urutan lain dari bilangan kompleks { X k } : = X 0 , X 1 , X 2 , . . . yang didefinisikan oleh X k = N - 1$N$$\{\mathbf{x}_n\}:=x_0,x_1,x_2,...,x_{N-1}$$\{\mathbf{X}_k\}:=X_0,X_1,X_2,...$ Kita dapat mengalikan dengan konstanta normalisasi yang sesuai sebagaimana diperlukan. Selain itu, apakah kita mengambil tanda plus atau minus dalam rumus tergantung pada konvensi yang kita pilih.

$$X_k=\sum_{n=0}^{N-1}x_n.e^{\pm\frac{2\pi i k n}{N}}$$

---

Misalkan, diberikan bahwa dan x = ( 1 2 - i - i - 1 + 2 i ) .$N=4$$\mathbf{x}=\begin{pmatrix} 1 \\ 2-i \\ -i \\ -1+2i \end{pmatrix}$

Kita perlu menemukan vektor kolom . Metode umum sudah ditampilkan di halaman Wikipedia . Tetapi kami akan mengembangkan notasi matriks untuk hal yang sama. X dapat dengan mudah diperoleh dengan pra mengalikan $\mathbf{X}$$\mathbf{X}$$\mathbf{x}$ dengan matriks:

$$M=\frac{1}{\sqrt{N}}\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & w & w^{ 2 } & w^{ 3 } \\ 1 & w^ 2 & w^4 & w^6 \\ 1 & w^3 & w^6 & w^9 \end{pmatrix}$$

dimana adalah e - 2 π $w$ . Setiap elemen dari matriks pada dasarnya adalahwij. $e^{\frac{-2\pi i}{N}}$$w^{ij}$$\frac{1}{\sqrt{N}}$ hanyalah konstanta normalisasi.

Akhirnya, ternyata menjadi: $\mathbf{X}$$\frac{1}{2}\begin{pmatrix} 2 \\ -2-2i \\ -2i \\ 4+4i \end{pmatrix}$ .

Sekarang, duduk sebentar dan perhatikan beberapa properti penting:

• Semua kolom dari matriks saling orthogonal.$M$
• Semua kolom memiliki magnitudo 1 .$M$$1$
• Jika Anda memposting kalikan $M$ dengan vektor kolom yang memiliki banyak nol (spread besar) Anda akan berakhir dengan vektor kolom dengan hanya beberapa nol (spread sempit). Kebalikannya juga berlaku. (Memeriksa!)

Sangat mudah diperhatikan bahwa DFT klasik memiliki kompleksitas waktu . Itu karena untuk mendapatkan setiap baris X , operasi N perlu dilakukan. Dan ada baris N di $\mathcal O(N^2)$$\mathbf{X}$$N$$N$$\mathbf{X}$ .

---

Transformasi fourier cepat:

Sekarang, mari kita lihat transformasi Fast Fourier. Transformasi Fourier cepat menggunakan simetri transformasi Fourier untuk mengurangi waktu komputasi. Sederhananya, kami menulis ulang transformasi Fourier ukuran sebagai dua transformasi Fourier ukuran N / 2 - istilah aneh dan genap. Kami kemudian mengulangi ini berulang-ulang untuk mengurangi waktu secara eksponensial. Untuk melihat bagaimana ini bekerja secara rinci, kita beralih ke matriks transformasi Fourier. Sementara kita melewati ini, mungkin perlu untuk memiliki DFT 8 di depan Anda untuk melihatnya. Perhatikan bahwa eksponen telah ditulis modulo 8 , karena w 8 = 1 .$N$$N/2$$\text{DFT}_8$$8$$w^8 = 1$

Perhatikan bagaimana baris sangat mirip dengan baris j + 4 . Juga, perhatikan bagaimana kolom j sangat mirip dengan kolom j + 4 . Termotivasi oleh ini, kita akan membagi transformasi Fourier menjadi kolom genap dan ganjil.$j$$j + 4$$j$$j + 4$

Pada frame pertama, kami telah mewakili seluruh Fourier transform matriks dengan menggambarkan baris th dan k kolom th: w j k . Dalam bingkai berikutnya, kita memisahkan kolom ganjil dan genap, dan juga memisahkan vektor yang akan diubah. Anda harus meyakinkan diri sendiri bahwa kesetaraan pertama benar-benar adalah kesetaraan. Pada frame ketiga, kita menambahkan sedikit simetri dengan memperhatikan bahwa w j + N / 2 = - w j (karena w n / 2 = - 1 ).$j$$k$$w^{jk}$$w^{j+N/2} = −w^j$$w^{n/2} = −1$

Perhatikan bahwa sisi ganjil dan genap mengandung istilah . Tetapi jika w adalah akar ke-N primitif persatuan, maka w 2 adalah akar ke- N primitif dan ke- 2 . Oleh karena itu, matriks yang entri j , k th adalah w 2 j k benar-benar hanya DFT ( N / 2 ) ! Sekarang kita dapat menulis DFT N dengan cara baru: Sekarang anggaplah kita menghitung transformasi Fourier dari fungsi f ( x $w^{2jk}$$w$$w^2$$N/2$$j$$k$$w^{2jk}$$\text{DFT}_{(N/2)}$$\text{DFT}_N$$f(x)$. Kita bisa menulis manipulasi atas sebagai persamaan yang menghitung jangka j f ( j ) .$\hat{f}(j)$

Catatan: QFT pada gambar hanya singkatan dari DFT dalam konteks ini. Juga, M mengacu pada apa yang kita sebut N.

Ini mengubah perhitungan menjadi dua aplikasi DFT ( N / 2 ) . Kita bisa mengubahnya menjadi empat aplikasi DFT ( N / 4 ) , dan sebagainya. Selama N = 2 n untuk beberapa n , kita dapat memecah perhitungan DFT N menjadi N perhitungan DFT 1 = $\text{DFT}_N$$\text{DFT}_{(N/2)}$$\text{DFT}_{(N/4)}$$N = 2n$$n$$\text{DFT}_N$$N$$\text{DFT}_1 = 1$ . Ini sangat menyederhanakan perhitungan kami.

Dalam kasus Fast Fourier transform, kompleksitas waktu berkurang menjadi (coba buktikan sendiri). Ini adalah peningkatan besar pada DFT klasik dan cukup banyak algoritma canggih yang digunakan dalam sistem musik modern seperti iPod Anda!$\mathcal{O}(N\log(N))$

---

Transformasi Quantum Fourier dengan gerbang kuantum:

Kekuatan FFT adalah kita dapat menggunakan simetri transformasi Fourier diskrit untuk keuntungan kita. Aplikasi sirkuit QFT menggunakan prinsip yang sama, tetapi karena kekuatan QFT superposisi bahkan lebih cepat.

QFT dimotivasi oleh FFT sehingga kami akan mengikuti langkah-langkah yang sama, tetapi karena ini adalah algoritma kuantum implementasi langkah-langkah akan berbeda. Artinya, pertama kita mengambil Fourier transform dari bagian aneh dan bahkan, kemudian kalikan istilah aneh oleh fase .$w^{j}$

Dalam algoritma kuantum, langkah pertama cukup sederhana. Istilah ganjil dan genap sama-sama dalam superposisi: istilah ganjil adalah mereka yang bit paling signifikan adalah , dan genap dengan 0 . Oleh karena itu, kita dapat menerapkan QFT ( N / 2 ) untuk istilah ganjil dan genap secara bersamaan. Kami melakukan ini dengan menerapkan, kami hanya akan menerapkan QFT ( N / 2 ) ke n - 1 bit yang paling signifikan, dan menggabungkan kembali yang aneh dan bahkan tepat dengan menerapkan Hadamard ke bit yang paling tidak signifikan.$1$$0$$\text{QFT}_{(N/2)}$$\text{QFT}_{(N/2)}$$n-1$

$j$$w^{j}$$1$$0$

Catatan: Dalam gambar M mengacu pada apa yang kita sebut N.

The phase associated with each controlled phase shift should be equal to $w^{j}$ where $j$ is associated to the $k$-th bit by $j = 2k$. Thus, apply the controlled phase shift to each of the first $n − 1$ qubits, with the least significant bit as the control. With the controlled phase shift and the Hadamard transform, $\text{QFT}_N$ has been reduced to $\text{QFT}_{(N/2)}$.

Note: In the image, M refers to what we are calling N.

Example:

Lets construct $\text{QFT}_3$. Following the algorithm, we will turn $\text{QFT}_3$ into $\text{QFT}_2$ and a few quantum gates. Then continuing on this way we turn $\text{QFT}_2$ into $\text{QFT}_1$ (which is just a Hadamard gate) and another few gates. Controlled phase gates will be represented by $R_\phi$. Then run through another iteration to get rid of $\text{QFT}_2$. You should now be able to visualize the circuit for $\text{QFT}$ on more qubits easily. Furthermore, you can see that the number of gates necessary to carry out $\text{QFT}_N$ it takes is exactly

$$\sum_{i=1}^{\log(N)} i=\log(N)(\log(N)+1)/2 = \mathcal{O}(\log^2 N)$$

---

Sources:

1. https://en.wikipedia.org/wiki/Discrete_Fourier_transform

2. https://en.wikipedia.org/wiki/Quantum_Fourier_transform

3. Quantum Mechanics and Quantum Computation MOOC (UC BerkeleyX) - Lecture Notes : Chapter 5

^{P.S: This answer is in its preliminary version. As @DaftWillie mentions in the comments, it doesn't go much into "any insight that might give some guidance with regards to other possible algorithms". I encourage alternate answers to the original question. I personally need to do a bit of reading and resource-digging so that I can answer that aspect of the question.}

One possible answer as to why we can realise the QFT efficiently is down to the structure of its coefficients. To be precise, we can represent it easily as a quadratic form expansion, which is a sum over paths which have phases given by a quadratic function:

$$F_{2^n} = \frac{1}{\sqrt{2^n}} \sum_{k,x \in \{0,1\}^n} \exp\bigl(i Q(k,x)\bigr) \; \lvert k \rangle\!\langle x \rvert,$$ where $Q(z) = \sum_{1 \leqslant j \leqslant k \leqslant 2n} \theta_{j,k} z_j z_k$ is a quadratic form defined on $2n$-bit strings. The quantum Fourier transform in particular involves a quadratic form whose angles are given by $$\theta_{j,k} = \begin{cases} \pi\big/2^{2n-j-k}, & \text{if $1 \leqslant j \leqslant n < k \leqslant 2n-j+1$} \\ 0, & \text{otherwise}. \end{cases}$$ The structure of these angles has an important feature, which allows the QFT to be easily realised as a unitary circuit:

1. There is a function $f: \{1,2,\ldots,n\} \to \{n{+}1,n{+}2,\ldots,2n\}$ such that $\theta_{j,k} = \pi$ for each $1 \leqslant j \leqslant n$ (where $f(j) = 2n-j+1$ in the case of the QFT);
2. For any $1 \leqslant h,j \leqslant n$ for which $\theta_{h,\,f(j)} \ne 0$, we have $\theta_{j,\,f(h)} = 0$.

We may think of the indices of $z = (k,x) \in \{0,1\}^{2n}$ as input and output wires of a quantum circuit, where our task is to show what the circuit in the middle is which shows how the inputs connect to the outputs. The function $f$ above allows us to see the association of output wires to input wires, that in each case there is a Hadamard gate which connects the two ends together, and that apart from the Hadamards (and SWAP gates which accounts for the reversal of in the order of the indices between $(1,2,\ldots,n)$ and $(f(1), f(2), \ldots, f(n))$), all of the other operations are two-qubit controlled-phase gates for relative phases of $\exp(i \theta_{j,k})$. The second condition on $f$ serves to ensure that these controlled-phase gates can be given a well-defined time ordering.

There are more general conditions which one could describe for when a quadratic form expansion gives rise to a realisable circuit, along similar lines. The above describes one of the simplest cases, in which there are no indices in the sum except for those for the standard basis of the input and output states (in which case the coefficients of the associated unitary all have the same magnitude).

This is deviating a little from the original question, but I hope gives a little more insight that could be relevant to other problems.

One might ask "What is it about order finding that lends itself to efficient implementation on a quantum computer?". Order Finding is the main component of factoring algorithms, and includes the Fourier transform as part of it.

The interesting thing is that you can put things like order finding, and Simon's problem, in a general context called the "Hidden Subgroup Problem".

Let us take a group $G$, with elements indexed by $g$, and a group operation '$\oplus$'. We are given an oracle that evaluates the function $f(g)$, and we are assured that there is a subgroup, $K$, of $G$ with elements $k$ such that for all $g\in G$ and $k\in K$, $f(g)=f(g\oplus k)$. It is our task to uncover the generators of the subgroup $K$. For example, in the case of Simon's problem, the group $G$ is all $n$-bit numbers, and the subgroup $K$ is a pair of elements $\{0,s\}$. The group operation is bitwise addition.

Efficient solutions (that scale as a polynomial of $\log|G|$) exist if the group $G$ is Abelian, i.e. if the operation $\oplus$ is commutative, making use of the Fourier Transform over the relevant group. There are well-established links between the group structure (e.g. $\{0,1\}^n,\oplus$) and the problem that can be solved efficiently (e.g. Simon's problem). For example, if we could solve the Hidden Subgroup Problem for the symmetric group, it would help with the solution of the graph isomorphism problem. In this particular case, how to perform the Fourier Transform is known, although this in itself is not sufficient for creating an algorithm, in part because there is some additional post-processing that is required. For example, in the case of Simon's Problem, we required multiple runs to find enough linearly independent vectors to determine $s$. In the case of factoring, we were required to run a continued fractions algorithm on the output. So, there's still some classical post-processing that has to be done efficiently, even once the appropriate Fourier transform can be implemented.

---

Some more details

In principle, the Hidden Subgroup Problem for Abelian groups is solved as follows. We start with two registers, $|0\rangle|0\rangle$, and prepare the first in a uniform superposition of all group elements,

$$\frac{1}{\sqrt{|G|}}\sum_{g\in G}|g\rangle|0\rangle,$$ and perform the function evaluation $$\frac{1}{\sqrt{|G|}}\sum_g|g\rangle|f(g)\rangle=\frac{1}{\sqrt{|G|}}\sum_{g\in K^\perp}\sum_{k\in K}|g\oplus k\rangle|f(g)\rangle,$$ where $K^\perp$ is defined such that by taking each element and combining with the members of $K$ yields the whole group $G$ (i.e. each member of $K^\perp$ creates a different coset, yielding distinct values of $f(g)$), and is known as the orthogonal subgroup. Tracing over the second register, $$\frac{1}{|K|}\sum_{g\in K^\perp}\sum_{k,k'\in K}|g\oplus k\rangle\langle g\oplus k'|.$$ Now we perform the Fourier Transform over the group $G$, giving the output state $$\frac{|K|}{|G|}\sum_{g\in K^\perp}|g\rangle\langle g|.$$ Each of the vectors $|g\in K^\perp\rangle$ has a probability of $|K|/|G|$ of being found, and all others have 0 probability. Once the generators of $K^\perp$ have been determined, we can figure out the generators of $K$ via some linear algebra.

One of many possible constructions that gives some insight into this question, at least to me, is as follows. Using the CSD (cosine-sine decomposition), you can expand any unitary operator into a product of efficient gates V that fit nicely into a binary tree pattern. In the case of the QFT, that binary tree collapses to a single branch of the tree, all the V not in the branch are 1.

Ref: Quantum Fast Fourier Transform Viewed as a Special Case of Recursive Application of Cosine-Sine Decomposition, by myself.