Algoritmo de estimativa de fase quântica - Quantum phase estimation algorithm

Na computação quântica , o algoritmo de estimativa de fase quântica (também referido como algoritmo de estimativa de autovalor quântico ), é um algoritmo quântico para estimar a fase (ou autovalor) de um autovetor de um operador unitário. Mais precisamente, dada uma matriz unitária e um estado quântico tal que , o algoritmo estima o valor de com alta probabilidade dentro do erro aditivo , usando qubits (sem contar os usados ​​para codificar o estado do vetor próprio) e operações de U controlado . O algoritmo foi inicialmente introduzido por Alexei Kitaev em 1995. ${\ displaystyle U}$ ${\ displaystyle | \ psi \ rangle}$${\ displaystyle U | \ psi \ rangle = e ^ {2 \ pi i \ theta} | \ psi \ rangle}$${\ displaystyle \ theta}$ ${\ displaystyle \ varepsilon}$${\ displaystyle O (\ log (1 / \ varepsilon))}$${\ displaystyle O (1 / \ varepsilon)}$

A estimativa de fase é freqüentemente usada como uma sub-rotina em outros algoritmos quânticos, como o algoritmo de Shor e o algoritmo quântico para sistemas lineares de equações .

O problema

Seja U um operador unitário que opera em m qubits com um autovetor tal que . ${\ displaystyle | \ psi \ rangle,}$${\ displaystyle U | \ psi \ rangle = e ^ {2 \ pi i \ theta} \ left | \ psi \ right \ rangle, 0 \ leq \ theta <1}$

Gostaríamos de encontrar o autovalor de , que neste caso é equivalente a estimar a fase , a um nível finito de precisão. Podemos escrever o autovalor na forma porque U é um operador unitário sobre um espaço vetorial complexo, então seus autovalores devem ser números complexos com valor absoluto 1. ${\ displaystyle e ^ {2 \ pi i \ theta}}$${\ displaystyle | \ psi \ rangle}$${\ displaystyle \ theta}$${\ displaystyle e ^ {2 \ pi i \ theta}}$

O algoritmo

Configurar

A entrada consiste em dois registradores (a saber, duas partes): os qubits superiores compreendem o primeiro registrador e os qubits inferiores são o segundo registrador . ${\ displaystyle n}$${\ displaystyle m}$

Criar superposição

O estado inicial do sistema é:

${\ displaystyle | 0 \ rangle ^ {\ otimes n} | \ psi \ rangle.}$

Depois de aplicar a operação de porta Hadamard de n bits no primeiro registro, o estado se torna: ${\ displaystyle H ^ {\ otimes n}}$

${\ displaystyle {\ frac {1} {2 ^ {\ frac {n} {2}}}} (| 0 \ rangle + | 1 \ rangle) ^ {\ otimes n} | \ psi \ rangle}$.

Aplicar operações unitárias controladas

Seja um operador unitário com autovetor tal que assim ${\ displaystyle U}$${\ displaystyle | \ psi \ rangle}$${\ displaystyle U | \ psi \ rangle = e ^ {2 \ pi i \ theta} | \ psi \ rangle,}$

${\ displaystyle U ^ {2 ^ {j}} | \ psi \ rangle = U ^ {2 ^ {j} -1} U | \ psi \ rangle = U ^ {2 ^ {j} -1} e ^ { 2 \ pi i \ theta} | \ psi \ rangle = \ cdots = e ^ {2 \ pi i2 ^ {j} \ theta} | \ psi \ rangle}$.

${\ displaystyle CU}$é uma porta U controlada que aplica o operador unitário no segundo registro apenas se o seu bit de controle correspondente (do primeiro registro) for . ${\ displaystyle U}$${\ displaystyle | 1 \ rangle}$

Assumindo por uma questão de clareza que as portas controladas são aplicadas sequencialmente, após a aplicação ao qubit do primeiro registro e do segundo registro, o estado torna-se ${\ displaystyle CU ^ {2 ^ {0}}}$${\ displaystyle n ^ {th}}$

${\ displaystyle {\ frac {1} {2 ^ {\ frac {1} {2}}}} \ underbrace {\ left (| 0 \ rangle | \ psi \ rangle + | 1 \ rangle e ^ {2 \ pi i2 ^ {0} \ theta} | \ psi \ rangle \ right)} _ {n ^ {th} \ qubit \ and \ second \ register} \ otimes {\ frac {1} {2 ^ {\ frac {n- 1} {2}}}} \ underbrace {\ left (| 0 \ rangle + | 1 \ rangle \ right) ^ {\ otimes ^ {n-1}}} _ {qubits \ 1 ^ {st} \ to \ n-1 ^ {th}} = {\ frac {1} {2 ^ {\ frac {1} {2}}}} \ left (| 0 \ rangle | \ psi \ rangle + e ^ {2 \ pi i2 ^ {0} \ theta} | 1 \ rangle | \ psi \ rangle \ right) \ otimes {\ frac {1} {2 ^ {\ frac {n-1} {2}}}} \ left (| 0 \ rangle + | 1 \ rangle \ right) ^ {\ otimes ^ {n-1}}}$${\ displaystyle = {\ frac {1} {2 ^ {\ frac {1} {2}}}} \ left (| 0 \ rangle + e ^ {2 \ pi i2 ^ {0} \ theta} | 1 \ rangle \ right) | \ psi \ rangle \ otimes {\ frac {1} {2 ^ {\ frac {n-1} {2}}}} \ left (| 0 \ rangle + | 1 \ rangle \ right) ^ {\ otimes ^ {n-1}} = {\ frac {1} {2 ^ {\ frac {n} {2}}}} \ underbrace {\ left (| 0 \ rangle + e ^ {2 \ pi i2 ^ {0} \ theta} | 1 \ rangle \ right)} _ {n ^ {th} \ qubit} \ otimes \ left (| 0 \ rangle + | 1 \ rangle \ right) ^ {\ otimes ^ {n- 1}} | \ psi \ rangle,}$

onde usamos:

${\ displaystyle | 0 \ rangle | \ psi \ rangle + | 1 \ rangle \ otimes e ^ {2 \ pi i2 ^ {j} \ theta} | \ psi \ rangle = (| 0 \ rangle + e ^ {2 \ pi i2 ^ {j} \ theta} | 1 \ rangle) | \ psi \ rangle, \ \ forall j.}$

Após a aplicação de todas as restantes operações controlada com como pode ser visto na figura, o estado do primeiro registo pode ser descrito como ${\ displaystyle n-1}$${\ displaystyle CU ^ {2 ^ {j}}}$${\ displaystyle 1 \ leq j \ leq n-1,}$

${\ displaystyle {\ frac {1} {2 ^ {\ frac {n} {2}}}} \ underbrace {\ left (| 0 \ rangle + e ^ {2 \ pi i2 ^ {n-1} \ theta } | 1 \ rangle \ right)} _ {1 ^ {st} \ qubit} \ otimes \ cdots \ otimes \ underbrace {\ left (| 0 \ rangle + e ^ {2 \ pi i2 ^ {1} \ theta} | 1 \ rangle \ right)} _ {n-1 ^ {th} \ qubit} \ otimes \ underbrace {\ left (| 0 \ rangle + e ^ {2 \ pi i2 ^ {0} \ theta} | 1 \ rangle \ right)} _ {n ^ {th} \ qubit} = {\ frac {1} {2 ^ {\ frac {n} {2}}}} \ sum _ {k = 0} ^ {2 ^ { n} -1} e ^ {2 \ pi i \ theta k} | k \ rangle,}$

onde denota a representação binária de , ou seja, é a base computacional, e o estado do segundo registro é deixado fisicamente inalterado em . ${\ displaystyle | k \ rangle}$${\ displaystyle k}$${\ displaystyle k ^ {th}}$${\ displaystyle | \ psi \ rangle}$

Aplicar transformada quântica inversa de Fourier

Aplicando a transformada quântica inversa de Fourier em

${\ displaystyle {\ frac {1} {2 ^ {\ frac {n} {2}}}} \ sum _ {k = 0} ^ {2 ^ {n} -1} e ^ {2 \ pi i \ theta k} | k \ rangle}$

rendimentos

${\ displaystyle {\ frac {1} {2 ^ {\ frac {n} {2}}}} \ sum _ {k = 0} ^ {2 ^ {n} -1} e ^ {2 \ pi i \ theta k} {\ frac {1} {2 ^ {\ frac {n} {2}}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} e ^ {\ frac {-2 \ pi ikx} {2 ^ {n}}} | x \ rangle = {\ frac {1} {2 ^ {n}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} \ soma _ {k = 0} ^ {2 ^ {n} -1} e ^ {2 \ pi i \ theta k} e ^ {\ frac {-2 \ pi ikx} {2 ^ {n}}} | x \ rangle = {\ frac {1} {2 ^ {n}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} \ sum _ {k = 0} ^ {2 ^ {n} -1} e ^ {- {\ frac {2 \ pi ik} {2 ^ {n}}} \ left (x-2 ^ {n} \ theta \ right)} | x \ rangle.}$

O estado de ambos os registros juntos é

${\ displaystyle {\ frac {1} {2 ^ {n}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} \ sum _ {k = 0} ^ {2 ^ {n} -1} e ^ {- {\ frac {2 \ pi ik} {2 ^ {n}}} \ left (x-2 ^ {n} \ theta \ right)} | x \ rangle \ otimes | \ psi \ rangle.}$

Representação de aproximação de fase

Podemos aproximar o valor de arredondando para o número inteiro mais próximo. Isso significa que onde é o número inteiro mais próximo de e a diferença é satisfeita . ${\ displaystyle \ theta \ in [0,1]}$${\ displaystyle 2 ^ {n} \ theta}$${\ displaystyle 2 ^ {n} \ theta = a + 2 ^ {n} \ delta,}$${\ displaystyle a}$${\ displaystyle 2 ^ {n} \ theta,}$${\ displaystyle 2 ^ {n} \ delta}$${\ displaystyle 0 \ leqslant | 2 ^ {n} \ delta | \ leqslant {\ tfrac {1} {2}}}$

Agora podemos escrever o estado do primeiro e do segundo registro da seguinte maneira:

${\ displaystyle {\ frac {1} {2 ^ {n}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} \ sum _ {k = 0} ^ {2 ^ {n} -1} e ^ {- {\ frac {2 \ pi ik} {2 ^ {n}}} \ left (xa \ right)} e ^ {2 \ pi i \ delta k} | x \ rangle \ otimes | \ psi \ rangle.}$

Medição

Realizar uma medição na base computacional no primeiro registro produz o resultado com probabilidade ${\ displaystyle | a \ rangle}$

${\ displaystyle \ Pr (a) = \ left | \ left \ langle a \ underbrace {\ left | {\ frac {1} {2 ^ {n}}} \ sum _ {x = 0} ^ {2 ^ { n} -1} \ sum _ {k = 0} ^ {2 ^ {n} -1} e ^ {{\ frac {-2 \ pi ik} {2 ^ {n}}} (xa)} e ^ {2 \ pi i \ delta k} \ right | x} _ {\ text {Estado do primeiro registro}} \ right \ rangle \ right | ^ {2} = {\ frac {1} {2 ^ {2n} }} \ left | \ sum _ {k = 0} ^ {2 ^ {n} -1} e ^ {2 \ pi i \ delta k} \ right | ^ {2} = {\ begin {cases} 1 & \ delta = 0 \\ & \\ {\ frac {1} {2 ^ {2n}}} \ left | {\ frac {1- {e ^ {2 \ pi i2 ^ {n} \ delta}}} {1 - {e ^ {2 \ pi i \ delta}}}} \ right | ^ {2} & \ delta \ neq 0 \ end {cases}}}$

Pois a aproximação é precisa, assim e Neste caso, sempre medimos o valor exato da fase. O estado do sistema após a medição é . ${\ displaystyle \ delta = 0}$${\ displaystyle a = 2 ^ {n} \ theta}$${\ displaystyle \ Pr (a) = 1.}$${\ displaystyle | 2 ^ {n} \ theta \ rangle \ otimes | \ psi \ rangle}$

Pois uma vez que o algoritmo produz o resultado correto com probabilidade . Provamos isso da seguinte maneira: ${\ displaystyle \ delta \ neq 0}$${\ displaystyle | \ delta | \ leqslant {\ tfrac {1} {2 ^ {n + 1}}}}$${\ displaystyle \ Pr (a) \ geqslant {\ frac {4} {\ pi ^ {2}}} \ approx 0,405}$

${\ displaystyle {\ begin {alinhados} \ Pr (a) & = {\ frac {1} {2 ^ {2n}}} \ left | {\ frac {1- {e ^ {2 \ pi i2 ^ {n } \ delta}}} {1- {e ^ {2 \ pi i \ delta}}}} \ right | ^ {2} && {\ text {para}} \ delta \ neq 0 \\ [6pt] & = {\ frac {1} {2 ^ {2n}}} \ left | {\ frac {2 \ sin \ left (\ pi 2 ^ {n} \ delta \ right)} {2 \ sin (\ pi \ delta) }} \ right | ^ {2} && \ left | 1-e ^ {2ix} \ right | ^ {2} = 4 \ left | \ sin (x) \ right | ^ {2} \\ [6pt] & = {\ frac {1} {2 ^ {2n}}} {\ frac {\ left | \ sin \ left (\ pi 2 ^ {n} \ delta \ right) \ right | ^ {2}} {| \ sin (\ pi \ delta) | ^ {2}}} \\ [6pt] & \ geqslant {\ frac {1} {2 ^ {2n}}} {\ frac {\ left | \ sin \ left (\ pi 2 ^ {n} \ delta \ right) \ right | ^ {2}} {| \ pi \ delta | ^ {2}}} && | \ sin (\ pi \ delta) | \ leqslant | \ pi \ delta | {\ text {for}} | \ delta | \ leqslant {\ frac {1} {2 ^ {n + 1}}} \\ [6pt] & \ geqslant {\ frac {1} {2 ^ {2n}} } {\ frac {| 2 \ cdot 2 ^ {n} \ delta | ^ {2}} {| \ pi \ delta | ^ {2}}} && | 2 \ cdot 2 ^ {n} \ delta | \ leqslant | \ sin (\ pi 2 ^ {n} \ delta) | {\ text {para}} | \ delta | \ leqslant {\ frac {1} {2 ^ {n + 1}}} \\ [6pt] & \ geqslant {\ frac {4} {\ pi ^ {2}}} \ end {alinhado}}}$

Esse resultado mostra que mediremos a melhor estimativa de n bits de com alta probabilidade. Aumentando o número de qubits e ignorando esses últimos qubits, podemos aumentar a probabilidade para . ${\ displaystyle \ theta}$${\ displaystyle O (\ log (1 / \ epsilon))}$${\ displaystyle 1- \ epsilon}$

Veja também

• Algoritmo de Shor
• Algoritmo de contagem quântica
• Medição de paridade

Referências