ECE-592 / CSC-591 PROJECT TOPIC: Combinatorial Optimization

Subset Sum Problem

Under professor Greg Byrd

Kushal Batra

What is SUBSET SUM PROBLEM ?

For example, given the set { − 40 , − 2 , 1 , 2 , 3 , 4 , 5 , 6 } , the answer is "yes" because the subset { − 2 , 2 } sums to zero. The Subset Sum Problem belongs to complexity class of NP-complete, meaning it is easier to evaluate whether the final result obtained is correct or not. Also, this checking can be done in polynomial time. The problem itself takes non-deterministic polynomial time to find the solution. The subset sum problem is used in the field of complexity theory and cryptography.

In computational complexity theory, a problem is NP-complete when it can be solved by a restricted class of brute force search algorithms and it can be used to simulate any other problem with a similar algorithm. More precisely, each input to the problem should be associated with a set of solutions of polynomial length, whose validity can be tested quickly (in polynomial time), such that the output for any input is "yes" if the solution set is non-empty and "no" if it is empty (source : wikipedia). The Subset Sum Problem can be thought of as a modification to knapsack problem where the limit of the bag is infinite and the assumption that the weight of the elements can ne negative.

OTHER VARIATIONS OF THE PROBLEM

1. Subset Sum Problem where the sum is equal to some constant. This variation is extenion of the question such that the sum instead of 0 can be any other integer k
   Example - Suppose the parent set is {− 2 , 0 , 1 , 3}. and we are find subset such that sum equals 2. The answer is "yes" the subset {− 2 , 1 , 3} gives the sum=2.


2. Subset Sum Problem where it is posibble to subdivide this set into two strict subsets such that the sum of elements of one set is equal to another set.
   Example - Suppose the parent set is {− 2 , 0 , 1 , 3}. The answer is "yes" the subsets are {− 2 , 3} and {0 , 1 } where the sum of elements is 1
.

PROJECT APPROACH

Classical Approach

Theory of VQE (Quantum Approximate Optimization Algorithm) and QAOA

So the VQE algorithm works as a subrotine to our QAOA algorithm. This VQE is used to solve minimize/maximize the parameterss for our ising Hamiltonian generated.The heart of the QAOA relies on the use of unitary operators dependent on 2 p angles, where p > 1 is an input integer. These operators are iteratively applied on a state that is an equal-weighted quantum superposition of all the possible states in the computational basis. In each iteration, the state is measured in the computational basis and C ( z ) is calculated. After a sufficient number of repetitions, the value of C ( z ) is almost optimal, and the state being measured is close to being optimal as well. (source : wikipedia).

The QAOA algorithm solves the Combinatorial optimization problems are specified by n bits and m clauses. Each clause is a constraint on a subset of the bits which is satisfied for certain assignments of those bits and unsatisfied for the other assignments. The objective function, defined on n bit strings, is the number of satisfied clauses, C(z) = Σ C_α(z) where z = z ₁,z ₂ ...,z_n is the bit string and C_α(z) = 1 if z satisfies clause α and 0 otherwise. Typically C_α depends on only a few of the n bits. Satisfiability asks if there is a stringthat satisfies every clause. In the QAOA algorithm our motive is to find Approximate Optimization(To find a string (z) for which C(z) is close to the maximum).

QAOA (Qiskit) for our problem

Challenges with this cost function

1. The cost function is known but its QUBO formulation is still unknown.
Reason The above Cost function we have written is not in the form QUBO (2 ising model Hamiltonian ). The QUBO format should be in terms of X^TQX which is not the case with us. This is essential because in QAOA or any other optimization algorithm, the first step is to generate the QUBO and then try to minimize or maximize it. But the cost function we have is not in that form.
Solution 1 : Use of Docplex. This is a IBM designed optimization library which takes input in terms of classical function and returns the QUBO form i.e in 2 ising model Hamiltonian form. To obtain the accurate Hamiltonian from Docplex we need to optimize our function and add constraints to our function to obtain te best hamiltonian for our problem. The issue with this is that there are no specific constraints for our problem. So the Hamiltonian we construct is not in the optimized form.
Solution 2 : Use of library PyQubo. This is another alternative to our problem which generates the QUBO (2 ising model Hamiltonian) directly without adding any constraints to our input function.

2. Let us for a while assume that the cost function we established is correct. The problem arises is to determine what the minimum energy level will be for the given sum.
Reason We don't know whether minimizing or maximizing the cost function will yield the lowest energy level or not.
Solution: As now we are able to formulate our problem in terms of Hamiltonian, we now can minimize our energy levels for our correct solution.

So we use the approach of Docplex and Pyqubo to solve our problem. We use PyQubo to generate our Hamiltonian and then we feed it to our docplex for minimiaztion. We could have just skipped the use of Docplex but then it is a better wrapper class for the Qiskit Aqua so we used it.

DWave (Quantum Annealing)

It is not known to be polynomially equivalent to a universal quantum computer and, in particular, cannot execute Shor's algorithm because Shor's algorithm is not a hill climbing process. Shor's algorithm requires a universal quantum computer. D-Wave claims only to do quantum annealing. From the implementation of QAOA we can extract the QUBO and plug it into the DWAVE program.We also have to work out the embedding for our problem

The QUBO Formulation : minimize Y=X^TQX
To convert Y into symmetric form we can replace q_ij by (q_ij+q_ji)/2 where i is not equal to j.
This information that we are extracting is from the QAOA . We will be using this QUBO information and then construct the implicit and explicit embedding for it.

Challenges in DWave

1. As the number of elements increases or decreases in our problem set the problem of fitting the problem in our 4x4 Bipartite graph changes.
   Solution: We can do is implicit embedding reducing the complexity. But this may reduce the accuracy of our results.

Timeline and individual Contribution

Results and discussions

1. Analyzing results from DWAVE
   • Three elements in the set: Occurrences (correct solution) vs the chain strength

     We ran a simple for loop for 'chain strength' from 0 -> 50 (with an increment of 5) to determine the variations in the occurrence of our chain strength. For this particular example, in our set we had elements {2 , 2 , 4} and the sum to find = k = 4. We observe that for this particular the subset solution we have 2 solutions {2 , 2} and {4}. In the solution, both the solutions have negative energy levels. We observe that the graph has a peak at chain strength = 5. We ran our code for different sets and for different sets of the element. We saw that chain strength = 5 gives best result for sets where the number of sets in the set = 3. With an increase in this cardinality of strength, we get an increase in the chain strength value.
     

     

     
     The first graph is for 'chain strength' from 0 -> 50 (with increment of 5). The second graph is chain strength from 0->5 (with increment of 0.5)
   • Processing time vs chain strength

     This graph had an interesting pattern. When the chain strength crosses the point of 25 the processing time decrease. There can be two reasons for this. Firstly, as chain strength increases the solution {2,2} chances/occurrences increases (as coupling strength is high). Secondly, it might be possible that till chain strength 20 the servers were busy and hence the high processing time. We ruled out the second scenario by running our solutions 3 times and still obtained somewhat same graph.

   
   
   

   

   

   
   The first graph is for 'chain strength' from 0 -> 50 (with increment of 5). The second graph is chain strength from 0->10 (with increment of 1).
2. Analyzing results from QISKIT
   • 3 elements in the set: Processing Time vs the circuit depth

   We initially expected the graph between time vs depth to be exponential but our results show that this dependence of time on depth of the circuit is linear. We were not able to assess the reason for this behaviour.
   

   

   
   
   • The Subset-Sum Objective vs depth

   As expected from the graph, more depth we add to the circuit more accurate the results we obtain. Subset Sum objective for the correct solution should be zero. So the graph turns out to be a graph in terms of error deviation from 0 with respect to depth of the circuit.
   

   

   • The Circuit obtained for three elements with depth =5

     

Comparing the results from QISKIT and DWAVE

1. The solution obtained from DWave takes less time to compute results as compared to Qiskit Aqua (with minimim depth). This information can be extracted by comparing the graphs in fig 1 and fig 5
2. When n (#no. of elements in the set increases) increases the solution sample also degrades exponentilly in both Dwave and Qiskit. The degardation trend is more prominenet in case of Dwave when compared with Qiskit.
3. Weakness with Dwave is that as the problem set space increases the number of used qubit also increases and in Dwave the chimera graph is not completely uniform. In case of Qiskit , the number of qubo's are limited with the IBM's quantum achitecture.

Future Work

• Try to implement manual embedding for Dwave solution to increase purity of our solution states. This is because when we are dealing with n>=10 our solution sets start giving impure states.
• Similarly in QAOA if we are able to generate the Hamiltonian using some other method instead of Docplex or PyQubo we will get better and faster solution. This is because Docplex and Pyqubo are libraries which are operated or executed in classical computer.

REFERENCE PAPER