The code within this repository implements a quantum algorithm for solving the subset sum problem, which is stated as follows:
Given a set of integers X = {x1, x2, ..., xn} and a target sum s, determine those subsets whose elements add to s.
Some authors are only concerned with whether or not such a subset exists, rather than its contents, but the code here tells us whether solutions exist and what those solutions are.
After cloning the repository and navigating into the resulting directory, the module can be installed via the following command:
pip install .
Note that a local installation is necessary as the code hasn't been published to the Python Package Index. Following installation, the module can be imported like so:
import qss
An example is provided below:
import qss
q = qss.QuantumSubsetSum([5, 7, 8, 9, 1], 16)
q.execute()
The output should look something like this:
[([7, 8, 1], 0.3525390625), ([7, 9], 0.3232421875)]
Where the first element of each tuple is a solution subset. The second element is the probability of measuring the corresponding subset state during execution of the underlying quantum circuit.
If you're interested in the raw measurements and their frequencies, these can be obtained via the get_measurement_counts function:
{'110000': 1, '000001': 3, '101001': 4, '100100': 2, '011111': 4, '010111': 2, '100011': 9, '000111': 2, '101000': 2, '001110': 3, '010100': 3, '011000': 4, '000110': 4, '100000': 3, '110101': 5, '010001': 6, '000100': 8, '001000': 4, '011110': 4, '100111': 5, '110011': 1, '111100': 10, '110111': 3, '001001': 3, '011001': 7, '111101': 7, '110010': 4, '010110': 6, '001111': 3, '010010': 8, '111000': 5, '111010': 19, '000101': 7, '010011': 5, '111110': 5, '011010': 3, '101010': 331, '001101': 5, '010101': 2, '001100': 3, '111011': 2, '010000': 15, '101111': 4, '100010': 3, '111111': 10, '011011': 3, '110110': 361, '001010': 2, '000010': 4, '101110': 4, '110100': 5, '011101': 5, '111001': 18, '100110': 17, '001011': 6, '101011': 4, '000000': 5, '000011': 4, '100101': 4, '100001': 3, '110001': 4, '011100': 3, '101101': 5, '101100': 18}
Follow these steps to execute the algorithm on the IBM Quantum Platform:
- Sign up for an IBM Quantum Platform account, if you don't already have one.
- Create an API key for your account.
- Run the following code to initialize
QiskitRuntimeServicewith your credentials:
service = QiskitRuntimeService.save_account(channel="ibm_quantum_platform", token="<api-key>")
- Determine the available backends:
service.backends()
- Specify your chosen backend from the displayed options in the
QuantumSubsetSumconstructor and set thesimulateparameter toFalsein the call toexecute:
import qss
q = qss.QuantumSubsetSum([5, 7, 8, 9, 1], 16, "<backend_name>")
q.execute(simulate=False)
Executing the code in the section above within a simulator and extracting the measurement counts provides us with the following probability distribution.
The histogram displays two clear peaks with measurements corresponding to states 110110 and 101010. The leftmost qubit in these states represents the target sum which has been encoded with a negative phase. It is present in all solution states as the negative target sum value cancels out the sums of subsets which add to the target sum. If we ignore the qubit representing the target sum, each of the qubits read from right to left tells us which elements from the input set are included in the solution subset. A 1 indicates that the element is present while a 0 indicates that the element is not present. Reading the states using this procedure gives us [7, 8, 1] and [7, 9], which are the correct solutions.
Updated Results from December, 2025
It's amazing how far quantum computers have come since this project was created. As described in the original results section, one was once limited to 5 qubits in the free tier of the public offering and now I am able to run experiments on ibm_marrakesh which has a total of 156 qubits. That's a little over 31 times the prior capacity.
A higher capacity does not automatically provide correct results, however. It appears that the error rates are too high to produce the expected solution for the example problem. There is a fairly even distribution of measurement counts among the possible sets:
>>> q.get_measurement_counts()
{'101': 487, '011': 513, '111': 357, '000': 675, '001': 681, '010': 483, '100': 535, '110': 365}
An avenue of further exploration would be to learn more about the error rates of this particular backend, examine the transpiled circuit to see if it can be optimized to reduce error, and to consider introducing a form of quantum error correction into my algorithm.
Original Results from August, 2022
The same experiment was attempted using IBM's quantum computing infrastructure, but ultimately failed for input sets with cardinality greater than one. This was not due to a deficiency of the algorithm, but due to the fact that such sets require more than the 5 qubits included on IBMQ machines open to the public. If a quantum computer with at least 7 qubits was available, a non-trivial problem instance could have been executed. Although this is disappointing, the fortunate fact is that quantum computers are being built with more and more qubits as time progresses. With this comes a potential reduction in price, so it's possible that IBM will open up larger machines to the public in the future.
Unit tests can be executed by running:
python -m unittest qss/test_quantum_subset_sum.py
The implementation of this algorithm is based off concepts and techniques learned from the following resources:
-
Daskin, Ammar. "A quantum approach to subset-sum and similar problems." arXiv preprint arXiv:1707.08730 (2017).
-
Draper, Thomas G. "Addition on a quantum computer." arXiv preprint quant-ph/0008033 (2000).
-
Gunter, David, and Toks Adedoyin. "Towards An Implementation of the Subset-sum Problem on the IBM Quantum Experience." arXiv preprint arXiv:1912.03254 (2019).
-
Qiskit.org. 2022. Grover's Algorithm. https://qiskit.org/textbook/ch-algorithms/grover.html [Accessed 28 February 2022].
-
Qiskit.org. 2022. Phase Kickback. https://qiskit.org/textbook/ch-gates/phase-kickback.html [Accessed 28 February 2022].
-
Qiskit.org. 2022. Quantum Fourier Transform. https://qiskit.org/textbook/ch-algorithms/quantum-fourier-transform.html [Accessed 28 February 2022].
-
Qiskit.org. 2022. Quantum Phase Estimation. https://qiskit.org/textbook/ch-algorithms/quantum-phase-estimation.html [Accessed 28 February 2022].
-
Zheng, Qilin, et al. "Quantum algorithm and experimental demonstration for the subset sum problem." Science China Information Sciences 65.8 (2022): 1-14.