Quantum Computing for solving the 3SAT ...
Document type :
Autre communication scientifique (congrès sans actes - poster - séminaire...): Communication dans un congrès avec actes
Title :
Quantum Computing for solving the 3SAT problem by reduction to the MIS combinatorial optimization problem
Author(s) :
Deleplanque, Samuel [Auteur]
Acoustique - IEMN [ACOUSTIQUE - IEMN]
Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 [IEMN]
Acoustique - IEMN [ACOUSTIQUE - IEMN]
Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 [IEMN]
Conference title :
Emerging optimization methods: from metaheuristics to quantum approaches
City :
Troyes
Country :
France
Start date of the conference :
2023-04-17
English keyword(s) :
Quantum Computing
Optimization
Combinatorial optimization
3SAT
MIS
Optimization
Combinatorial optimization
3SAT
MIS
HAL domain(s) :
Informatique [cs]
Mathématiques [math]
Physique [physics]
Mathématiques [math]
Physique [physics]
English abstract : [en]
This work tries to anticipate the main issues related to the D-Wave machines topology for solving the 3Sat problem. The polynomial reduction to the Maximum Independent Set Problem (MIS) is employed for solving a 3Sat ...
Show more >This work tries to anticipate the main issues related to the D-Wave machines topology for solving the 3Sat problem. The polynomial reduction to the Maximum Independent Set Problem (MIS) is employed for solving a 3Sat instance to furnish a less dense graph to the machine. These analog quantum machines, based on the quantum annealing process, takes a Quadratic Unconstrained Binary Optimization model (QUBO) as input, which is a specific mathematical program easy to build considering the MIS.Show less >
Show more >This work tries to anticipate the main issues related to the D-Wave machines topology for solving the 3Sat problem. The polynomial reduction to the Maximum Independent Set Problem (MIS) is employed for solving a 3Sat instance to furnish a less dense graph to the machine. These analog quantum machines, based on the quantum annealing process, takes a Quadratic Unconstrained Binary Optimization model (QUBO) as input, which is a specific mathematical program easy to build considering the MIS.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Source :
Files
- document
- Open access
- Access the document
- EUME_JE.SamPaper.pdf
- Open access
- Access the document