Los científicos de NTT dicen que tienen una nueva forma de verificar la ventaja cuántica

Sunnyvale, Calif. – 26 de octubre de 2022 – NTT Research anunció que un científico de su Laboratorio de criptografía y seguridad de la información (CIS) y un colega de la Laboratorios de Informática Social NTT (SIL) han escrito un documento innovador sobre la ventaja cuántica. El documento fue seleccionado para ser presentado en el Simposio anual IEEE sobre Fundamentos de Ciencias de la Computación (FOCS), que se llevará a cabo del 31 de octubre al 3 de noviembre. XNUMX en Denver.

Los coautores del artículo, titulado “Ventaja cuántica verificable sin estructura”, son el Dr. Takashi Yamakawa, distinguido investigador de NTT SIL y el Dr. Mark Zhandry, científico principal en el Investigación NTT Laboratorio CIS. El trabajo se realizó en parte en la Universidad de Princeton, donde el Dr. Yamakawa fue investigador visitante y el Dr. Zhandry también se desempeña como profesor asistente de informática. 

El tema de la ventaja cuántica (o aceleración cuántica) se relaciona con los tipos de problemas que las computadoras cuánticas pueden resolver más rápido que las computadoras clásicas o no cuánticas y cuánto más rápido son. Los problemas en cuestión se describen comúnmente como una clase de tiempo polinomial (NP) no determinista. La cantidad de ventaja podría variar en gran medida. Una computadora cuántica puede ser capaz de resolver un problema particular en un minuto o en un segundo, lo que le toma a una computadora clásica una semana, o posiblemente una cantidad de tiempo exponencial insondable. En este artículo, los autores abordan el desafío de verificar esta superioridad y hacerlo de manera eficiente. Hasta la fecha, las demostraciones de la ventaja cuántica han implicado una “estructura” significativa o comunicación de ida y vuelta entre dos o más partes. El avance del artículo de Yamakawa y Zhandry es demostrar un problema difícil de NP donde la verificación es posible sin estructura.

"Esta es la primera vez que vemos una aceleración cuántica exponencial para un problema de búsqueda de NP, que solo requiere un oráculo aleatorio", dijo el Dr. Scott Aaronson, profesor de informática de la Universidad de Texas en Austin, quien comentó sobre una versión anterior. del documento durante un taller el 13 de junio de 2022 en el Instituto Simons para la Teoría de la Computación. Al requerir únicamente un oráculo aleatorio, es decir, una caja negra teórica que genera respuestas aleatorias a cada consulta, Yamakawa y Zhandry construyeron su problema sobre suposiciones computacionales no estructuradas. Como tal, su problema se alinea más con las funciones unidireccionales que con las estructuradas, como las que se encuentran en la criptografía de clave pública. Esa alineación unidireccional facilita una verificación eficiente.

"Es emocionante ver a criptógrafos afiliados a NTT colaborando en una investigación que una vez más merece la etiqueta de 'avance', especialmente en un artículo que enriquece nuestra comprensión de la computación cuántica, otra área de interés para nosotros en NTT Research", dijo Kazuhiro Gomi. , presidente y director ejecutivo de investigación de NTT. “Felicitaciones y los mejores deseos a todos los participantes en esta prestigiosa conferencia IEEE”. 

El problema de búsqueda de NP que diseñaron Yamakawa y Zhandry era un problema dos en uno que implica encontrar 1) una cadena de n símbolos que es una palabra clave de un código de corrección de errores dado, y 2) una cadena de n símbolos donde cada el símbolo se asigna a cero bajo el oráculo aleatorio. Cada problema por separado es fácil. Pero encontrar una sola cadena de símbolos que sea a la vez una palabra en clave y se asigne a cero es mucho más difícil, al menos clásicamente. “Si eres cuántico, puedes resolver esto en tiempo polinomial”, dijo el Dr. Zhandry, “pero si eres clásico, al menos si estás en este modelo de caja negra, necesitas tiempo exponencial”. Por otro lado, dada una posible solución, es sencillo comprobarla comprobando que resuelve por separado cada uno de los dos problemas. Tenga en cuenta que, como corresponde a un documento para FOCS, este trabajo es básico o fundamental. Como se señaló en la charla del Dr. Aaronson en el Instituto Simons (discutida en este NTT Research artículo del blog), el argumento de Yamakawa-Zhandry cae en una clase de aceleraciones que pueden verificarse fácilmente matemáticamente, pero no demostrarse en la práctica con una computadora cuántica real en el corto plazo. Sin embargo, más allá de su innovador esquema de verificación, el documento también apunta a algo nuevo sobre el alcance de la aceleración cuántica.

“Antes de nuestro trabajo, teníamos ejemplos de ventajas cuánticas para problemas de NP, como la factorización o, en el marco de la caja negra, la búsqueda de períodos. Pero resulta que el algoritmo cuántico que subyace en todos estos ejemplos era básicamente la búsqueda de períodos, aunque mostrar cómo aplicar la búsqueda de períodos a estos ejemplos a menudo no era trivial”, dijo el Dr. Zhandry. “Nuestro artículo muestra que hay al menos un segundo caso. Se podría interpretar con optimismo que dice que hay esperanza de que la ventaja cuántica esté más extendida de lo que pensábamos anteriormente".

Patrocinado por el Comité Técnico de Fundamentos Matemáticos de la Computación (TCMF) de la IEEE Computer Society, FOCS es una conferencia líder en el campo de la informática teórica. La convocatoria de artículos para FOCS 2022, la 63ª reunión anual de este tipo, incluyó la computación cuántica como una de las 17 áreas generales de interés. El artículo de Yamakawa-Zhandry está programado para presentarse el 31 de octubre de 2022 a las 10:15 a. m. MT. Para obtener más información e inscribirse en este evento, visite el FOC 2022 sitio web.