Case Studies

This section provides examples of solving optimization, mathematical, and graph problems using PyQBPP. The Easy / Medium / Hard label after each problem indicates how hard the page is to understand, judged from the background needed to understand the problem, the ideas in the formulation, and the structure of the program.

Some of the case studies are also presented in videos (see the Videos (Case Studies) page).

Math Problems

1. Math Problem: Find Three Integers (Easy)
2. 3-Digit Math Problem (Easy)
3. Cubic Equation (Easy)
4. Square Root (Easy)
5. Fractions Close to Pi (Easy)
6. Greatest Common Divisor (GCD) (Easy)
7. Remainder Problem (Easy)
8. Pythagorean Triples (Medium)
9. Taxicab Number 1729 (Medium)
10. Prime Factorization by Recursion (Medium)

Puzzle

1. N-Queens Problem (Easy)
2. Star Battle (Easy)
3. Sudoku (Medium)
4. Nonogram (Medium)
5. Slitherlink (Medium)
6. Magic Square (Medium)
7. SEND + MORE = MONEY Problem (Medium)

Graph Problems

Selecting vertices and sets

1. Maximum Independent Set (MIS) Problem (Easy)
2. Maximum Clique Problem (Easy)
3. Minimum Vertex Cover Problem (Easy)
4. Minimum Dominating Set Problem (Medium)
5. Minimum Set Cover Problem (Medium)

Cuts and partitioning

1. Max-Cut Problem (Easy)
2. Minimum Graph Bisection Problem (Easy)
3. Cutwidth Problem (Medium)

Matching

1. Maximum Matching Problem (Easy)
2. Minimum Maximal Matching Problem (Medium)

Coloring

1. Graph Coloring Problem (Easy)
2. 3-Colorable Vertex Deletion Problem (Medium)
3. Graph Edge Coloring Problem (Medium)

Isomorphism

1. Subgraph Isomorphism Problem (Medium)

Routing Problems

1. Shortest Path Problem (Medium)
2. Traveling Salesman Problem (Medium)
3. Capacitated Vehicle Routing Problem (CVRP) (Hard)

Combinatorial Optimization Problems

1. QUBO Problem (Easy)
2. Integer Linear Programming (Easy)
3. LABS Problem (Easy)
4. Knapsack Problem (Medium)
5. Three Formulations of the Partitioning Problem (Medium)
6. Interval Subset Sum Problem (ISSP) (Medium)
7. Cutting Stock Problem (Medium)
8. Facility Location (p-median and p-center) (Medium)
9. Portfolio Optimization (Hard)

Scheduling

1. Shift Scheduling Problem (Medium)
2. Day and Night Shift Roster (Medium)
3. Machine Scheduling with Due Dates (Hard)
4. Job Shop Scheduling (Hard)

Satisfiability

1. Boolean Satisfiability Problem (SAT) (Medium)
2. Not-All-Equal SAT (NAE-SAT) (Medium)

Circuit Simulation

1. Adder Simulation (Medium)
2. Multiplier Simulation and Factorization (Hard)

Image processing

1. Image Halftoning (Medium)
2. Image Denoising (Medium)
3. Optical Flow (Medium)
4. Clustered-Dot Halftoning (Hard)
5. ASCII Art Generation (Hard)

Black-box optimization

1. Black-Box Optimization with FMQA (Hard)
2. Quantum Chemistry with FMQA (Hard)

Quantum annealers

1. Simulating a Quantum Annealer (Medium)

NOTE Graph case studies include visualization code using matplotlib and networkx. Install them with: pip install matplotlib networkx