quantum-computing-subset-sum

Using Qiskit to implement a subset sum checker based off Grover's Algorithm.

This project implements a subset-sum checker in Qiskit using Grover's algorithm.

Given:

• a finite list of positive integers,
• a target value,

the goal is to find a subset whose sum equals the target, or determine with high probability that no such subset exists.

The project includes:

• an explanatory notebook, subset-sum-nt.ipynb, which develops the construction step-by-step
• a reusable function grover_Subset_sum(weights, target) inside the notebook for assignment-scale inputs.

What the notebook does

The notebook proceeds in two stages:

1. Toy worked example It first studies the subset-sum instance $(a_0, a_1, a_2) = (1,2,3), \text{ for } T = 3$ and verifies the Grover workflow using a hard-coded oracle.
2. Reusable assignment-scale implementation It then defines a more general function, grover_subset_sum(weights, target), which constructs a subset-sum Grover circuit automatically for small inputs.

Assignment scope

This implemnetation is designed to satisfy the assignment-scale requirement:

• $n \leq 4$
• each input weight $< 8$

That means:

• at most 4 input integers
• each integer is between 0 and 7

Usage

Open subset-sum-nt.ipynb, run the cells, and then call:

toy_result = grover_subset_sum([1,2,3],3)
toy_result