Podemos acelerar o algoritmo de Grover executando processos paralelos?

Na computação clássica, podemos executar a pesquisa de chaves (por exemplo, AES) executando os nós de computação paralela o maior número possível.

É claro que também podemos executar muitos algoritmos de Grover.

Minha pergunta é ; é possível acelerar usando mais de um algoritmo de Grover como na computação clássica?

— kelalaka
fonte

Respostas:

Certamente! Imagine que você tem $K = 2^{k}$ cópias do oráculo de pesquisa $U_{S}$ que você pode usar. Normalmente, você pesquisar por iteração a ação

H^{\otimes n} (I_{n} - 2 | 0 ⟩ ⟨ 0 |^{\otimes n}) H^{\otimes n} U_{S},

a partir de um estado inicial

(H | 0 ⟩)^{\otimes n}

. Isso leva tempo

Θ (\sqrt{N})

. (Estou usando

I_{n}

para denotar amatriz de identidade

2^{n} \times 2^{n}

Pode-se substituir este com $2^{k}$ cópias paralelas, cada um indexado por um $x \in {0, 1}^{k}$ , usando

({Eu}_{k} \otimes H^{\otimes (n - k)}) {Eu}_{k} \otimes ({Eu}_{n - k} - 2 | 0 0 ⟩ ⟨ 0 0 |^{\otimes (n - k)}) ({Eu}_{k} \otimes H^{\otimes (n - k)}) {você}_{S}

e a partir de um estado

| x ⟩ (H | 0 ⟩)^{\otimes (n - k)}

O tempo necessário para executar estes seria reduzida a

O (\sqrt{N / K})

, ao custo de exigir

K

vezes mais espaço.

Em um sentido de escala, pode-se considerar isso um resultado irrelevante. Se você possui um número fixo de oráculos, $K$ , obtém um número fixo ( $\sqrt{K}$ ) melhoria (assim como, se você tiver $K$ núcleos clássicos paralelos, a melhor melhoria possível é um fator de $K$ ), e isso não altera a escala. Mas isso muda o tempo de execução fundamental. Sabemos que o algoritmo de Grover é exatamente ideal. Leva o tempo mínimo absoluto possível com um único oráculo. Então, sabendo que você recebe um $\sqrt{K}$ melhoria no tempo é útil no que diz respeito a esse valor de referência de um tempo específico em execução em um valor específico de $N$ .

— DaftWullie
fonte

mas se você fizer isso, a comparação com a performance clássica perde parte de seu significado, não é? Afinal, você também pode acelerar a pesquisa clássica executando a operação que verifica se um determinado

é o alvo em paralelo em todas as entradas. Isso claramente requer suposições adicionais sobre os recursos disponíveis, mas o mesmo tipo de suposição que é feito em seu argumento

x

— glS 25/10/1918

vai para o infinito, mas

não. Seu problema aumenta, mas seus recursos permanecem poucos.

N

K

— AHusain

Esta resposta está correta (embora possa não ser a ideal, como o DaftWullie adverte). Este é o mesmo atestado à paralelização que se observa na complexidade clássica dos circuitos. Se você deseja uma aceleração devido à paralelização, analisa a profundidade do circuito (porque a coordenação de vários processos não reduzirá o trabalho total). Não importa se

é constante - ou você está interessado na melhoria da profundidade da paralelização ou não. Como na computação quântica, apenas jogar mais computadores em um problema não magicamente torna tudo rápido!

K

— Niel de Beaudrap 26/10/19

De certa forma, se estivéssemos fazendo isso em paralelo em diferentes nós, você economizaria tempo para executar. Mas se falamos de complexidade (é o que geralmente chamamos de aceleração), precisamos de um pouco de análise.

Você concorda que precisamos sobre $\sqrt{N}$ operações para o caso não paralelo. Digamos que temos dois nós e separamos a lista de N elementos em duas listas de tamanho $N_{1}, N_{2}$ . A pesquisa nas sub-listas leva cerca de $\sqrt{N_{1}}, \sqrt{N_{2}}$ .

No entanto, temos que

\sqrt{N} = \sqrt{N_{1 1} + N_{2}} \leq \sqrt{N_{1 1}} + \sqrt{N_{2}}

E você ainda precisaria verificar qual saída entre o que é retornado pelos processos paralelos é a que você procura. Ele adiciona uma constante na complexidade, de modo que geralmente a ocultamos na notação $O$

No entanto, isso ainda seria interessante, especialmente se tivermos que agrupar o hardware, porque somos limitados em número de qubits ou outras limitações.

— cnada
fonte

Para N1 = N2 é ainda uma desigualdade: sqrt (2) * sqrt (N1) <2 * sqrt (N1)

— Mariia Mykhailova

Ah, de fato. Na minha cabeça $ \ sqrt {a b} = \ sqrt {a} \ sqrt {b} $ pensei. Eu deveria parar de responder aqui à meia-noite e quando estiver cansado. Obrigado por apontar isso.

— Cnada

@cnada: Existem pelo menos duas noções diferentes de complexidade, ambas relevantes para acelerar. Um é a complexidade do tamanho e o outro é a complexidade profunda A menos que especificado de outra forma, geralmente preferimos considerar a complexidade do tamanho, mas a profundidade ainda é algo que interessa muito à complexidade computacional quântica, por exemplo, no MBQC [arXiv: quant-ph / 0301052 , arXiv: 0704.1736 ] e resultados recentes em separações incondicionais de profundidade [arXiv: 1704.00690 ].

— Niel de Beaudrap 25/10/19

@NieldeBeaudrap Eu pensei que as pessoas olham mais profundamente na complexidade. Mas para Grover, o tamanho e a complexidade da profundidade são da mesma ordem. Isso é quadrático no tamanho do problema (geralmente visto como o tamanho de uma lista de N elementos). Você acha que minha abordagem aqui não está certa?

— Cnada

Você não está dizendo nada de errado , estou apenas apontando que você está enfatizando indevidamente a complexidade do tamanho e não está realmente trabalhando no benefício da complexidade profunda. Não acontece muita coisa interessante se você apenas fizer

processos paralelos de Grover, mas, como sugere a resposta de DaftWullie (e considerando o pós-processamento clássico), a complexidade da profundidade vai de

k \in O (1)

para

\sqrt{N}

para

processos paralelos de Grover, que é uma melhoria por um fator de

\log (k) \sqrt{N / k}

k (N) \in Ω (1)

(o fator de log vem da identificação de qual processo, se houver, encontrou uma solução).

\sqrt{k} / \log (k)

— Niel de Beaudrap 25/10/19