0
$\begingroup$

I have a set S = {a, b, c, d, e, f} from which I need to find out if there exists two subsets S0 and S1 such that the sum of elements of S0 = sum of elements of S1. Also, the max of S0 and S1 cannot exceed h. I'm thinking of treating it as a search problem. I have to use quantum walk algorithm to solve and develop the quantum circuit for this as well. I understand that I can encode a to f using qubits for example, then create a circuit for finding sets of possible elements. And another circuit to identify those which meets the criteria. Where to begin? Any references could be of great help.

$\endgroup$
6
  • 1
    $\begingroup$ Can you give some context that would explain why you posted this question on the quantum computing stackexchange? E.g. does the task require you to use a quantum circuit? $\endgroup$ Mar 17, 2023 at 8:45
  • $\begingroup$ @RajivKrishnakumar yes, have to create the quantum circuit which does this. added context. thanks! $\endgroup$
    – Van Peer
    Mar 17, 2023 at 9:50
  • 1
    $\begingroup$ I'm not sure to understand, what prevents you from using $S_0=S_1$? Do you also have the condition that $S_0\cap S_1=\varnothing$? $\endgroup$
    – Tristan Nemoz
    Mar 18, 2023 at 13:45
  • 1
    $\begingroup$ If you have $S_0 \cup S_1 = S$ this would be the subset-sum problem. Should I assume you are looking for smaller-sized solutions? $\endgroup$
    – rhundt
    Mar 18, 2023 at 14:42
  • $\begingroup$ @rhundt that's correct. for example, S={0,2,3,4,5,6} then S0= {0,2,3,5} and S1={4,6}. Yes to smaller-sized solutions. Interested to know what approaches to follow. $\endgroup$
    – Van Peer
    Mar 18, 2023 at 17:20

1 Answer 1

1
$\begingroup$

I've put an implementation here. The idea is to construct a Hamiltonian, which would be a diagonal matrix, and then use a variational algorithm to see whether there exists a state with eigenvalue 0, which would indicate equilibrium. Of course, since I constructed the Hamiltonian I can just inspect it. VQE-by-peek-a-boo.

This doesn't tell you what the solution is, only whether one exists. At least, at this point. Not sure this could be massaged further to find an exact solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.