¿La implementación de 2016 del algoritmo de Shor es realmente escalable?

En el artículo de Ciencia de 2016 " Realización de un algoritmo Shor escalable " [ 1 ], los autores factorizan 15 con solo 5 qubits, que es menos que los 8 qubits "requeridos" según la Tabla 1 de [ 2 ] y la Tabla 5 de [ 3] ] El requisito de 8 qubits proviene del final de [ 4 ] que establece que el número de qubits necesarios para factorizar un número de bits es que para 15 es . $n$ $1.5n+2$ $1.5\cdot 4 + 2=8$

El documento que usa solo 5 qubits afirma que su algoritmo "reemplaza un QFT que actúa sobre M qubits con un QFT semiclásico que actúa repetidamente en un solo qubit", pero las consecuencias de esto en la complejidad del algoritmo nunca se mencionaron en el documento.

Ahora ha habido duras críticas al artículo que afirma factor 15 en una forma "escalable", como dicen en la Sección 2 que el argumento de complejidad para el algoritmo de Shor ya no es válido. Sin embargo, esta crítica no se ha corroborado en ninguna parte, y el artículo de Science se celebra cada vez más como una versión "escalable" del algoritmo de Shor. ¿Cuál es la complejidad del algoritmo Shor "escalable"?

[ 1 ] Monz y col. (2016) Ciencia . Vol. 351, número 6277, pp. 1068-1070
[ 2 ] Smolin y col. (2013) Naturaleza . 499, 163–165
[ 3 ] Dattani y Bryans (2014) arXiv: 1411.6758
[ 4 ] Zalka (2008) arXiv: quant-ph / 0601097
[ 5 ] Cao & Luo "Comentario sobre: Realización de un algoritmo Shor escalable"

cc.complexity-theory ds.algorithms quantum-computing factoring security usuario1271772
fuente

Depende de lo que quieras decir con "escalable". Algunas de las críticas a Cao y Liu parecen bastante quisquillosas. Por ejemplo, una de sus críticas es que Kitaev no afirmó que se pudiera usar solo un qubit en el documento citado para este resultado. No parecen investigar si esta afirmación en sí misma es realmente verdadera o falsa. De hecho, el algoritmo de Kitaev puede modificarse para usar solo un qubit, como afirma el artículo de Science, aunque esta afirmación no parece estar en el documento de Kitaev sobre su algoritmo.

Peter Shor

@ PeterShor, ¡qué honor saber de usted! De acuerdo, los autores (correctamente) extendieron los resultados del artículo de Kitaev para hacerlo posible con un qubit, y Cao y Liu se quejan de que lo llaman "algoritmo de Kitaev" en lugar de "algoritmo de Kitaev modificado o algo así". Sin embargo, también dicen que el argumento de la complejidad ya no se cumple cuando el QFT se convierte en el "QFT semiclásico". Todavía soy un estudiante cuando se trata de este tipo de análisis, por lo que agradecería su aporte. ¿Sigue siendo la complejidad O (log n) ^ 3? ¿Sigue siendo "escalable" en términos de ser polinomial, o al menos <GNFS?

user1271772

Dejaré que alguien más responda esto, ya que la gente podría decir que soy parcial. Pero permítanme señalar que los autores del artículo de Science no extendieron el algoritmo de Kitaev ... es una extensión bien conocida. Simplemente no citaron la referencia correcta.

Peter Shor

Estas fórmulas que llegan a 8 qubits toman una implementación específica del algoritmo de Shor y calculan cuántos qubits toma esa implementación. No afirman que esta sea la mejor implementación posible.

Peter Shor

@ user1271772 Esto se marcó para atención de moderación sobre la base de que usted es uno de los autores mencionados en su propia publicación. No es que eso sea malo, un poco de publicidad propia es una parte inevitable de la ciencia, pero ¿quizás sea mejor ser claro al respecto?

Bjørn Kjos-Hanssen

El objetivo principal del argumento de Cao y Luo es que en la variante del algoritmo que se implementó, el primer registro, que finalmente contiene la salida, contiene solo 1 bit. Y si solo obtiene 1 bit de salida del algoritmo, eso es insuficiente para la factorización. (Por un lado, aunque este no es su argumento, 1 bit claramente no contiene suficiente información para determinar los factores).

Lo que Cao y Luo parecen no darse cuenta es que para la variación de la transformada de Fourier con solo un bit en el primer registro, se emite el mismo valor de que en el algoritmo de factorización estándar; solo sale un bit a la vez. Este cambio no afecta a la $c$ $O(\log^3 N)$

Para tratar de ser justos con Cao y Luo, dicen que no creen que este algoritmo funcione, y si funciona, entonces no es el algoritmo de Shor porque no coincide exactamente con el algoritmo descrito en el documento de factorización original. . Una cita de su artículo:

Finalmente, nos gustaría enfatizar que si la implementación es realmente creíble, entonces sería un nuevo algoritmo de factorización cuántica, no el algoritmo Shor, porque no se cumplen todos los requisitos del algoritmo original de Shor.

Y, de hecho, no es el algoritmo de mi trabajo de factoring original. Utiliza el procedimiento de estimación de fase del algoritmo de factorización de Kitaev, y una variante descubierta por Griffiths y Niu (no por Parker y Plenio, como dije en una edición anterior de esta respuesta) que permite que el algoritmo genere la estimación de la fase. un poco a la vez

Peter Shor
fuente

Muéstrame en qué parte del trabajo de Cao y Luo dicen que la producción de un bit a la vez afecta el costo de operación. Si estoy leyendo su periódico correctamente, no lo hacen. Creo que he refutado adecuadamente sus críticas.

Peter Shor

c

$c$

x \cdot t

$x\cdot t$

t

$t$

No voy a pasar por el circuito para estimar la fase de salida de un qubit y explicar por qué el cambio relativamente pequeño necesario para lograr esto no afecta la complejidad del tiempo. Es la modificación "semi-clásico" descrito en la página 2 de Parker y Plenio de papel , factorización eficiente con un único qubit puro y log N qubits mixtos .

Peter Shor

\log N + 1

$\log N + 1$

1

$1$

\log N + 1

$\log N + 1$

Como dije, tienes que leer y entender el periódico. Cuenta tú mismo si no confías en mí. La estructura básica del algoritmo no ha cambiado.

Peter Shor

¿La implementación de 2016 del algoritmo de Shor es realmente escalable?

Respuestas: