¿Cuántos qubits se necesitan para un cálculo útil?

Viendo las noticias sobre 14 estados entrelazados hoy @ Innsbruck:

No he encontrado una guía clara en línea sobre cuántos qubits estamos apuntando para una primera computadora cuántica práctica, por ejemplo, factorización, búsqueda o reimplementación de problemas informáticos a gran escala.

  1. Dados los relativamente pocos algoritmos que tenemos y el hecho de que los algoritmos no necesariamente tienen que mapear 1:1 con el tamaño del dominio (es decir, ser de varios pasos), ¿podemos hacer conjeturas razonables para los casos de uso anteriores?

La entrada de Wikipedia para el algoritmo de Shor parece indicar "Los registros de qubit de entrada y salida necesitan... el doble de qubits de los necesarios...", por lo que necesitaríamos 1024 qubits para el cifrado común que se usa hoy en día, por ejemplo, AES. ¿Es este un entendimiento correcto?

referencias: http://en.wikipedia.org/wiki/Shor%27s_algorithm http://en.wikipedia.org/wiki/Key_size

¿Ya hay más información sobre algoritmos cuánticos adecuados para problemas informáticos a gran escala? por ejemplo, 50-100 qubits para cálculos propios* 'útiles' (1999) http://prl.aps.org/abstract/PRL/v83/i24/p5162_1 - solo tiene acceso al resumen

Salud

Dudo que sea AES, más probablemente RSA ;-) La longitud de bit común para RSA es 1024 con 2048 siendo cada vez más el valor predeterminado.
Peter Shor es un miembro activo del sitio Stack Exchange de Theoretical Computer Science (TCS). Considero que esta pregunta es apropiada tanto para Física como para TCS, pero si no obtiene ninguna respuesta aquí a esta pregunta, consideraría solicitar que se mueva la pregunta a su sitio (después de todo, esta también es una pregunta sobre computación).
No puedo leer tu pregunta sin escuchar a Bill Cosby en mi cabeza. ¿Cómo hiciste eso?
Zalka da una versión del algoritmo de Shor que requiere solo ⌈ 1.5 Iniciar sesión ⁡ norte ⌉ + 2 qubits, por lo que 1000 qubits es un buen umbral para realizar una factorización útil.
Y Seifert dice que se puede hacer en ( 1 + ε ) Iniciar sesión ⁡ norte qubits No sé el tamaño del término de error implícito, pero esto podría reducir el umbral a 700 más o menos.

Respuestas (2)

Para el modelado de sistemas físicos (y químicos) en una computadora cuántica, incluso 25-30 qubits ya serían bastante buenos, consulte Lanyon, et al, "Towards Quantum Chemistry on a Quantum Computer", Nature Chemistry 2, 106 - 111 (2009) ( ver también http://arxiv.org/abs/0905.0887 )

Realmente, la sección quant-ph en arXiv.org es un lugar estándar para artículos sobre computadoras cuánticas, el artículo de PRL que mencionaste también se puede encontrar allí (pero parece que solo puedo publicar un enlace).

El segundo enlace es arxiv.org/abs/quant-ph/9807070
En la estimación también utilicé el hecho de que la simulación de fuerza bruta en las supercomputadoras clásicas hoy en día está limitada a 24 qubits más o menos.
todos los autores esperan correlaciones perfectas. Si trabajas con datos experimentales, no parece tan claro...

En este documento, puede encontrar una manera de reducir drásticamente la cantidad de qubits requeridos:

arxiv.org: algoritmo de Shor con menos qubits (puros)

Christof Zalka (Presentado el 15 de enero de 2006)

Se agradece si puede agregar un sabor de lo que está en el papel.
¿Cuántos qubits se necesitan para un cálculo útil?
RespuestasAquíPolítica de privacidad1y, 0v