logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro