3
$\begingroup$

Puzzle

I have the following puzzle for which I would like to create a quantum algorithm.

  1. There are 2 players that need to complete 3 tasks as fast as possible.
  2. There are 3 different types of tasks ( A, B, C )
  3. There are 3 different types of tools (a, b, c)
  4. Each player will only get 2 tools (they might get the same tool twice)
  5. Tool a will make that the player can finish task A 10 minutes faster than without tool a.
  6. Tool b will make that the player can finish task B 10 minutes faster than without tool b.
  7. Tool c will make that the player can finish task C 10 minutes faster than without tool c.
  8. The output of the quantum algorithm must be (a) a random combination of the 3 tasks (the same task might appear multiple times) and (b) a random assignment of 2 tools to each of the 2 players but it should also remain a fair competition (in other words one player will not gain more time in total thanks to the set of tools he got).

So a possible outcome of the quantum algorithm:

  • Tasks A, A, C (note that same task can appear multiple times) and
  • Player one gets tools a,b
  • Player two gets tools a,a (although he gets 2 a tools - he can only use one tool at a time - so the 2nd a tool would not give any benefits)

So, in this case, both players will equally benefit (= 20 minutes) thanks to tool a and the 2 tasks A, A.

So how would you implement such a problem in a quantum algorithm?


Generalized Puzzle

Of course this puzzle can be further generalized as:

  • each player has to complete n tasks (and not 3)
  • instead of 3 different types of tasks (A, B, C) and 3 corresponding different types of tools (a, b, c), there are t different types of tasks with corresponding tools giving them a 10 minute performance benefit.
  • each player gets k tools instead of 2.

I don't need an answer on this generalized puzzle ! I am more than happy to get an answer on the simple puzzle.

$\endgroup$
  • 5
    $\begingroup$ Do you have a classical version of the algorithm? Do you have any reason to expect a quantum algorithm will be any better than a classical one? $\endgroup$ – DaftWullie Jun 1 '18 at 22:39
  • $\begingroup$ "but it should also remain a fair competition (in other words one player will not gain more time in total thanks to the set of tools he got)" does this mean that the algorithm should give each player a set of tools such that they get the same time bonus? Also, in your example, there are two 'a' tasks, and so the 'a' tool is used twice by the first player, therefore gaining 20 minutes. but the second player has two 'a' tools, leading me to think they should have a gain of 40 minutes. can a player only use one tool at a time? $\endgroup$ – heather Jun 2 '18 at 1:24
  • $\begingroup$ Indeed the set of tools should give each player the same time bonus for the 3 tasks. Having the same tool twice won’t give you an extra benefit for the task (for this I have edited the description.) $\endgroup$ – JanVdA Jun 2 '18 at 9:10
  • $\begingroup$ Regarding first comment: in a classical program it will not be easy to come with a random solution. In a classical program you can of course iterate through all possibilities and check if it meets the fairness criteria and then randomly pick one of those good possibilities. But this approach won’t work for more complex cases (more tasks, more tools): the number of possible combinations becomes rapidly huge, so I was wondering if for such kind of problems quantum algorithms would be superior. $\endgroup$ – JanVdA Jun 2 '18 at 9:26
  • 1
    $\begingroup$ However, please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – Discrete lizard Jun 4 '18 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.