Apakah ada satu set gerbang kesatuan terbatas yang dapat secara tepat mewujudkan semua QFT pesanan

Saya sedang mempertimbangkan ide-ide tentang algoritma kuantum yang tepat. Secara khusus, saya sedang mempertimbangkan kemungkinan keterbatasan , yang terdiri dari bahasa yang dapat diputuskan dengan tepat oleh rangkaian sirkuit kuantum seragam-waktu selama rangkaian gerbang berhingga terbatas.$\mathsf{EQP}$

Kuantum transformasi Fourier (QFT), yang diberikan oleh

$$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^{N-2} \\ 1 & \omega^3 & \omega^6 & \omega^9 & \cdots & \omega^{N-3} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{N-1} & \omega^{N-2} & \omega^{N-3} & \cdots & \omega^{(N-1)^2} \end{bmatrix}} \quad\text{for $\omega = \mathrm e^{2\pi i/N}$},$$ adalah bagian terkenal dari teori komputasi kuantum. Dalam kasus$N = 2^n$ , ada dekomposisi$F_N$ menjadi Hadamard, gerbang SWAP, dan gerbang diagonal $$\mathrm{CZ}_{2^T} = \mathrm{diag}(1,1,1,\mathrm e^{2\pi i/2^T\!})$$ $T \geqslant 1$$\mathsf{EQP} \smallsetminus \mathsf{P}$$F_{2^n}$$F_{2^n}$$\mathrm{CZ}_{2^n}$

Jelas, oleh teorema Solovay-Kitaev, kita dapat memperkirakan gerbang atau sewenang-wenang dengan baik dengan set gerbang universal yang ditutup dengan invers. Apa yang ingin saya ketahui adalah apakah ada gerbang terbatas yang dapat benar - benar mewujudkan keluarga operator ini - atau, apa yang saya duga lebih mungkin, apakah ada bukti bahwa tidak ada gerbang terbatas itu ada.$F_{2^n}$$\mathrm{CZ}_{2^n}$

Pertanyaan. Apakah ada dekomposisi dari sebagai keluarga rangkaian seragam-poli-waktu pada himpunan gerbang berhingga, atau bukti bahwa ini tidak mungkin?$\{ F_{2^n} \}_{n \geqslant 1}$

Tidak, tidak ada dekomposisi seluruh keluarga menjadi satu set gerbang hingga yang terbatas. Inilah sebabnya.$\{F_{2^n}\}_{n\geqslant1}$

QFT hanya melibatkan koefisien over , penutupan aljabar kompleks dari bilangan rasional. Dalam analogi dengan [ Adleman + Demarrais + Huang – 1997 ], jika kita melibatkan gerbang yang menyertakan bilangan transendental, kita dapat memilih sekumpulan transendental minimal dan menggambarkan koefisien gerbang. dasarnya sebagai fungsi rasional . Untuk memperoleh QFT sebagai produk dari gerbang semacam itu, kita harus mengatur agar semua komponen transendental dibatalkan (hal serupa harus terjadi untuk memastikan masing-masing gerbang itu kesatuan); tapi kemudian kita mungkin juga mengganti semua transendental dengan$\overline{\mathbb Q}$$\{\tau_1, \tau_2, \ldots\}$$\overline{\mathbb Q}(\tau_1, \tau_2, \ldots)$$0$, sehingga semua koefisien aljabar. Jadi kita membatasi diri pada gerbang-aljabar tanpa kehilangan sifat umum.

Koefisien gerbang berhingga yang ditetapkan di atas semuanya dapat dimasukkan dalam ekstensi derajat hingga dari , yang dapat dibangun dengan memperluas oleh koefisien yang sangat tinggi itu. Namun, gerbang jelas memiliki koefisien milik ekstensi bidang lebih dari derajat , yaitu derajat tidak terikat. Dengan demikian keluarga QFT dari pesanan tidak terurai menjadi gerbang-set terbatas.$\overline{\mathbb Q}$$\mathbb Q$$\mathbb Q$$\mathrm{CZ}_{2^n}$$\mathbb Q$$2^{n-1}$$2^n$

Sebagai akibat wajar, kami tidak dapat berharap untuk memiliki algoritma apa pun di yang bergantung pada QFT pada cincin siklik dengan ukuran tidak terbatas - perhatikan bahwa masalah yang sama terjadi pada setiap rangkaian keluarga yang mungkin menggunakan QFT dengan urutan acak.$\mathsf{EQP}$