Czy istnieje skończony jednolity zestaw bramek, który może dokładnie zrealizować wszystkie QFT rzędu

Rozważam pomysły dotyczące dokładnych algorytmów kwantowych. W szczególności rozważam prawdopodobne ograniczenia , które składa się z języków dokładnie określonych przez rodziny jednorodnych obwodów kwantowych o jednolitym czasie działania w dowolnym zestawie skończonych bramek.$\mathsf{EQP}$

Kwantowa transformata Fouriera (QFT), dana przez jest znaną częścią kwantowej teorii obliczeniowej. W przypadku N = 2 n dobrze znany jest rozkład F N na Hadamardy, bramki SWAP i bramy ukośne C Z 2 T = d i a g ( 1 , 1 , 1 , e 2 π i / 2

$$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}$},$$ $N = 2^n$$F_N$ dla różnych T ⩾ 1 , co wynika z Coppersmith. Jeśli E Q P ∖ P ma zawierać jakiekolwiek problemy, można mieć nadzieję, że jeden z nich skorzysta z QFT F 2 n , w którym to przypadku wymagałby, aby rodzina operacji F 2 n rozpadła się na pewien określony zestaw bram skończonych . Przy zastosowaniu rekurencyjnego rozkładu QFT jest to równoważne z rozkładem wszystkich bramek C Z 2 n na jeden zbiór skończonych bramek. $$\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}$

$F_{2^n}$$\mathrm{CZ}_{2^n}$

$\{ F_{2^n} \}_{n \geqslant 1}$

$\{F_{2^n}\}_{n\geqslant1}$

$\overline{\mathbb Q}$$\{\tau_1, \tau_2, \ldots\}$$\overline{\mathbb Q}(\tau_1, \tau_2, \ldots)$$0$

$\overline{\mathbb Q}$$\mathbb Q$$\mathbb Q$$\mathrm{CZ}_{2^n}$$\mathbb Q$$2^{n-1}$$2^n$

$\mathsf{EQP}$