A implementação de 2016 do algoritmo de Shor é realmente escalável?

No artigo científico de 2016 " Realização de um algoritmo Shor escalável " [ 1 ], os autores fatoram 15 com apenas 5 qubits, o que é menor que os 8 qubits "necessários", de acordo com a Tabela 1 de [ 2 ] e a Tabela 5 de [ 3 ] O requisito de 8-qbit vem a partir da extremidade de [ 4 ], que indica que o número de qubits necessários para factoring um número de bits é , que para 15 é . $n$ $1.5n+2$ $1.5\cdot 4 + 2=8$

O artigo que usa apenas 5 qubits afirma que seu algoritmo "substitui um QFT atuando em M qubits por um QFT semiclássico agindo repetidamente em um único qubit", mas as consequências disso sobre a complexidade do algoritmo nunca foram mencionadas no artigo.

Agora, houve duras críticas ao artigo que afirma ter o fator 15 de forma "escalonável", como dizem na Seção 2 que o argumento da complexidade do algoritmo de Shor não é mais válido. No entanto, essas críticas não foram corroboradas em nenhum lugar, e o artigo da Science continua sendo comemorado como uma versão "escalável" do algoritmo de Shor. Qual é a complexidade do algoritmo Shor "escalável"?

[ 1 ] Monz et al. (2016) Science . Vol. 351, Edição 6277, pp. 1068-1070
[ 2 ] Smolin et al. (2013) Nature . 499, 163-165
[ 3 ] Dattani e Bryans (2014), arXiv: 1411.6758.
[ 4 ] Zalka (2008), arXiv: quant-ph / 0601097.
[ 5 ] Cao & Luo "Comentário sobre: Realização de um algoritmo Shor escalável"

cc.complexity-theory ds.algorithms quantum-computing factoring security user1271772
fonte

Depende do que você quer dizer com "escalável". Algumas das críticas de Cao e Liu parecem bastante exigentes. Por exemplo, uma de suas críticas é que Kitaev não afirmou que você poderia usar apenas um qubit no artigo citado para esse resultado. Eles não parecem investigar se essa afirmação em si é realmente verdadeira ou falsa. De fato, o algoritmo de Kitaev pode ser modificado para usar apenas um qubit, como afirma o artigo da Science, embora essa afirmação não pareça estar no artigo de Kitaev sobre seu algoritmo.

Peter Shor

@ PeterShor, que honra ouvir de você! Ok, então os autores (corretamente) estenderam os resultados do artigo de Kitaev para tornar possível com um qubit, e Cao & Liu reclamam que o chamam de "algoritmo de Kitaev" em vez de "algoritmo de Kitaev modificado ou algo parecido". No entanto, eles também dizem que o argumento da complexidade não é mais válido quando o QFT é transformado no "QFT semi-clássico". Eu ainda sou um estudante quando se trata desse tipo de análise, por isso gostaria de receber sugestões. A complexidade ainda é O (log n) ^ 3? Ainda é "escalável" em termos de ser polinomial, ou pelo menos <GNFS?

precisa saber é o seguinte

Vou deixar que outra pessoa responda a isso, pois as pessoas podem afirmar que sou tendenciosa. Mas deixe-me salientar que os autores do artigo da Science não estenderam o algoritmo de Kitaev ... é uma extensão bem conhecida. Eles simplesmente não citaram a referência correta.

quer

Essas fórmulas que chegam a 8 qubits usam alguma implementação específica do algoritmo de Shor e calculam quantos qubits essa implementação leva. Eles não afirmam que esta é a melhor implementação possível.

Peter Shor

@ user1271772 Isso foi sinalizado para atenção com moderação com base em você ser um dos autores mencionados em sua própria postagem. Não que isso seja ruim, algum anúncio pessoal é uma parte inevitável da ciência, mas talvez seja melhor esclarecer isso?

Bjørn Kjos-Hanssen

O principal argumento do argumento de Cao e Luo é que, na variante do algoritmo implementado, o primeiro registro - que eventualmente contém a saída - contém apenas 1 bit. E se você obtiver apenas 1 bit de saída do algoritmo, isso será insuficiente para a fatoração. (Por um lado, embora esse não seja o argumento deles, 1 bit claramente não contém informações suficientes para determinar os fatores.)

$c$ $O(\log^3 N)$

Para tentar ser justo com Cao e Luo, eles dizem que não acham que esse algoritmo funciona, e se funciona, não é o algoritmo de Shor porque não corresponde exatamente ao algoritmo descrito no documento de factoring original . Uma citação de seu artigo:

Finalmente, gostaríamos de enfatizar que, se a implementação for realmente credível, seria um novo algoritmo de fatoração quântica, não o algoritmo Shor, porque todos os requisitos do algoritmo original do Shor não são satisfeitos.

E, de fato, não é o algoritmo do meu trabalho de fatoração original. Ele usa o procedimento de estimativa de fase do algoritmo de fatoração de Kitaev, e uma variante disso, descoberta por Griffiths e Niu (não por Parker e Plenio, como eu disse em uma edição anterior desta resposta) que permite que o algoritmo produza a estimativa da fase um pouco de cada vez.

Peter Shor
fonte

Por favor, mostre-me onde, no artigo de Cao e Luo, eles dizem que a saída de um bit por vez afeta o custo da operação. Se estou lendo o jornal deles corretamente, eles não lêem . Eu acho que refutei adequadamente as críticas deles.

Peter Shor

c

$c$

x \cdot t

$x\cdot t$

t

$t$

Não vou percorrer o circuito para estimar a fase de saída de um qubit e explicar por que a mudança relativamente pequena necessária para fazer isso não afeta a complexidade do tempo. É a modificação "semi-clássica", descrito na página 2 de Parker e Plenio de papel , fatoração eficiente com uma única qbit puro e log N qubits mistos .

Peter Shor

\log N + 1

$\log N + 1$

1

$1$

\log N + 1

$\log N + 1$

Como eu disse, você precisa ler e entender o papel. Conte-os você mesmo se não confiar em mim. A estrutura básica do algoritmo não mudou.

precisa

A implementação de 2016 do algoritmo de Shor é realmente escalável?

Respostas: