Solving 3SAT and MIS Problems with Analog ...
Document type :
Partie d'ouvrage
Title :
Solving 3SAT and MIS Problems with Analog Quantum Machines
Author(s) :
Deleplanque, Samuel [Auteur]
JUNIA [JUNIA]
Acoustique - IEMN [ACOUSTIQUE - IEMN]
Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 [IEMN]
JUNIA [JUNIA]
Acoustique - IEMN [ACOUSTIQUE - IEMN]
Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 [IEMN]
Book title :
Computational Science and Its Applications – ICCSA 2023 Workshops
Publisher :
Springer Nature Switzerland
Publication place :
Cham
Publication date :
2023-06-29
ISBN :
978-3-031-37104-2
English keyword(s) :
Quantum Computing
Quantum Annealing
3SAT
Maximum Independent Set
Combinatorial optimization
Quantum Annealing
3SAT
Maximum Independent Set
Combinatorial optimization
HAL domain(s) :
Physique [physics]
Sciences de l'ingénieur [physics]
Sciences de l'ingénieur [physics]
English abstract : [en]
This work considers the use of analog quantum machinesto solve the boolean satisfiability problem 3SAT by taking QuadraticUnconstrained Binary Optimization models (QUBO) as input. Withthe aim of using real quantum computers ...
Show more >This work considers the use of analog quantum machinesto solve the boolean satisfiability problem 3SAT by taking QuadraticUnconstrained Binary Optimization models (QUBO) as input. Withthe aim of using real quantum computers instead of emulators to solveinstances of the problem, we choose the D-Wave quantum machines,which have a static topology and limited connectivity. Therefore, thechoice of the problem formulation must take these important constraintsinto account. For this reason, we propose to solve 3SAT instances throughpolynomial-time reduction to the Maximum Independent Set problem.This is because the resulting graph is less dense and requires lower con-nectivity than the one that would be produced by directly modeling3SAT into a QUBO.Show less >
Show more >This work considers the use of analog quantum machinesto solve the boolean satisfiability problem 3SAT by taking QuadraticUnconstrained Binary Optimization models (QUBO) as input. Withthe aim of using real quantum computers instead of emulators to solveinstances of the problem, we choose the D-Wave quantum machines,which have a static topology and limited connectivity. Therefore, thechoice of the problem formulation must take these important constraintsinto account. For this reason, we propose to solve 3SAT instances throughpolynomial-time reduction to the Maximum Independent Set problem.This is because the resulting graph is less dense and requires lower con-nectivity than the one that would be produced by directly modeling3SAT into a QUBO.Show less >
Language :
Anglais
Audience :
Internationale
Popular science :
Non
Source :
Files
- document
- Open access
- Access the document
- 3SAT.Proof.LNCS.546341_1_En_29_Chapter_Author.pdf
- Open access
- Access the document
- document
- Open access
- Access the document
- 3SAT.Proof.LNCS.546341_1_En_29_Chapter_Author.pdf
- Open access
- Access the document