Transformada quântica de Fourier - Quantum Fourier transform

Na computação quântica , a transformada quântica de Fourier (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 descoberta por Don Coppersmith .

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 amplitudes pode ser implementada como um circuito quântico que consiste apenas em portas de Hadamard e portas de deslocamento de fase controlado , onde é o número de qubits. Isso pode ser comparado com a clássica transformada discreta de Fourier, que leva portas (onde é o número de bits), que é exponencialmente maior que . 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. ${\ displaystyle 2 ^ {n}}$${\ displaystyle O (n ^ {2})}$ ${\ displaystyle n}$${\ displaystyle O (n2 ^ {n})}$${\ displaystyle n}$${\ displaystyle O (n ^ {2})}$

Os melhores algoritmos de transformada de Fourier quântica conhecidos (no final de 2000) requerem apenas portas para alcançar uma aproximação eficiente. ${\ displaystyle O (n \ log n)}$

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 normalmente consideramos vetores de comprimento . ${\ displaystyle N = 2 ^ {n}}$

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

${\ 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 e é um N ^th raiz da unidade . ${\ displaystyle \ omega _ {N} = e ^ {\ frac {2 \ pi i} {N}}}$${\ displaystyle \ omega _ {N} ^ {n}}$

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

${\ 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.)

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

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

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

${\ 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 é dada por ${\ displaystyle F_ {N}}$

${\ 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 . Obtemos, por exemplo, no caso e fase da matriz de transformação ${\ displaystyle \ omega = \ omega _ {N}}$${\ displaystyle N = 4 = 2 ^ {2}}$${\ displaystyle \ omega = i}$

${\ 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 decorre do fato de ser uma transformação unitária . Isso pode ser verificado realizando a multiplicação da matriz e garantindo que a relação se mantenha, onde é o adjunto de Hermitian . Alternativamente, pode-se verificar se os vetores ortogonais da norma 1 são mapeados para vetores ortogonais da norma 1. ${\ displaystyle FF ^ {\ dagger} = F ^ {\ dagger} F = I}$${\ displaystyle F ^ {\ dagger}}$${\ displaystyle F}$

Da propriedade unitária segue-se que o inverso da transformada quântica de Fourier é o adjunto Hermitiano da matriz de Fourier, portanto . Uma vez que existe um circuito quântico eficiente que implementa a transformada quântica de Fourier, o circuito pode ser executado ao contrário 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. ${\ displaystyle F ^ {- 1} = F ^ {\ dagger}}$

Implementação de circuito

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

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

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

Como já foi dito, nós assumimos . Temos a base ortonormal que consiste nos vetores ${\ displaystyle N = 2 ^ {n}}$

${\ 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 a notação do produto tensorial , indica que o qubit está no estado , com 0 ou 1. Por convenção, o índice do estado básico é o número binário codificado pelo , com o bit mais significativo. Com esta convenção, podemos escrever a transformada quântica de Fourier como: ${\ displaystyle \ otimes}$${\ displaystyle | x_ {j} \ rangle}$${\ displaystyle j}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {j}}$${\ displaystyle x}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {1}}$

${\ displaystyle {\ text {QFT}} (| x \ rangle) = {\ frac {1} {\ sqrt {N}}} \ bigotimes _ {j = 1} ^ {n} \ left (| 0 \ rangle + \ omega _ {n} '^ {x2 ^ {nj}} | 1 \ rangle \ right).}$

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}.}$

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).}$

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, as trocas são necessárias. ${\ displaystyle n / 2}$

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 uma porta Hadamard e portas de fase controlada, o próximo requer uma porta Hadamard e uma porta de fase controlada, e cada termo seguinte requer uma porta de fase controlada a menos. Somando o número de portas, excluindo aquelas necessárias para a reversão da saída, dá as portas, que é polinomial quadrático no número de qubits. ${\ displaystyle (n-1)}$${\ displaystyle (n-2)}$${\ displaystyle n + (n-1) + \ cdots + 1 = n (n + 1) / 2 = O (n ^ {2})}$

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 é uma oitava raiz primitiva de unidade que satisfaz (desde ). ${\ displaystyle \ omega _ {3} '= \ omega _ {\ left (2 ^ {3} \ right)}}$${\ displaystyle \ omega _ {3} '^ {8} = \ left (e ^ {\ frac {2 \ pi i} {2 ^ {3}}} \ right) ^ {8} = 1}$${\ displaystyle N = 2 ^ {3} = 8}$

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

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

A transformada quântica de Fourier 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 \ direita).}$

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

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

Relação com a transformada quântica de Hadamard

Usando a transformada de Fourier generalizada em grupos finitos (abelianos) , existem na verdade duas maneiras naturais de definir uma transformada de Fourier quântica em um registrador quântico de n-qubit . O QFT conforme definido acima é equivalente ao DFT, que considera esses n qubits como indexados pelo grupo cíclico . No entanto, também faz sentido considerar os qubits como indexados pelo grupo booleano e, neste caso, a transformada de Fourier é a transformada de Hadamard . Isso é obtido aplicando-se uma porta Hadamard a cada um dos n qubits em paralelo. Observe que o algoritmo de Shor usa os dois tipos de transformadas de Fourier, tanto uma transformação inicial de Hadamard quanto uma QFT. ${\ displaystyle \ mathbb {Z} / 2 ^ {n} \ mathbb {Z}}$ ${\ displaystyle (\ mathbb {Z} / 2 \ mathbb {Z}) ^ {n}}$

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)

links externos

• Wolfram Demonstration Project: Quantum Circuit Implementing Grover's Search Algorithm
• Projeto de demonstração Wolfram: Circuito Quântico Implementando Transformada Quantum de Fourier
• Transformada quirk de Fourier quântica de vida online