A Quantum Approach to Subset-Sum and Similar Problems
Ammar Daskin
quant-ph cs.CC cs.DS






Department of Computer Engineering, Istanbul Medeniyet University, Kadikoy, Istanbul, Turkey
	adaskin25@gmail.com 



	
		In this paper, we study the subset-sum problem  by using  a quantum heuristic approach similar to the verification circuit of quantum Arthur-Merlin games <cit.>. 
		Under described certain assumptions, we show that the exact solution of the subset sum problem my be obtained in polynomial time and  the exponential speed-up over the classical algorithms may be possible. 
		We give a numerical example and discuss the complexity of the approach and its further application to the  knapsack problem.
	


 
A Quantum Approach to Subset-Sum and Similar Problems
    Ammar Daskin
    Received: date / Accepted: date
=====================================================



§ INTRODUCTION

	Subset-sum <cit.> is a widely-studied NP-complete problem formally expressed as follows:
	Given a set of integer elements V = {v_1, …, v_n} and a target value W, determine if there is a subset, S, of V whose sum is equal to W. 
	In the associated optimization problem, the subset S with the maximum sum less than  W is searched. 
	The exact solution for this problem can be found by first computing the sum of elements for each possible S and then selecting the maximum among those whose sum is less than W. Clearly, this algorithm would take exponential-time in the number of elements. Another means to solve this problem is through dynamic programming which requires O(nW) time.  
	This is also exponential in the required number of bits to represent W: If W=2^m and m ≈ n, then the running time is O(n2^m) =O(n2^n). There are also many forms of polynomial time approximation algorithms applied to the subset problem. For an overall review of subset-sum problems and the different algorithms, we recommend the book by Keller et al. <cit.>.
	
	
	Quantum algorithms in general provides computational speed-up over the classical counter parts. 
	Quantum walk algorithm presented for element distinctness <cit.> is applied to the subset problems <cit.>. The computational complexity of this algorithm is shown to be bounded by O(n^|L|), where n is the number of items and |L| is the subset size. 
	In quantum computing, the cases where exponential speedups are possible are generally related to hidden subgroup problems: a few examples of these cases are the factoring <cit.>, the dihedral hidden subgroup problem <cit.> and some lattice problems <cit.>. A review of the algorithms giving the exponential speedups in the solutions of algebraic problems are given in Ref.<cit.>. There are also quantum optimization algorithms such as the ones in the adiabatic quantum computation <cit.> applied to different NP problems <cit.> and the quantum approximate optimization algorithm <cit.>  applied to the NP-hard problems. For a further review on general quantum algorithms, please refer to Ref. <cit.>, or to the introductory books <cit.>.  
	
	It is known that having the ability of a post-selected quantum computing (an imaginary computing model), one can obtain the result of a Grover search problem in O(1)  <cit.>. 
	This ability would also lead a quantum computer to solve NP-complete problems in polynomial time.  
	Although this model is imaginary, it still provides an insight to see one of the differences between quantum and classical computers on the solution of NP-complete problems: 
	i.e., mainly a quantum computer can generate all the solution space and mark the correct answer in polynomial time, which is not possible on classical computers. 
	However, this information, the marked item, can only be obtained by an observer with  an exponential overhead (which makes the computational complexity exponential in the number of qubits.).
	This motivates to do research on the applications of the algorithms  such as Grover's search algorithm <cit.> to the special cases of NP-complete problems so as to  gain at least some speed-up over the classical algorithms.

	The Grover search algorithm  in quantum computing provides quadratic computational-speedup over the classical brute force search algorithm. 
	It is well-known that the employment of this algorithm in general yields a quadratic speed-up also in the  exact solutions of NP-complete problems (please see the explanation for Hamiltonian cycle given in page 263 of Ref.<cit.>). 
The algorithm also plays important role in quantum Arthur-Merlin games <cit.> and applied along with the phase estimation algorithm to NP-complete problems such as 3-SAT and k-local Hamiltonian problems<cit.>.
The similar idea is also used to prepare the ground state of the many-body quantum systems <cit.>. 
Here, we study the subset-sum problems by using a quantum heuristic approach similar to the verification circuits of quantum Arthur-Merlin games<cit.>. 
The approach may provide exponential speed-up for the solution of the subset problems over the classical algorithms under the following assumptions:
	
		
	Let	|L| be the number of possible subset-sums less than W and  |L'| be the number of possible subset-sums greater than or equal to W. In this paper, we will assume that |L'|/|L| = poly(n). 
	
	Under this assumption, the probability of having a subset-sum less than W is 1/poly(n). However, we may still have O(2^n/poly(n)) number of possible subsets which gives a sum less than W. 
	Whence we can easily make the following remark:
	
		The subset-sum problem under this assumption is as difficult as without this assumption. Therefore, the maximization version of the problem is still NP-hard when W = O(2^n). 
	
In addition, the correctness of the solution produced by our heuristic is determined from the distribution (which can be guessed from the distribution of the input elements) of the feasible subset-sums. 
	It yields the exact answer with a high-probability if the following condition is satisfied.
		 
			
		Let ϕ_max be the maximum subset-sum less than W. 
		Let m-qubits in the output register of our algorithm represents the binary value of ϕ_max.  
			If the bit value of any tth qubit is 1 in the binary value of ϕ_max = (b_0… b_m-1)_2; then after measuring the first (t-1) number of qubits with the correct values (b_0b_1… b_t-2)_2, the probability of seeing |1⟩ on the tth qubit is not exponentially small (i.e. the probability is 1/poly(n).) in the normalized-collapsed state.
		
This assumption (condition)  only affects the accuracy of the output. As we shall show in the following sections, it does not change the polynomial running time. 
In addition, to the best of our knowledge, this assumption  does not simplify the original problem for the current classical algorithms:
 For instance, this condition is likely to hold when we have a random uniformly distributed set of input elements. 
As mentioned, generating possible subset-sums alone takes exponential time for any classical algorithm and the computational complexity of finding the solution is still bounded by O(2^n) for any classical algorithm when W=O(2^n).

	
	In the following sections, after preliminaries, we list the algorithmic steps and explain each step in the subsections. Then, we discuss the complexity analysis and show how the approach takes O(poly(n)) time under the above assumptions. We also discuss the application to the knapsack problem. Finally, we present a numerical example and conclude the paper.
	




§ PRELIMINARIES

	In this section, brief descriptions of the quantum algorithms used in this paper are given. For a broader understanding of these algorithms, the reader should refer to the introductory book by Chuang and Nielsen <cit.>.
	

 §.§ Notes on Notations

	Throughout the paper, we will use |...⟩ to represent a quantum state (a vector) and ⟨...| to conjugate transpose of a vector. 
	Bold faces such as |0⟩ indicates the vector is at least a two-dimensional vector. Using a value inside the ket-notation such as |ϕ⟩ indicates the basis vector associated with the binary representation of ϕ. 
	Other than W which is a given value, the capital letters generally represent matrices (operators). The quantum state |1⟩ on a qubit represents 1 as a bit value and |0⟩ is 0. The indices start from 0.
	
	

 §.§ Quantum Phase Estimation Algorithm

	Quantum phase estimation algorithm (PEA)<cit.> is a well-known eigenvalue solver which estimates the phases of the eigenvalues of a unitary matrix, U∈ C^⊗ n: i.e. the eigenvalues of U comes in the form of e^iϕ 2π with an associated eigenvector |ψ⟩. The  algorithm estimates the value of ϕ for a given approximate eigenvector |ψ⟩. 
	The accuracy of the estimation is determined by the overlap of the approximate and actual eigenvectors and the number of qubits used to represent the phase value. 
	PEA in general requires two registers to hold the value of the phase and the eigenvector. 
	The algorithm starts with an initial approximation of the eigenvector on the second register and |0⟩ state on the first register: |0⟩|ψ⟩.
	Then, the quantum Fourier transform is applied to the first register. It then the controlled-operators U^2^js are applied to the second register in consecutive order: here, 0≤ j< m, each U^2^j is controlled by the jth qubit of the first register and  m is the size of this register which determines the decimal precision of the estimation. 
	At this point in the first register the Fourier transform of the phase is obtained. Therefore,  applying the inverse Fourier transform and measurement on the first register yields the estimation of ϕ. 

	In general,	the computational complexity of PEA is governed by the number of gates used to implement each U^2^j. When they can be implemented in polynomial time, then the complexity of the algorithm can be bounded by some polynomial time, O(poly(n)).
	

 §.§ Amplitude Amplification Algorithm

	The amplitude amplification (AA) is based on the Grover search algorithm <cit.> and used to amplify the part of a quantum state  which is considered as “good". The algorithm is mainly composed of two operators. The first operator, F, marks (negates the signs of) the “good" states and the second operator, S, amplifies the amplitudes of the marked states.
	
	For |ψ⟩ = α|ψ_good⟩ + β|ψ_bad⟩; 
	F|ψ⟩ = α|ψ_good⟩ - β|ψ_bad⟩. The implementation of F depends on the function that describes the good part of the states. Through this paper, F is simply some combination of controlled Z and X gates (X and Z are Pauli spin matrices.).
	
	If |ψ⟩ = A |0⟩ for some  unitary matrix A ∈ C^N, then S = 2|ψ⟩⟨ψ| - I = A U_0^⊥A^*, where “*" represents the conjugate transpose. 
	The amplification is done by applying the iterator G = SF consecutively to |ψ⟩. The number of iteration depends on β and is bounded by O(1/β). For further details and  variants of AA, please refer to Chapter 8 of Ref.<cit.>.



§ ALGORITHM

	The approach uses a qubit and a rotation phase gate for each element of V,   to encode the possible subset sums as the eigen-phases of a diagonal unitary matrix U. 
	Then, it applies the phase estimation algorithm  to obtain the possible sums and associate eigenvectors on two quantum registers. 
	Marking the states with phases less than W, it eliminates the states with phases greater W through the amplitude amplification.
	Finally, it again employs the amplitude amplification in measurement processes to obtain the maximum phase and its associated eigenvector which indicates the solution of the problem.
Here, first the algorithmic steps in general are listed, and then the explanations and more details for each steps are given in the following subsections.
The steps are generalized as follows:
	
		
  * Encode the integer values as the phases of the rotation gates aligned on different qubits.  
		
  * Apply the phase estimation algorithm to the equal superposition state so as to produce the phases and the associated eigenvectors on quantum registers.
		
  * Apply the amplitude amplification to eliminate the states where ϕ_j ≥ W.   Now, the superposition of the sums and the eigenvectors are obtained with equal probabilities.
		
  * Find the maximum ϕ_j in the first register. Then, measure the second register to attain the solution. 
	
	The quantum circuit representing the above steps is drawn in Fig.<ref>. 
	

 §.§ Encoding the Values into the Phases

	First, the values are scaled so that ∑_j =0^n-1  v_j ≤ 0.5. 
	For each value v_j with 0≤ j<n, a rotation gate in the following form is put on the (j+1)st qubit:
	
    R_j = ( 
    		1   0
    
    		0   e^iv_j2π).

  The n-qubit circuit formed with these rotation gates can be then represented by the following unitary matrix:
	
    U  = R_n-1⊗…⊗ R_0.
 
	Here, U is a diagonal matrix with the diagonal elements (eigenvalues):
	
    [ 1, e^iv_0, e^iv_1, e^iv_0+v_1, …, e^i(v_0+ … + v_n-1)] = [ e^iϕ_0, e^iϕ_1,  …, e^i ϕ_n-1].
 
	As seen in the above, the phases of the eigenvalues associated with the eigenvectors forming the standard-basis-set encode all the possible sum and the subset information: i.e. the j vector in the standard basis indicates the phase ϕ_j and the elements of the jth subset.
	

 §.§ Generating All Possible Sums and Subsets on Registers

Consider the phase estimation algorithm applied to U with the following initial state:
	
    |ψ_0⟩ = |0⟩1/√(2^n)∑_j=0^2^n-1|j⟩.

Here, |ψ_0⟩ can be simply generated by 
( I^⊗ m⊗ H^⊗ n) |0⟩|0⟩, where I represents an identity matrix and H is the Hadamard matrix. 
Since the eigenvectors of U are of the standard basis, the final output of the phase estimation holds the equal superposition of the eigenvector and phases:
	
    |ψ_1⟩ = U_pea|ψ_0⟩ = 1/√(2^n)∑_j=0^2^n-1|ϕ_j⟩|j⟩,
 
where U_pea represents the phase estimation algorithm applied to U and  forms the first part of the circuit in Fig.<ref>.
Obviously if we are able to efficiently find the index of the maximum ϕ_j less than  W in the above, then we solve the maximum subset-sum problem efficiently.



 §.§ Eliminating the Subsets with ϕ_j≥ W

Before searching for the solution, we divide the quantum state in Eq.(<ref>) into two parts: 

    |ψ_1⟩ = 
     1/√(2^n)∑_j∈ L|ϕ_j⟩|j⟩ + 1/√(2^n)∑_j∈ L'|ϕ_j⟩|j⟩ .
    = √(|L|/2^n)|ψ_good⟩ + √(|L'|/2^n)|ψ_bad⟩
 
where L ={j:ϕ_j<W} and 
L' = {j:ϕ_j≥ W} with 0≤ j<2^n.
This equation includes all the possible eigenpairs. To eliminate the ones included in L', we apply the amplitude amplification algorithm defined by the iterator G =S(F_ϕ⊗ I^⊗ n) as shown in Fig.<ref>. Here, F_ϕ operates on the first register and flips the sign of the states with ϕ_j  < W: 

    (F_ϕ⊗ I^⊗ n)|ψ_1⟩ = -√(|L|/2^n)|ψ_good⟩ + 
    √(|L'|/2^n)|ψ_bad⟩.

S = 2|ψ_1⟩⟨ψ_1|-I and can be implemented as follows:
	
    S = (I^⊗ m⊗ H ^⊗ n)U_pea U_0^⊥(I^⊗ m⊗ H ^⊗ n)U_pea^*,

where  U_0^⊥ = I - 2|0⟩⟨0|.

After each iteration, the amplitudes of the “good" states are amplified.
The number of iterations in the algorithm (the number of applications of G) is determined by the initial probability and  is bounded by O( √(2^n/|L|)). In the worst case where |L|<<|L'|, the complexity becomes O(√(2^n)). 
However, in the other cases, the number of iterations is bounded by O(poly(n)). In addition, using the quantum counting one can estimate the value of √(|L|/2^n) and |L| in polynomial time (see quantum counting in Chapter 8 of Ref.<cit.>). 

As explained in the Introduction, in this paper we make the assumption given in Assumption <ref>: i.e., mainly |L'|/|L| = O(poly(n)). 
	As a result of this assumption, this part of the algorithm takes O(poly(n)) time. And at the end of the amplitude amplification, the final quantum state  becomes:
	
    |ψ_2⟩≈1/√(|L|)∑_j ∈ L|ϕ_j⟩|j⟩.




 §.§ Finding the Maximum Sum with Its Subset

	Grover search algorithm <cit.> is able to find a maximum or minimum element of a list of |L| items in O(√(|L|)) times <cit.>. 
	It can be directly applied to Eq.(<ref>) to find the maximum of ϕ_js and the value of j. However, this makes the running time of the whole algorithm exponential because of Assumption <ref>. 
	
	The elements of the set {ϕ_j:0 ≤ j<2^n} is partially sorted and mostly ϕ_j ≤ϕ_j+x for a considerably large x. Therefore, in some cases, quantum binary search algorithm (e.g. <cit.>) can be used to produce an approximate solution. This will require O(lg|L|) = O(poly(n)) time complexity.
	
	Below, similarly to the binary search algorithm and the verification circuit given <cit.>, a polynomial time method for finding the maximum is presented by applying a sequence of conditional amplitude amplifications:	
	Let us assume the maximum ϕ_j in Eq.(<ref>) is ϕ_max = (b_0… b_m-1)_2. If we try to maximize the measurement outcome of the first register, then we attain a value close to ϕ_max. 
	This maximization can be done by starting the measurement from the most significant qubits while trying to measure  as many qubits in |1⟩ state as possible. Therefore, we will measure a qubit: if the outcome is not |1⟩, then we apply the amplitude amplification to amplify the states where this qubit is in |0⟩ state and then do the measurement again. If the qubit does not yield |1⟩ after a few iterations, then we will assume |0⟩ as the qubit value and move on to the next qubit. And we repeat this process for the all qubits in the first register. This is explained in more details below and indicated in Fig.<ref> (Note that the measurements after each amplitude amplification is omitted in the figure.): 
	
	
		
  * We measure the first qubit (representing the most significant bit, b_0): 
		
			
  * If it is |1⟩, then we set |b_0⟩ = |1⟩ and move on to the next qubit in the collapsed state. 
			
  * Otherwise, we apply the amplitude amplification by flipping the signs of the states in which the first qubit is in |1⟩ state. While the flipping can be done by simply using the Pauli Z-gate, the amplification operator,  S_1, can be implemented in a way similar to Eq.(<ref>):
				
    S1 = U_1 U_0^⊥U_1^*,

   where U_1 represents all the quantum operations up to this point. Here, we only apply the  iterator G_1 = S_1 (Z⊗ I^⊗ mn-1)  a few times until the measurement yields |1⟩. If it does not, then |b_0⟩ is set to |0⟩.
		 
		
  * In the second qubit, we repeat the same process. However, this time 
		G_2 = S_2 (Ẑ⊗ I^⊗ mn-2); where, S_2 involves all the operations done up to this point, and the gate Ẑ is the controlled-Z gate acting on the second qubit and controlled by the first qubit: if the first qubit was |0⟩, then the control bit is |0⟩ (i.e. the gate acts when the first qubit is |0⟩.). Otherwise, it is set to |1⟩. 
		
  * Similarly, using Z gates controlled by the previous qubits, the measurements along with the amplitude amplifications are repeated for the remaining qubits. Here, the control-bits are either 0 or 1 determined from the measurement results of the previous qubits.
	
	The above maximization method is able to amplify the amplitude of ϕ_max if at any point the probability to measure |1⟩ on the qubit is not exponentially small. Otherwise, the number of the amplitude amplification required to see |1⟩ on that qubit becomes exponentially large. 
	Since the amplitude amplification  is only applied a few times (when |1⟩ is not encountered, the qubit is assumed to be |0⟩), this will cause an error in the result.  
Let us assume that the condition given in Assumption <ref> holds: i.e., if the bit value of any tth qubit is 1 in the binary value of ϕ_max = (b_0… b_m-1)_2; then after the individual measurements of the first (t-1) number of qubits with the values (b_0b_1… b_t-2)_2, the probability of seeing |1⟩ on the tth qubit is not exponentially small in the normalized-collapsed state.
	This assumption  affects the accuracy of the result rather than the running time since the amplitude amplification on a qubit is applied only a few times and when |1⟩ is not encountered, the related bit value of ϕ_max is assumed 0. 
	
	To further simplify the circuit in Fig.<ref> and the numerical simulations, we will also make following remark:
	

		
		 S_1 can be used in places of S_2… S_m to simplify the implementation of the amplitude amplifications.

	The circuit in accordance with the above remark is presented in Fig.<ref> (The measurements on the qubits are also explicitly indicated in this figure however not in Fig.<ref>).  Sect. VI gives a numerical example based on this circuit.
	Now, we will explain  how this circuit may yield the solution by going through the measurements of the first two qubits on the circuit:
Let us first divide the state given in Eq.(<ref>) (the state after U_1 in Fig.<ref>) into four parts with the same length:
		
    |ψ_2⟩ = 
    		(
    		x_0
    x_1
    x_2
    x_3).

	The probabilities of measuring |0⟩ and |1⟩ on the first qubit are P_0 = (||x_0||^2 + ||x_1||^2 ) and P_1 = (||x_2||^2 + ||x_3||^2 ), respectively.
	If P_1 is not exponentially less than P_0, then with the help of the amplitude amplification (G_1 = S_1Ẑ), the first qubit, can be measured in |1⟩. Therefore, b_0 becomes 1.
    Let us assume we obtain b_0=1 after the measurement. 
		If we use a qubit  in place of the first qubit and initialize it in |1⟩ state, we obtain the following normalized-sate:
		
    |ψ_3⟩ =
    		|1⟩⊗( 
    		ζx_2
    ζx_3),
    		 with ζ = 1/√(||x_2||^2+||x_3||^2).

		For the second qubit,  the part represented by x_3 is marked by the controlled Z gate, and then S_1 is applied:
		
    S_1(Ẑ⊗ I)|ψ_3⟩
    		=(2|ψ_2⟩⟨ψ_2|-I)
    		( 
    		0
    0
    ζx_2
     -ζx_3)
    		=ζ( 
    		2d_x x_0
    
    		2d_xx_1
    
    		(2d_x-1)x_2
    
    		(2d_x+1) x_3),

		where d_x = ||x_2||^2- ||x_3||^2. 
		Due to ||x_2|| ≥ ||x_3||, d_x≥ 0:
		
			
  * If dx ≥ 0.5, then all of the amplitudes in the above quantum states are unmarked. Therefore, in the subsequent iteration of AA only x_3 will  be marked, and the amplitudes corresponding to x_3 will be amplified.
			
  * If dx = (||x_2||- ||x_3|| )< 0.5, that means the probability difference between |0⟩ and |1⟩ is small; thus, we are very likely to measure |1⟩  after the first amplitude amplification. After the measurement, the state collapses to 
			
    ζ(0
    
    			2d_xx_1
    0
    
    			(2d_x+1) x_3).

		
	
	


§ COMPLEXITY ANALYSIS

 We will follow the circuit in Fig.<ref> to analyze the complexity of the whole approach under Assumption 1 and 2. The algorithm starts with two quantum registers of respectively m and n qubits, and then later in the maximum finding part of the algorithm it uses another register with m qubits which is implicitly indicated in Fig.<ref> but not  in Fig.<ref>. Therefore, the total number of qubits employed in the whole running of the algorithm is (2m+n).

Since U involves only phase gates described in Eq.(<ref>), using U^2^j, 0 ≤ j<m in the phase estimation requires only n number of controlled phase gates (Note that the power of the unitary can be taken by simply changing the angles of the rotation gates.).
	Therefore, including the complexity of the quantum Fourier transform <cit.>, U_pea, the phase estimation part, requires O(n+mlgm) =O(poly(n)) number of quantum gates. 
	
	In the amplitude amplification part, the operator F_ϕ can be  designed in O(poly(n)) time by using a logical circuit: i.e., the circuit is composed of X and Z gates and marks all of the states less than W.   
Moreover, the implementation of S defined in Eq.(<ref>) involves the Hadamard gates, U_pea and U_0^⊥ all of which  can be implemented in polynomial time. 
	
The remaining part of the circuit is for finding maximum and involves  S_js and controlled-Z gates. The implementation of any S_j is similar to the operator S: they involve the repetitions of the circuit up to their location, and hence requires more computations. However, because of Assumption 2, this part of the circuit and the whole processes are still bounded by some polynomial time, O(poly(n)).



§ APPLICATION TO 1/0-KNAPSACK PROBLEM

The maximum subset-sum problem is related to many other problems. One of these  is the 1/0-knapsack problem <cit.> described as: For a given items with weights {w_0 … w_n-1} and values {v_0, v_n-1}, determine which items should be included in a subset to maximize the total subset-value while keeping the total-weight less than W.
	This problem can be solved in a similar fashion to the subset-problem by adding one additional register to the algorithm:
	
		
  * |sw⟩ – The first register holds the sum of the weights.
		
  * |sv⟩ – The second register holds the values.
		
  * |j⟩ – The third register indicates the items included in the subset: |j⟩ describes the jth vector in the standard basis.
	
	The algorithm starts with constructing the superposition of the possible sums of weights and values as a quantum state by using the phase gates where the least-significant-bits encode the item-values while the most-significant bits are used for the weights. After the phase estimation, the following quantum state is generated:
	
    |ψ_1⟩ = 
    	1/√(N)∑_j=1^N|sw_j⟩|sv_j⟩|j⟩

	Then, applying the amplitude amplification, the states where sw_j ≥ W are eliminated and  the probability of the states where  |sw_j⟩ < W are put into the equal superposition:
	
    |ψ_2⟩ = 
    	1/√(|L|)∑_j∈ L|sw_j⟩|sv_j⟩|j⟩

	Now, the maximum finding is done on the second register:  After finding |sv_j⟩ with the maximum decimal value, the solution to the knapsack problem 
	is obtained from the corresponding |j⟩ which indicates the involved items. 

	

§ NUMERICAL EXAMPLE

	In this section, we present a random numerical example based on the circuit in Fig.<ref>.
	Let us assume that given the set of values 
	
    V = {
    	0.10937500,
    
    	0.10546875,
    
    	0.10156250,
    
    	0.09375000,
    
    	0.05468750,
    
    	0.02343750,
    
    	0.00390625
    	},
 
	which are normalized so that the maximum possible sum is at most 0.5, we are asked to find the subset which gives the maximum possible sum less than W = 0.19921875. If we use 9 bits of precision: i.e. m=9 (the size of the first register in PEA), then W=(001100101)_2).   
	
	We start with the construction of U which requires a qubit and a single rotation gate for each element of V: that means n=7 (the size of the second-register in PEA) and U∈ C^⊗ n. 
	The eigen-phases of U shown in Fig.<ref> represents the solution space, the possible subset-sums of V.
 Fig.<ref> depicts the distribution of these phases.
	
	
	
	
	
	After PEA is applied with an initial superposition state on the second register; using AA, the amplitudes of the states in which the phase value on the first register is less than W=(001100101)_2 are marked and amplified. After one iteration of AA, the probability of the eigenvector-phase pairs are presented in Fig<ref>. 
	At this point, we have ∑_j, ϕ_j<W|ϕ_j⟩|j⟩.  
		
	In the maximum-finding part, we start doing the measurement from the most significant qubits: 
	
		
  * Qubit-1 and qubit-2 yields |0⟩s with probability ≈1s. Therefore, |b_0b_1⟩ = |00⟩. After the normalization, we have the solution space where all ϕ_js are less than W. This is shown in Fig.<ref>.
		
  * The measurement on qubit-3 yields either |0⟩ or |1⟩ with probabilities, respectively, 0.4390 and 0.5610. Therefore,  it is very likely |1⟩ is measured after a few attempts. 
		In that case, we have |b_0⟩|b_1⟩|b_2⟩=|0⟩|0⟩|1⟩ on the first three qubits and the collapsed-state on the remaining qubits. 
		The normalized probabilities at this point are drawn on Fig.<ref>.
		
  * The probabilities of |0⟩ and |1⟩ for qubit-4 is 
		0.8261 and 0.1739 in the normalized state. 
		After a few measurements, if we see |1⟩, we set |b_4⟩ = |1⟩ and continue on the fifth qubit. Otherwise, we apply the amplitude amplification. This changes the probabilities for qubit-4 to    0.1991 and
		0.8009, respectively. However, it also brings back some of the eliminated states with some small probabilities. This is shown in Fig.<ref>.
		After the measurement of qubit-4 in |1⟩, the state collapses into four remaining eigenpairs with equal probabilities shown in Fig.<ref>.
		
  * In all of these four states, qubit-5 and qubit-6 are in |0⟩ state. Therefore, the measurements on these qubits yield |0⟩ states with probability 1.
		
  * The probability of seeing qubit-7 in |1⟩ state is 0.25. An iteration of AA amplifies this to 0.3488 as shown in Fig.<ref>. At this point, after a few measurements, we are likely to encounter |1⟩ on qubit-7. This collapses the state into the solution.
		
  * And finally, qubit-8 and qubit-9 are measured in |0⟩ with probability 1.	 
	
	The above maximization yields 0.1953125 as the maximum phase with |0011000⟩ as the corresponding eigenvector, which is the exact solution. 
	
	
	
	
	

§ CONCLUSION

In this paper we have studied the subset-sum and similar problems: e.g. the knapsack problem. In particular, we have generated the possible sums by using the phase estimation and the amplitude amplification algorithms. Then, we have used a maximum-finding procedure to obtain the solution.
	The approach requires polynomial time if the number of possible sums less than or equal to the given value are not exponentially smaller than the number of possible sums greater than the value. 
	In addition, it yields the exact answer  if the probability of seeing the correct bit value  on the tth qubit is not exponentially small in the normalized-collapsed state after the first (t-1) number of most significant bit values are correctly measured. 
	The approach is general and can be further improved for the similar NP-complete problems.

		unsrtnat
		

