Patrón qubos: construcción algorítmica de transformaciones de 3SAT a QUBO
Autores: Zielinski, Sebastian; Nüßlein, Jonas; Stein, Jonas; Gabor, Thomas; Linnhoff-Popien, Claudia; Feld, Sebastian
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
2023
Patrón qubos: construcción algorítmica de transformaciones de 3SAT a QUBO
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería Eléctrica y Electrónica
Palabras clave
Computadora cuántica
QUBOs
Algoritmo QAOA
Recocedores cuánticos
Calidad de la solución
Transformación a QUBO
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 54
Citaciones: Sin citaciones
Una forma de resolver instancias en un ordenador cuántico es transformar las instancias en instancias de Optimizaciones Binarias No Cuadráticas Restringidas (QUBOs), que pueden utilizarse como entrada para el algoritmo QAOA en sistemas de compuertas cuánticas o como entrada para los recocedores cuánticos. Esta asignación se realiza mediante una transformación de -a-QUBO. Recientemente, se ha demostrado que la elección de la transformación de -a-QUBO puede afectar significativamente la calidad de la solución del recocido cuántico. Se ha demostrado que la calidad de la solución puede variar hasta en un orden de magnitud en la cantidad de soluciones correctas recibidas, dependiendo únicamente de la transformación de -a-QUBO. Una pregunta abierta es: ¿qué causa estas diferencias en la calidad de la solución al resolver instancias con diferentes transformaciones de -a-QUBO? Para poder realizar estudios significativos que evalúen las razones de las diferencias en el rendimiento, se necesitaría un mayor número de transformaciones de -a-QUBO diferentes. Sin embargo, actualmente, solo se conocen algunas transformaciones de -a-QUBO, y todas ellas fueron creadas manualmente por expertos, que utilizaron tiempo y un razonamiento inteligente para crear estas transformaciones. En este artículo, resolveremos este problema proponiendo un método algorítmico que es capaz de crear miles de nuevas y diferentes transformaciones de -a-QUBO, y así permitir a los investigadores estudiar sistemáticamente las razones de la diferencia significativa en el rendimiento de diferentes transformaciones de -a-QUBO. Nuestro método algorítmico es un procedimiento de búsqueda exhaustiva que explota propiedades de dimensional, un concepto que se ha utilizado implícitamente en la creación de transformaciones de -a-QUBO antes, pero que nunca se describió explícitamente. Por lo tanto, también introduciremos formal y explícitamente el concepto de en este artículo.
Descripción
Una forma de resolver instancias en un ordenador cuántico es transformar las instancias en instancias de Optimizaciones Binarias No Cuadráticas Restringidas (QUBOs), que pueden utilizarse como entrada para el algoritmo QAOA en sistemas de compuertas cuánticas o como entrada para los recocedores cuánticos. Esta asignación se realiza mediante una transformación de -a-QUBO. Recientemente, se ha demostrado que la elección de la transformación de -a-QUBO puede afectar significativamente la calidad de la solución del recocido cuántico. Se ha demostrado que la calidad de la solución puede variar hasta en un orden de magnitud en la cantidad de soluciones correctas recibidas, dependiendo únicamente de la transformación de -a-QUBO. Una pregunta abierta es: ¿qué causa estas diferencias en la calidad de la solución al resolver instancias con diferentes transformaciones de -a-QUBO? Para poder realizar estudios significativos que evalúen las razones de las diferencias en el rendimiento, se necesitaría un mayor número de transformaciones de -a-QUBO diferentes. Sin embargo, actualmente, solo se conocen algunas transformaciones de -a-QUBO, y todas ellas fueron creadas manualmente por expertos, que utilizaron tiempo y un razonamiento inteligente para crear estas transformaciones. En este artículo, resolveremos este problema proponiendo un método algorítmico que es capaz de crear miles de nuevas y diferentes transformaciones de -a-QUBO, y así permitir a los investigadores estudiar sistemáticamente las razones de la diferencia significativa en el rendimiento de diferentes transformaciones de -a-QUBO. Nuestro método algorítmico es un procedimiento de búsqueda exhaustiva que explota propiedades de dimensional, un concepto que se ha utilizado implícitamente en la creación de transformaciones de -a-QUBO antes, pero que nunca se describió explícitamente. Por lo tanto, también introduciremos formal y explícitamente el concepto de en este artículo.