Criptografía para problemas QUBO

Criptograf´ ıa para problemas QUBO Mariano Caruso* Fundaci´ on I+D del Software Libre, FIDESOL [email protected]g Universidad Internacional de La Rioja, UNIR [email protected] Daniel Escanez-Exposito Universidad de La Laguna Tenerife, Spain [email protected] Pino Caballero-Gil Universidad de La Laguna Tenerife, Spain [email protected] Carlos Kuchkovsky QCentroid Bilbao, Spain [email protected] Resumen—Los problemas cuadr´ aticos sin restricciones de optimizaci´ on binaria (QUBO) son ubicuos y pueden ser resueltos v´ ıa computaci´ on cl´ asica o cu´ antica. Su resoluci´ on v´ ıa internet conlleva una posible exposici´ on de la informaci´ on codificada en dicho problema de optimizaci´ on. Este art´ ıculo propone la resoluci´ on de problemas QUBO de forma segura mediante dos m´ etodos criptogr´ aficos agn´ osticos al hardware utilizado. Index Terms—QUBO, optimizaci´ on, computaci´ on cu´ antica, criptograf´ ıa Tipo de contribuci´ on: Investigaci´ on original I. INTRODUCCI´ ON La programaci´ on cuadr´ atica binaria sin restricciones, tambi´ en conocida como optimizaci´ on binaria cuadr´ atica sin restricciones QUBO, es un desaf´ ıo central en la optimizaci´ on combinatoria con una amplia gama de aplicaciones en diversos campos: inform´ atica te´ orica, econom´ ıa, f´ ısica, aprendizaje autom´ atico [1]–[6]. En su formulaci´ on general, estos problemas son computacionalmente dif´ ıciles, perteneciente a la clase NP−hard. Su relevancia se extiende a muchos problemas cl´ asicos de la inform´ atica te´ orica, tales como max-cut, coloraci´ on de grafos y partici´ on de conjuntos [7]–[9]. En el ´ ambito del aprendizaje autom´ atico es posible mapear modelos de regresi´ on, clasificaci´ on y clusterizaci´ on a problemas tipo QUBO [10], [11]. Dada la estrecha relaci´ on entre estos ´ ultimos y los modelos tipo Ising [12], es posible atacar su resoluci´ on en el contexto de la computaci´ on cu´ antica adiab´ atica [13] y mediante un proceso f´ ısico conocido como quantum annealing [14], lo que destaca su importancia en el desarrollo de algoritmos y aplicaciones cu´ anticas. En el mundo de la optimizaci´ on, los problemas cuadr´ aticos sin restricciones de optimizaci´ on binaria (QUBO) se han establecido en una enorme variedad de campos: En el ´ ambito de las finanzas [1], QUBO se aplica a la optimizaci´ on de carteras, la gesti´ on de riesgos y las estrategias de negociaci´ on algor´ ıtmica. Los modelos econ´ omicos [2] aprovechan este esquema para resolver problemas de asignaci´ on de recursos, equilibrio de mercado y minimizaci´ on de costes. En el ´ ambito de las rutas y la log´ ıstica [3], este ayuda a resolver problemas de rutas de veh´ ıculos, optimizaci´ on de la ubicaci´ on de instalaciones y dilemas de gesti´ on de la cadena de suministro. M´ as all´ a de estos ´ ambitos, QUBO trasciende las fronteras disciplinarias, siendo tambi´ en de gran utilidad en ´ areas tan diversas como la biolog´ ıa computacional [4], las telecomunicaciones [5] o la sanidad [6]. Es por ello que la resoluci´ on de cualquiera de estos problemas plantea desaf´ ıos significativos, especialmente cuando se trata de equilibrar la eficiencia computacional con la seguridad de la informaci´ on. Tanto la computaci´ on cl´ asica como la cu´ antica ofrecen m´ etodos para abordar estos problemas, pero su resoluci´ on a trav´ es de plataformas en l´ ınea genera dificultades vinculadas a la privacidad y la exposici´ on de datos sensibles. Es decir, cuando se env´ ıa un problema a un resolutor en la nube de problemas tipo QUBO, los datos del mismo son compartidos con el servidor en cuesti´ on, pudiendo ser consultados y alterados por los proveedores del servicio. En esta encrucijada digital, emerge la necesidad apremiante de salvaguardar la confidencialidad de tales empresas intelectuales. En estas p´ aginas, se propone un tratado sobre la seguridad en la resoluci´ on de QUBO, tejido con los hilos de la criptograf´ ıa, que promete resguardar celosamente la integridad de la informaci´ on. En este art´ ıculo, exploraremos una soluci´ on que combina la potencia de los m´ etodos criptogr´ aficos con la resoluci´ on de problemas QUBO, ofreciendo una forma segura y fiable al usuario de abordar estos desaf´ ıos. Para ello, se propone un sistema de cifrado del problema original de manera que el proveedor de hardware, en adelante QUBO −solver, opere con los datos cifrados y resuelva el problema sin exponer la informaci´ on de los datos originales. Finalmente, ser´ a posible recuperar la soluci´ on de manera local por el usuario. El objetivo es dotar de una capa de seguridad del lado del usuario que pretenda resolver un problema de este tipo. II. DEFINICI ´ ON Y RESOLUCI´ ON DE PROBLEMAS QUBO Comencemos por definir el conjunto de ´ ındices naturales In:= {1,···n}, luego consideremos el espacio de n−tuplas binarias B={0,1}n, una funci´ on f:B−→Rconstruida a partir de una matriz Q∈Rn×n, cuyos elementos son Qij, un vector columna p p p∈Rncuyos elementos son piy un vector columna x x x∈Bde componentes xi, donde (i, j)∈I2 n f(x x x) = X (i,j)∈I2 n Qij xixj+X i∈In pixi(1) Dado que se pretende optimizar la funci´ on f, existe cierta arbitrariedad en la definici´ on de fa menos de una constante real aditiva. En otras palabras, si x x x∗es un valor ´ optimo para f(x x x)tambi´ en lo ser´ a para f(x x x) + c,∀c∈R. El problema de optimizaci´ on QUBO suele consisitir en la minimizaci´ on de f, i.e. encontrar un vector binario x x x∗∈B tal que f(x x x∗)≤f(x x x),∀x x x∈B, arg min x x x∈B f(x x x).(2) Haciendo uso de la identidad x2 i=xi,∀i∈Ines posible reescribir fde forma que su parte cuadr´ atica contenga solo JNIC 2024 ISBN:978-84-09-62140-8 417 productos xixjcon i=jy trasladar el t´ ermino x2 ia la parte lineal de f f(x x x) = X (i,j)∈I2 n i=j Qij xixj+X i∈In (Qii +pi)xi(3) Tomando en cuenta que Pi∈Inpixi=p·x p·x p·xse puede escribir tambi´ en como x x x·diag(p p p)x x x, donde diag(p p p)representa la matriz que tiene en su diagonal principal las componentes de p p py nulos el resto de sus elementos de matriz. Esto permite trasladar los t´ erminos lineales a la parte cuadr´ atica de fpara expresarla finalmente de forma compacta como f(x x x) = x·Q x·Q x·Qx x x(4) donde Q Q Q:= Q+diag(p p p). Notar que la matriz Q Q Qcontiene toda la informaci´ on del problema QUBO a resolver. En cuanto a la resoluci´ on del problema de optimizaci´ on (2) con la funci´ on cuadr´ atica dada por (4), podemos esquematizarla en la siguiente figura 1. Figura 1: A partir de la definici´ on de f(x x x), la matriz Qes enviada v´ ıa internet al dispositivo QUBO−solver que minimiza a f(x x x). Se ha hecho menci´ on a la ubicuidad de los problemas QUBO, en tanto multiplicidad y variedad de casos de uso, pero adem´ as hay un amplio grado de inclusi´ on, en el sentido en que es posible encontrar problemas que no sean cuadr´ aticos, con restricciones y que no sean en variable binaria y que igualmente pueden mapearse a la generosa categor´ ıa de problemas QUBO. III. PRINCIPIO DE TRANSFERENCIA En esta secci´ on se har´ a referencia a una propuesta de resoluci´ on segura de (2), formularemos un principio que permita mapear (transferir) el problema de optimizaci´ on original a otro equivalente en el dominio cifrado, resolverlo de manera segura y obtener la soluci´ on localmente. En general, dada una funci´ on f:X−→ Ry un problema de optimizaci´ on para f(x x x), pretendemos construir otra funci´ on g:Y−→ Rque capture el problema de optimizaci´ on original. Sea Tuna transformaci´ on de Yen X, con la cual mapear el problema de optimizaci´ on (2) de fen otro similar para otra funci´ on g, de forma tal que resolver el problema para gsea seguro y pueda obtenerse la soluci´ on del problema original usando T. Definimos la funci´ on gseg´ un g(y y y) := f( ( (T(y y y)) ) ),(5) es decir, la funci´ on gtoma valores id´ enticos que los transformados por Tde la funci´ on f. Esto garantiza una conexi´ on entre los argumentos de fygque las hacen ´ optimas. En el caso de optimizaci´ on, minimizar o maximizar, similar al de (2), resulta que arg opt x x x∈X f(x x x)T ←−−→ arg opt y y y∈Y g(y y y),(6) donde arg opt abrevia la b´ usqueda del argumento que optimiza (maximiza o minimiza) a la funci´ on en cuesti´ on. De manera que si al minimizar (maximizar) gse obtiene y y y∗entonces se sabr´ a que el m´ ınimo (m´ aximo) para fse obtendr´ a en x x x∗tal que x x x∗=T(y y y∗). En adelante, denotaremos por x x x′al vector binario y por f′(x x x′)a la funci´ on objetivo que resultan de cifrar v´ ıa T al vector binario x x xy a la funci´ on objetivo f(x x x), originales, denotado por x x x=T(x x x′). Se propone que Tsea una transformaci´ on caracterizada por una matriz que hace las veces de clave local generada para transformar (cifrar) el problema original de manera de enviarse de forma segura al QUBO−solver. Tambi´ en consideramos otra propuesta con un t´ ermino aditivo para la transformaci´ on T, que mapea dos vectores x x x,x x x′∈ {0,1}n. En este caso el factor aditivo hace las veces de clave local generada para transformar (cifrar) el problema original de manera de enviarse de forma segura al QUBO−solver. Repetimos el procedimiento de la secci´ on anterior en tanto estudiar la forma que tendr´ a la matriz Q′que debe enviarse al QUBO−solver. IV. CONCLUSIONES El presente trabajo ofrece dos soluciones para abordar los desaf´ ıos de seguridad asociados con la resoluci´ on en l´ ınea de problemas cuadr´ aticos sin restricciones de optimizaci´ on binaria. Al proponer el uso de dos m´ etodos criptogr´ aficos, se establece un marco confiable para la resoluci´ on segura de estos problemas, tanto a trav´ es de computaci´ on cl´ asica como cu´ antica. Esta aproximaci´ on no solo garantiza la protecci´ on de la informaci´ on del problema durante el proceso de resoluci´ on, sino que tambi´ en promueve la adopci´ on de t´ ecnicas avanzadas en un entorno en l´ ınea, fomentando as´ ı el desarrollo continuo en el campo de la computaci´ on cu´ antica y la seguridad de datos. Se ha comentado que existe una estrecha relaci´ on entre los problemas QUBO y los modelos de Ising, y que estos ´ ultimos pueden ser tratados con computaci´ on cu´ antica. No obstante, cabe destacar que la transformaci´ on de protecci´ on de la informaci´ on de los datos se ha aplicado solamente a nivel de variables binarias del problema QUBO. Esto se debe a que: a. se presupone que el canal de comunicaci´ on por el que se env´ ıa la informaci´ on de la matriz Qes cl´ asico y b. dar una capa de seguridad al usuario que garantice que el problema a resolver por QUBO −solver no ser´ a expuesto, independientemente de la naturaleza cl´ asica o cu´ antica de tal proveedor. Sin embargo, podr´ ıa pensarse en un esquema en el que las operaciones de cifrado y descifrado se apliquen a los estados cu´ anticos asociados al problema QUBO v´ ıa Ising. En este caso y para mantener v´ alida la afirmaci´ on b. deben ser considerados, al menos, dos escenarios respecto a la naturaleza de la comunicaci´ on usuario−solver:1. canal cu´ antico el usuario deber´ ıa poder manipular y enviar/recibir la informaci´ on de los estados cu´ anticos al/del proveedor 2. canal cl´ asico y el usuario manipule y env´ ıe/reciba la informaci´ on de M. Caruso, D. Escanez-Exposito, P. Caballero-Gil and C. Kuchkovsky 418 los estados cu´ anticos cifrada. Notar que este ´ ultimo escenario no parece ser pr´ actico, pues se trata de un problema QUBO que se transforma a uno Ising, se le aplican operaciones de cifrado/descifrado y luego se vuelve a transformar para enviarse/recibirse al/del solver v´ ıa el canal cl´ asico. Podr´ ıa imaginarse que la propuesta de m´ etodos para cifrar el problema Ising equivalente y conservar un canal cl´ asico, tendr´ a sentido pr´ actico si se quisiera implementar directamente en un proveedor de hardware cu´ antico. En ese caso, la soluci´ on de seguridad ser´ ıa implementable fuera del entorno local del usuario. En resumen, el argumento de la protecci´ on de la informaci´ on en formato cu´ antico se saldr´ ıa fuera del contexto de este trabajo, pues pretend´ ıa ser agn´ ostico al hardware, sin presuponer siquiera su naturaleza. Es posible que la soluci´ on general provenga de aplicar ambas propuestas de manera conjunta. Se encuentran en proceso la implementaci´ on en c´ odigo y la aplicaci´ on de las t´ ecnicas de criptoan´ alisis adecuadas. AGRADECIMIENTOS La presente investigaci´ on fue realizada con el soporte en el contexto de la Red de Excelencia Contramedidas Inteligentes de Ciberseguirdad para la Red del Futuro (CICERO), CER- 20231019, financiado por el Ministerio de Ciencia, Innovaci´ on y Universidades, a trav´ es de CDTI, el proyecto Q−CAYLE, European Union, Next Generation UE/MICIU/Plan de Recuperacion, Transformacion y esiliencia/Junta de Castilla y Leon y el proyecto PID2022-138933OB-I00: ATQUE financiado por MCIN/AEI/10.13039/501100011033/FEDER, EU. REFERENCIAS [1] Or´ us, R., Mugel, S., Lizaso, E.: “Quantum computing for finance: Overview and prospects”, Reviews in Physics, vol. 4, pp. 100028, 2019. [2] Hong, S. W., et al.: “Market graph clustering via qubo and digital annealing”, Journal of Risk and Financial Management, vol. 14, n. 1, pp. 34, 2021. [3] Neukart, F., et al.: “Traffic flow optimization using a quantum annealer”, Frontiers in ICT, vol. 4, pp. 29, 2017. [4] Li, R. Y., et al.: “Quantum annealing versus classical machine learning applied to a simplified computational biology problem”, NPJ quantum information, vol. 4, n. 1, pp. 14, 2018. [5] Novak, R.: “Quantum Algorithms in Electromagnetic Propagation Modelling for Telecommunications”, IEEE Access, 2023. [6] Streif, M., Neukart, F., Leib, M.: “Solving quantum chemistry problems with a d-wave quantum annealer”, Quantum Technology and Optimization Problems: First International Workshop, Springer International Publishing, vol, 11413, pp. 111-122, 2019. [7] Rehfeldt, D., Koch, T., Shinano, Y.: “Faster exact solution of sparse MaxCut and QUBO problems”, Mathematical Programming Computation, vol. 15, n. 3, pp. 445-470, 2023. [8] Tabi, Z., et al.: “Quantum optimization for the graph coloring problem with space-efficient embedding”, 2020 IEEE international conference on quantum computing and engineering (QCE), pp. 56-62, 2020. [9] Mniszewski, S. M.: “Graph partitioning as quadratic unconstrained binary optimization (QUBO) on spiking neuromorphic hardware”, Proceedings of the International Conference on Neuromorphic Systems, pp. 1-5, 2019. [10] Date, P., Potok, T.:“Adiabatic quantum linear regression”, Scientific reports, vol. 11, n. 1, pp. 21905, 2021. [11] Date, P., Arthur, D., Pusey-Nazzaro, L.: “QUBO formulations for training machine learning models”, Scientific reports, vol. 11, n. 1, pp. 10029, 2021. [12] Brush, S. G.: “History of the Lenz-Ising model”, Reviews of modern physics, vol. 39, n. 4, pp. 883, 1967. [13] Albash, T., Lidar, D. A.: “Adiabatic quantum computation”, Reviews of Modern Physics, vol. 90, n. 1, pp. 015002, 2018. [14] Hauke, P., et al: “Perspectives of quantum annealing: Methods and implementations”, Reports on Progress in Physics, vol. 83, n. 5, pp. 054401, 2020. [15] Horn, R. A., Johnson, C. R. “Matrix Analysis”, Cambridge University Press, ISBN: 0521386322, (1990). [16] Birkhoff, G. “Three observations on linear algebra”, Univ. Nac. Tacuman, Rev. Ser. A, 5, 147-151 (1946). Criptograf´ıa para problemas QUBO 419