Transformada Quântica de Fourier

Na computação quântica, a transformada de Fourier quântica (abreviadamente: QFT) é uma transformação linear em bits quânticos e é o análogo quântico da transformada discreta inversa de Fourier . A transformada de Fourier quântica é uma parte de muitos algoritmos quânticos, notavelmente o algoritmo de Shor para fatorar e calcular o logaritmo discreto, o algoritmo de estimativa de fase quântica para estimar os valores próprios de um operador unitário e algoritmos para o problema do subgrupo oculto . A transformada quântica de Fourier foi inventada por Don Coppersmith .^[1]

A transformada quântica de Fourier pode ser realizada de forma eficiente em um computador quântico, com uma decomposição particular em um produto de matrizes unitárias mais simples. Usando uma decomposição simples, a transformada discreta de Fourier em ${\displaystyle 2^{n}}$ amplitudes podem ser implementadas como um circuito quântico consistindo apenas em ${\displaystyle O(n^{2})}$ Portões Hadamard e portões de mudança de fase controlada, onde ${\displaystyle n}$ é o número de qubits.^[2] Isso pode ser comparado com a transformada discreta de Fourier clássica, que leva ${\displaystyle O(n2^{n})}$ portões (onde ${\displaystyle n}$ é o número de bits), que é exponencialmente maior que ${\displaystyle O(n^{2})}$ . No entanto, a transformada de Fourier quântica atua em um estado quântico, enquanto a transformada de Fourier clássica atua em um vetor, portanto, nem toda tarefa que usa a transformada de Fourier clássica pode tirar vantagem dessa aceleração exponencial. 

Os melhores algoritmos de transformada quântica de Fourier conhecidos (no final de 2000) exigem apenas ${\displaystyle O(n\log n)}$ portas para conseguir uma aproximação eficiente.^[3]

Definição

A transformada de Fourier quântica é a transformada de Fourier discreta clássica aplicada ao vetor de amplitudes de um estado quântico, onde geralmente consideramos vetores de comprimento ${\displaystyle N=2^{n}}$ .

A transformada de Fourier clássica atua em um vetor ${\displaystyle (x_{0},x_{1},\ldots ,x_{N-1})\in \mathbb {C} ^{N}}$ e mapeia para o vetor ${\displaystyle (y_{0},y_{1},\ldots ,y_{N-1})\in \mathbb {C} ^{N}}$ de acordo com a fórmula:

${\displaystyle y_{k}={\frac {1}{\sqrt {N}}}\sum _{n=0}^{N-1}x_{n}\omega _{N}^{-kn},\quad k=0,1,2,\ldots ,N-1,}$

Onde ${\displaystyle \omega _{N}=e^{\frac {2\pi i}{N}}}$ e ${\displaystyle \omega _{N}^{n}}$ é um N ^th raiz da unidade .

Da mesma forma, a transformada quântica de Fourier atua em um estado quântico ${\displaystyle |x\rangle =\sum _{i=0}^{N-1}x_{i}|i\rangle }$ e mapeia para um estado quântico ${\displaystyle \sum _{i=0}^{N-1}y_{i}|i\rangle }$ de acordo com a fórmula:

${\displaystyle y_{k}={\frac {1}{\sqrt {N}}}\sum _{n=0}^{N-1}x_{n}\omega _{N}^{nk},\quad k=0,1,2,\ldots ,N-1,}$

(As convenções para o sinal do expoente do fator de fase variam; aqui usamos a convenção de que a transformada de Fourier quântica tem o mesmo efeito que a transformada de Fourier discreta inversa e vice-versa. )

Desde a ${\displaystyle \omega _{N}^{n}}$ é uma rotação, a transformada quântica inversa de Fourier age de forma semelhante, mas com:

${\displaystyle x_{n}={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}y_{k}\omega _{N}^{-nk},\quad n=0,1,2,\ldots ,N-1,}$

Em caso de ${\displaystyle |x\rangle }$ é um estado básico, a transformada quântica de Fourier também pode ser expressa como o mapa

${\displaystyle {\text{QFT}}:|x\rangle \mapsto {\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}\omega _{N}^{xk}|k\rangle .}$

Equivalentemente, a transformada de Fourier quântica pode ser vista como uma matriz unitária (ou uma porta quântica, semelhante a uma porta lógica booleana para computadores clássicos) agindo em vetores de estado quântico, onde a matriz unitária ${\displaystyle F_{N}}$ É dado por

${\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}}}$

Onde ${\displaystyle \omega =\omega _{N}}$ . Obtemos, por exemplo, no caso de ${\displaystyle N=4=2^{2}}$ e fase ${\displaystyle \omega =i}$ a matriz de transformação

${\displaystyle F_{4}={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix}}}$

Propriedades

Unidade

A maioria das propriedades da transformada de Fourier quântica resulta do fato de ser uma transformação unitária . Isso pode ser verificado executando a multiplicação da matriz e garantindo que a relação ${\displaystyle FF^{\dagger }=F^{\dagger }F=I}$ detém onde ${\displaystyle F^{\dagger }}$ é o anexo hermitiano de ${\displaystyle F}$ . Alternativamente, pode-se verificar se os vetores ortogonais da norma 1 são mapeados para vetores ortogonais da norma 1.

Da propriedade unitária segue-se que o inverso da transformada quântica de Fourier é o adjunto Hermitiano da matriz de Fourier, assim ${\displaystyle F^{-1}=F^{\dagger }}$ . Uma vez que existe um circuito quântico eficiente implementando a transformada quântica de Fourier, o circuito pode ser executado no sentido inverso para realizar a transformada quântica inversa de Fourier. Assim, ambas as transformações podem ser executadas com eficiência em um computador quântico.

Implementação de circuito

As portas quânticas usadas no circuito são a porta de Hadamard e a porta de fase controlada ${\displaystyle R_{m}}$, aqui em termos de

${\displaystyle H={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}\qquad {\text{and}}\qquad R_{m}={\begin{pmatrix}1&0\\0&e^{\frac {2\pi i}{2^{m}}}\end{pmatrix}}}$

com ${\displaystyle e^{\frac {2\pi i}{2^{m}}}=\omega _{m}'=\omega _{\left(2^{m}\right)}}$ o primitivo ${\displaystyle 2^{m}}$ -ésima raiz da unidade. O circuito é composto por ${\displaystyle H}$ portões e a versão controlada de ${\displaystyle R_{m}}$

Todas as operações quânticas devem ser lineares, portanto, basta descrever a função em cada um dos estados básicos e deixar que os estados mistos sejam definidos pela linearidade. Isso é diferente de como as transformadas de Fourier são geralmente descritas. Normalmente descrevemos as transformadas de Fourier em termos de como os componentes dos resultados são calculados em uma entrada arbitrária. É assim que você calcularia a integral do caminho ou mostraria que o BQP está em PP . Mas é muito mais simples aqui (e em muitos casos) apenas explicar o que acontece a um estado de base arbitrário específico, e o resultado total pode ser encontrado por linearidade.

A transformada quântica de Fourier pode ser aproximadamente implementada para qualquer N ; entretanto, a implementação para o caso em que N é uma potência de 2 é muito mais simples. Como já foi dito, assumimos ${\displaystyle N=2^{n}}$ . Temos a base ortonormal que consiste nos vetores

${\displaystyle |0\rangle ,\ldots ,|2^{n}-1\rangle .}$

Os estados básicos enumeram todos os estados possíveis dos qubits:

${\displaystyle |x\rangle =|x_{1}x_{2}\ldots x_{n}\rangle =|x_{1}\rangle \otimes |x_{2}\rangle \otimes \cdots \otimes |x_{n}\rangle }$

onde, com notação de produto tensorial ${\displaystyle \otimes }$, ${\displaystyle |x_{j}\rangle }$ indica que qubit ${\displaystyle j}$ está no estado ${\displaystyle x_{j}}$, com ${\displaystyle x_{j}}$ 0 ou 1. Por convenção, o índice de estado básico ${\displaystyle x}$ ordena os possíveis estados dos qubits lexicograficamente, ou seja, convertendo de binário para decimal desta forma:

${\displaystyle x=x_{1}2^{n-1}+x_{2}2^{n-2}+\cdots +x_{n}2^{0}.\quad }$

Também é útil emprestar a notação binária fracionária:

${\displaystyle [0.x_{1}\ldots x_{m}]=\sum _{k=1}^{m}x_{k}2^{-k}.}$

Por exemplo, ${\displaystyle [0.x_{1}]={\frac {x_{1}}{2}}}$ e ${\displaystyle [0.x_{1}x_{2}]={\frac {x_{1}}{2}}+{\frac {x_{2}}{2^{2}}}.}$

Com esta notação, a ação da transformada de Fourier quântica pode ser expressa de forma compacta:

${\displaystyle {\text{QFT}}(|x_{1}x_{2}\ldots x_{n}\rangle )={\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)}$

${\displaystyle {\text{QFT}}(|x_{1}x_{2}\ldots x_{n}\rangle )={\frac {1}{\sqrt {N}}}\ \left(|0\rangle +\omega _{1}'^{[x_{n}]}|1\rangle \right)\otimes \left(|0\rangle +\omega _{2}'^{[x_{n-1}x_{n}]}|1\rangle \right)\otimes \cdots \otimes \left(|0\rangle +\omega _{n}'^{[x_{1}...x_{n-1}x_{n}]}|1\rangle \right).}$

onde usamos:

${\displaystyle [0.x_{1}x_{2}...x_{m}]=[x_{1}x_{2}...x_{n}]/2^{m}}$ e ${\displaystyle \omega _{m}'=\omega _{\left({2^{m}}\right)}=e^{2\pi i/2^{m}}.}$

Isso pode ser visto reescrevendo a fórmula para a transformada de Fourier na expansão binária:

${\displaystyle {\text{QFT}}(|x\rangle )={\frac {1}{\sqrt {N}}}\sum _{k=0}^{2^{n}-1}\omega _{N}^{xk}|k\rangle ={\frac {1}{\sqrt {N}}}\sum _{k_{1}\in \{0,1\}}\sum _{k_{2}\in \{0,1\}}\ldots \sum _{k_{n}\in \{0,1\}}\omega _{N}^{x\sum _{j=1}^{n}k_{j}2^{n-j}}|k_{1}k_{2}\ldots k_{n}\rangle }$

${\displaystyle ={\frac {1}{\sqrt {N}}}\sum _{k_{1}\in \{0,1\}}\sum _{k_{2}\in \{0,1\}}\ldots \sum _{k_{n}\in \{0,1\}}\bigotimes _{j=1}^{n}\omega _{N}^{xk_{j}2^{n-j}}|k_{j}\rangle ={\frac {1}{\sqrt {N}}}\sum _{k_{1}\in \{0,1\}}\sum _{k_{2}\in \{0,1\}}\ldots \sum _{k_{n}\in \{0,1\}}\omega _{N}^{xk_{1}2^{n-1}}|k_{1}\rangle \otimes \bigotimes _{j=2}^{n}\omega _{N}^{xk_{j}2^{n-j}}|k_{j}\rangle }$

${\displaystyle ={\frac {1}{\sqrt {N}}}\left(\sum _{k_{1}\in \{0,1\}}\omega _{N}^{xk_{1}2^{n-1}}|k_{1}\rangle \right)\otimes \sum _{k_{2}\in \{0,1\}}\ldots \sum _{k_{n}\in \{0,1\}}\omega _{N}^{xk_{2}2^{n-2}}|k_{2}\rangle \otimes \bigotimes _{j=3}^{n}\omega _{N}^{xk_{j}2^{n-j}}|k_{j}\rangle }$

${\displaystyle ={\frac {1}{\sqrt {N}}}\left(\sum _{k_{1}\in \{0,1\}}\omega _{N}^{xk_{1}2^{n-1}}|k_{1}\rangle \right)\otimes \left(\sum _{k_{2}\in \{0,1\}}\omega _{N}^{xk_{2}2^{n-2}}|k_{2}\rangle \right)\otimes \sum _{k_{3}\in \{0,1\}}\ldots \sum _{k_{n}\in \{0,1\}}\omega _{N}^{xk_{3}2^{n-3}}|k_{3}\rangle \otimes \bigotimes _{j=4}^{n}\omega _{N}^{xk_{j}2^{n-j}}|k_{j}\rangle =\dots }$

${\displaystyle ={\frac {1}{\sqrt {N}}}\bigotimes _{j=1}^{n}\sum _{k_{j}\in \{0,1\}}\omega _{N}^{xk_{j}2^{n-j}}|k_{j}\rangle ={\frac {1}{\sqrt {N}}}\bigotimes _{j=1}^{n}\left(|0\rangle +\omega _{N}^{x2^{n-j}}|1\rangle \right).}$

Agora:

${\displaystyle \omega _{N}^{x2^{n-j}}=e^{{\frac {2\pi i}{2^{n}}}x2^{n-j}}=e^{{2\pi i}(x2^{-j})}\ \ \ \ \ \ \ \ \ \ (2)}$ .

Deixei ${\displaystyle f(j)=x2^{-j}=2^{-j}\sum _{r=1}^{n}x_{r}2^{n-r}=\sum _{r=1}^{n}x_{r}2^{n-j-r}=\sum _{r=1}^{n-j}x_{r}2^{n-j-r}+\sum _{r=n-j+1}^{n}x_{r}2^{n-j-r}=a(j)+b(j);}$

então ${\displaystyle a(j)\ \epsilon \ \mathbb {N} _{0}}$, Porque ${\displaystyle 2^{n-j-r}\geq 0}$, para ${\displaystyle \ n-j-r\geq 0}$, e ${\displaystyle b(j)=0.x_{n-j+1}x_{n-j+2}\dots x_{n}}$, Então, o ${\displaystyle (2)}$ torna-se:

${\displaystyle e^{{2\pi i}f(j)}=e^{{2\pi i}(a(j)+b(j))}=e^{{2\pi i}a(j)}\cdot e^{{2\pi i}b(j)}=e^{{2\pi i}[0.x_{n-j+1}x_{n-j+2}\cdots x_{n}]},}$

Desde a ${\displaystyle e^{{2\pi i}a(j)}=(e^{2\pi i})^{a(j)}=1}$ para todos ${\displaystyle j}$ .

Então podemos escrever:

${\displaystyle {\text{QFT}}(|x_{1}x_{2}\dots x_{n}\rangle )={\frac {1}{\sqrt {N}}}\bigotimes _{j=1}^{n}\left(|0\rangle +\omega _{N}^{x2^{n-j}}|1\rangle \right)={\frac {1}{\sqrt {N}}}\bigotimes _{j=1}^{n}\left(|0\rangle +e^{2\pi i[0.x_{n-j+1}x_{n-j+2}\ldots x_{n}]}|1\rangle \right)}$

${\displaystyle ={\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 \dots \otimes \left(|0\rangle +e^{2\pi i[0.x_{1}x_{2}\ldots x_{n}]}|1\rangle \right).}$

Para obter esse estado do circuito descrito acima, uma operação de troca dos qubits deve ser realizada para inverter sua ordem. No máximo ${\displaystyle n/2}$ são necessárias trocas, cada uma sendo realizada usando três portas NOT (C-NOT) controladas.^[2]

Após a reversão, o n- ésimo qubit de saída estará em um estado de superposição de ${\displaystyle |0\rangle }$ e ${\displaystyle e^{2\pi i\,[0.x_{1}...x_{n}]}|1\rangle }$, e da mesma forma os outros qubits antes disso (dê uma segunda olhada no esboço do circuito acima).

Em outras palavras, a transformada discreta de Fourier, uma operação em n qubits, pode ser fatorada no produto tensorial de n operações de um único qubit, sugerindo que ela é facilmente representada como um circuito quântico (até uma inversão de ordem da saída). Na verdade, cada uma dessas operações de qubit único pode ser implementada de forma eficiente usando uma porta Hadamard e portas de fase controladas . O primeiro termo requer um portão Hadamard e ${\displaystyle (n-1)}$ portas de fase controlada, a próxima requer uma porta Hadamard e ${\displaystyle (n-2)}$ porta de fase controlada, e cada termo seguinte requer uma porta de fase controlada a menos. Somando o número de portas, excluindo as necessárias para a reversão da saída, dá ${\displaystyle n+(n-1)+\cdots +1=n(n+1)/2=O(n^{2})}$ gates, que é polinomial quadrático no número de qubits.

Exemplo

Considere a transformada de Fourier quântica em 3 qubits. É a seguinte transformação:

${\displaystyle {\text{QFT}}:|x\rangle \mapsto {\frac {1}{\sqrt {2^{3}}}}\sum _{k=0}^{2^{3}-1}\omega _{3}'^{xk}|k\rangle ,}$

Onde ${\displaystyle \omega _{3}'=\omega _{\left(2^{3}\right)}}$ é uma oitava raiz primitiva de unidade que satisfaz ${\displaystyle \omega _{3}'^{8}=\left(e^{\frac {2\pi i}{2^{3}}}\right)^{8}=1}$ (Desde a ${\displaystyle N=2^{3}=8}$ )

Resumindo, configuração ${\displaystyle \omega =\omega _{3}'=\omega _{8}}$, a representação matricial desta transformação em 3 qubits é:

${\displaystyle F_{2^{3}}={\frac {1}{\sqrt {2^{3}}}}{\begin{bmatrix}1&1&1&1&1&1&1&1\\1&\omega &\omega ^{2}&\omega ^{3}&\omega ^{4}&\omega ^{5}&\omega ^{6}&\omega ^{7}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&\omega ^{8}&\omega ^{10}&\omega ^{12}&\omega ^{14}\\1&\omega ^{3}&\omega ^{6}&\omega ^{9}&\omega ^{12}&\omega ^{15}&\omega ^{18}&\omega ^{21}\\1&\omega ^{4}&\omega ^{8}&\omega ^{12}&\omega ^{16}&\omega ^{20}&\omega ^{24}&\omega ^{28}\\1&\omega ^{5}&\omega ^{10}&\omega ^{15}&\omega ^{20}&\omega ^{25}&\omega ^{30}&\omega ^{35}\\1&\omega ^{6}&\omega ^{12}&\omega ^{18}&\omega ^{24}&\omega ^{30}&\omega ^{36}&\omega ^{42}\\1&\omega ^{7}&\omega ^{14}&\omega ^{21}&\omega ^{28}&\omega ^{35}&\omega ^{42}&\omega ^{49}\\\end{bmatrix}}={\frac {1}{\sqrt {2^{3}}}}{\begin{bmatrix}1&1&1&1&1&1&1&1\\1&\omega &\omega ^{2}&\omega ^{3}&\omega ^{4}&\omega ^{5}&\omega ^{6}&\omega ^{7}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&1&\omega ^{2}&\omega ^{4}&\omega ^{6}\\1&\omega ^{3}&\omega ^{6}&\omega &\omega ^{4}&\omega ^{7}&\omega ^{2}&\omega ^{5}\\1&\omega ^{4}&1&\omega ^{4}&1&\omega ^{4}&1&\omega ^{4}\\1&\omega ^{5}&\omega ^{2}&\omega ^{7}&\omega ^{4}&\omega &\omega ^{6}&\omega ^{3}\\1&\omega ^{6}&\omega ^{4}&\omega ^{2}&1&\omega ^{6}&\omega ^{4}&\omega ^{2}\\1&\omega ^{7}&\omega ^{6}&\omega ^{5}&\omega ^{4}&\omega ^{3}&\omega ^{2}&\omega \\\end{bmatrix}}.}$

Isso poderia ser simplificado ainda mais usando ${\displaystyle \omega ^{4}=-1}$, ${\displaystyle \omega ^{2}=i}$ e ${\displaystyle \omega ^{6}=-i}$

e então ainda mais dado que ${\displaystyle \omega ^{5}=-\omega }$, ${\displaystyle \omega ^{3}=i\omega }$ e ${\displaystyle \omega ^{7}=-i\omega }$ .

A transformada de Fourier quântica de 3 qubit pode ser reescrita como:

${\displaystyle {\text{QFT}}(|x_{1},x_{2},x_{3}\rangle )={\frac {1}{\sqrt {2^{3}}}}\ \left(|0\rangle +e^{2\pi i\,[0.x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{2}x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}x_{3}]}|1\rangle \right)}$

${\displaystyle {\text{QFT}}(|x_{1},x_{2},x_{3}\rangle )={\frac {1}{\sqrt {2^{3}}}}\ \left(|0\rangle +\omega _{1}'^{[x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +\omega _{2}'^{[x_{2}x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +\omega _{3}'^{[x_{1}x_{2}x_{3}]}|1\rangle \right).}$

No caso de utilizarmos o circuito obtemos a fatoração em ordem inversa, nomeadamente

${\displaystyle |x_{1},x_{2},x_{3}\rangle \longmapsto {\frac {1}{\sqrt {2^{3}}}}\ \left(|0\rangle +\omega _{3}'^{[x_{1}x_{2}x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +\omega _{2}'^{[x_{2}x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +\omega _{1}'^{[x_{3}]}|1\rangle \right).}$

Aqui usamos notações como:

${\displaystyle [0.x_{1}x_{2}x_{3}]=[x_{1}x_{2}x_{3}]/2^{3}}$ e ${\displaystyle \omega _{m}'=\omega _{\left(2^{m}\right)}=e^{2\pi i/2^{m}}.}$

No esboço a seguir, temos o respectivo circuito para ${\displaystyle n=3}$ (com ordem errada de qubits de saída em relação ao QFT adequado):

Conforme calculado acima, o número de portas usadas é ${\displaystyle n(n+1)/2}$ que é igual a ${\displaystyle 6}$, para ${\displaystyle n=3}$ .

Referências

• KR Parthasarathy, Lectures on Quantum Computation and Quantum Error Correcting Codes (Indian Statistical Institute, Delhi Centre, junho de 2001)
• John Preskill, Lecture Notes for Physics 229: Quantum Information and Computation (CIT, setembro de 1998)

Ligações externas

• Wolfram Demonstration Project: Quantum Circuit Implementing Grover's Search Algorithm
• Projeto de demonstração da Wolfram: Circuito Quântico que implementa a transformada Quantum Fourier
• Transformação quirk de Fourier quântica de vida online