# Quantum algorithm for binary assignment problem

Based on the properties of the qubit, how could I solve this problem:

• I have 3 person A B C and 2 taxis T1 and T2
• A and B are friends
• B and C hate each other
• A and C hate each other

How could I maximize the pairs of people (A,C), (A,B) and (B,C) which are friends and minimize the pairs of people who hate each other using qubits?

I know that 'pair' means entangled, so I have the possible 'pairs' in a quantum state

$$a|AB\rangle +b|AC\rangle+c|BC\rangle$$

satisfying $$|a|^{2}+|b|^{2}+|c|^{2}=1$$ after normalization.

• Hi and welcome to Quantum Computing SE. What do you mean by "maximize the pairs of people". – Martin Vesely Jan 31 '20 at 14:22
• the optimal form to transport the pair of people using quantum computation and the 2 taxis – Jose Javier Garcia Jan 31 '20 at 16:50
• It seems to me obvious, put person A and B to one taxi and person C to second one. I do not see need for quantum computer here. In case there are more pairs, I would use binary assignment problem and maximized objective function on quantum annealer, for example. – Martin Vesely Jan 31 '20 at 18:46
• As Martin said, this particular example is straightforward - are you looking to use this as some sort of 'proof of principle' example for a larger version of this problem (i.e. are you looking for how you'd solve the 'general case')? Or are you asking about more general optimisation problems? Or are you perhaps asking how to 'search' for the right result? Or have you got some proof-or-principle experiment in mind and are asking for more specific details on the level of what gates to use? (edit: I've just spotted that the answer below is what you want, so I'll take that to answer this comment) – Mithrandir24601 Feb 2 '20 at 10:54

I will try to give you a hint how to rewrite your problem as an binary optimization problem which can be solved on quantum annealer, i.e. a single purpose quantum computer for solving optimization task (see more about annealers here).

Your problem as an binary assignment problem:

Lets denote $$x_{ik} \in \{0;1\}$$ a binary variable meaning whether a person $$i$$ is assigned to a taxi $$k$$ (i.e. $$x_{ik} = 1$$) or not (i.e. $$x_{ik} = 0$$). Further let $$P$$ be a set of persons and $$T$$ set of taxis. Without loss of generality, assume that number of taxi is half the number of persons (in case number of persons is odd, you can add a dummy person, when the dummy is assigned to some taxi, this means that only one person is in the taxi).

Lets denote $$c_{ijk}$$ a cost of assigning persons $$i$$ and $$j$$ to taxi $$k$$. In case the persons are friends then $$c_{ijk} = 1$$, in case they hate each other then $$c_{ijk} = -1$$ and if one person is the dummy one then $$c_{ijk} = 0$$.

$$f = \sum_{i,j \in P \\k \in T} c_{ijk}x_{ik}x_{jk} \rightarrow \mathrm{MAX},$$

subject to conditions

$$\forall k \in T: \sum_{i \in P} x_{ik} = 2$$

and

$$\forall i \in P: \sum_{i \in T} x_{ik} = 1$$

The first condition means that there are two persons in each taxi, the second one means that each person is assigned to just one taxi.

Now you can employ a quantum annealer to perform the optimization.

• bravo :D , the perfect answer – Jose Javier Garcia Feb 1 '20 at 11:55