Skip to content

Use Grover's algorithm to solve Boolean Satisfiability Problem and Traveling Salesman Problem

License

Notifications You must be signed in to change notification settings

thyung/qiskit_grover

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

1 Commit
 
 
 
 
 
 
 
 

Repository files navigation

Overview

Quick revision to Grover's algorithm and solve a Boolean Satisfiability Problem. Then, apply to a Travelling Salesman Problem. As Grover's algorithm is $O(sqrt(N)), both problems are still in exponential time.

Content

  1. Chapter 1 Grover's algorithm revision and illustrate with an example Boolean Satisfiability Problem.

  2. Chapter 2 attempt to solve a 4 nodes Travelling Salesman Problem.

Notes

  1. Qiskit 1.0.2 or up is required.

References:

  1. Install qiskit 1.x, https://www.youtube.com/watch?v=dZWz4Gs_BuI
  2. Grover's algorithm, https://en.wikipedia.org/wiki/Grover%27s_algorithm
  3. Boolean Satisfiability Problem, https://en.wikipedia.org/wiki/Boolean_satisfiability_problem
  4. Travelling Salesman Problem, https://en.wikipedia.org/wiki/Travelling_salesman_problem

About

Use Grover's algorithm to solve Boolean Satisfiability Problem and Traveling Salesman Problem

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published