Intriguing scientific problems pop up when you would rather take your mind off them for a while, e.g., when playing video games -although, of course, it comes as no complete surprise to encounter them in this domain. Video games, by nature, pose a wide range of problems that players are expected to solve in order to progress, such as slaying enemies, traversing mazes or solving logical puzzles. Some games have even been shown to be NP-complete [1]. It is, however, a mild surprise to encounter them in Minecraft, which is an exceptionally serene open-world sandbox game developed by Mojang and first published around 2010 1 . In Minecraft, players can roam around a vast world containing mountains, oceans and caves made up entirely of cubic blocks, giving the game its unique and slightly retro visual quality (see Fig. 1). The game has been praised for fostering creativity in children (and adults) and has even been used as a tool for teaching [2].

However, in the darkness of a cave, hostile monsters can spawn on top of blocks that are insufficiently lit, either by the sun or a light source such as a torch or lantern. These monsters will attack the player, who therefore wants to light up dark areas as best as they can while exploring. At the same time, building torches requires valuable resources, which is why the 1a two players are running towards a village through a landscape with a river on the left. The entire game world is made up of cubes called "blocks". Figure 1b shows a cave with a few torches that illuminate the floor partly. In the foreground, a hostile creature called "Creeper" is searching for players to attack. Such creatures spawn on the surface of blocks that are below a certain light level.

player wants to use them sparingly, which leaves us with an interesting constrained optimization problem: Where should we place torches to properly light up an area using as few torches as possible?

The first key observation is that, given the discrete nature of Minecraft, solutions to this problem can be described by binary variables 𝑥 𝑠 ∈ {0, 1} = . . B, where 𝑥 𝑠 = 1 indicates that we should place a torch at location 𝑠. Problems of this kind can be approached with Quantum Computing, which has been a promising focus of research in recent years. Quantum Computers use Qubits to perform computations, which can take values 0 and 1, but also be in a superposition of both at once. In particular, Quantum Annealers are being built that can be used to find the ground state of Ising models by means of quantum tunneling effects [3,4]. This model is equivalent to a class of quadratic binary optimization problems called Qubo: Given an upper triangular weight matrix 𝑄 ∈ R 𝑛×𝑛 , we want to find a binary vector 𝑥 * such that

where 𝑓 𝑄 is called the energy function. This problem is NP-hard, and numerous problems have been re-formulated to be solvable in the form of Qubo, ranging from economics and finance [5,6,7] over satisfiability [8], resource allocation and routing problems [9,10] to machine learning [11,12,13,14,15,16]. The promise of efficient solvability on Quantum Hardware has renewed and intensified research efforts for finding Qubo formulations of various problems.

In this paper, we derive a formulation for the TorchPlacement problem. Due to the large number of constraints, our method involves a learning procedure for Lagrangian weights. This is performed in an iterative fashion on a real quantum computer, similar to [17]. We demonstrate our method in a range of experiments, using both generated and actual game data from a Minecraft world. Further, we discuss the surprising connection to another optimization problem that we uncovered in the process of working on this article.

In Section 2, we give a formal description of the TorchPlacement problem. In Section 3, we develop a Qubo formulation that attempts to solve it, combining quantum-enhanced optimization with an iterative learning scheme. In Section 4, we use our method to solve a range of example instances of TorchPlacement and discuss our observations. Section 5 puts our work in the context of similar work and related problems. Finally, in Section 6 we summarize our findings.

As input, we are given a heightmap of a room, consisting of a rectangular grid of tiles, as shown in Fig. 2. The grid has integer width 𝑤 and height ℎ. Additionally, each grid site 𝑠 = (𝑖, 𝑗) ∈ [ℎ] × [𝑤] has an elevation value 𝑧(𝑠) ∈ N 0 ∪ {∞}, where N 0 denotes the set of natural numbers including 0. We use the notation [𝑛] . . = {1, . . . , 𝑛}. Intuitively, 𝑧(𝑠) is the "floor level" of 𝑠. If 𝑧(𝑠) = ∞, the tile is considered to be a wall. Let 𝒮 = {𝑠 ∈ [ℎ] × [𝑤] | 𝑧(𝑠) < ∞} the set of all grid sites that are not walls.

Intuitively, the height map describes the top-down view of a 3-dimensional room consisting of cubic blocks that can be either empty or non-empty (see Fig. 4). Assuming a discrete coordinate system, each block has a location (𝑖, 𝑗, 𝑘) ⊤ ∈ Z 3 . If 𝑧(𝑖, 𝑗) = 𝑟, then ∀𝑟 ′ < 𝑟 ≤ 𝑟 ′′ : (𝑖, 𝑗, 𝑟 ′′ ) ⊤ is empty and (𝑖, 𝑗, 𝑟 ′ ) ⊤ is non-empty. Let the predicate E(𝑝) ≡ ⊤ (true) if and only if the block at 𝑝 is empty. Two blocks at 𝑝 and 𝑝 ′ are considered neighbors if ‖𝑝 − 𝑝 ′ ‖ 1 = 1, i.e., if they

Finally, the distance between two sites 𝑠 = (𝑖, 𝑗) and 𝑡 = (𝑖 ′ , 𝑗 ′ ), denoted by 𝑑(𝑠, 𝑡), is the shortest path from (𝑖, 𝑗, 𝑧(𝑠)) ⊤ to (𝑖 ′ , 𝑗 ′ , 𝑧(𝑡)) ⊤ moving through empty neighboring blocks:

If there is no path between the two blocks, we set 𝑑(𝑠, 𝑡) = ∞. Examples of heightmaps with distances are shown in Fig. 3.

Given a heightmap, our objective is to place torches on some of the tiles in such a way that all tiles have a minimal light level of 𝐿 min , using as few torches as possible. Light levels are integers 𝑙 ∈ N 0 , where 0 indicates complete darkness. If a torch is placed on a tile, the tile itself receives a light level of 𝐿 torch . The light spreads to surrounding tiles and decreases gradually with distance 𝑑 described in Eq. ( 2), both horizontally and with elevation. If a tile is illuminated by multiple nearby torches, it assumes the maximum over all light levels. Note that the way that light spreads in Minecraft does not at all align with physical reality, but is game-specific.

Where in reality we would expect light to move in straight lines and be blocked by obstacles, light in Minecraft has no sense of direction, but spreads evenly to all neighboring blocks, and can even "creep around corners". Let 𝒯 ⊆ 𝒮 be the set of all tile sites that have a torch. The light level of each tile 𝑠 can then be described mathematically as

If 𝒯 = ∅, then we set ∀𝑠 : 𝑙(𝑠 | ∅) = 0. Overall, the problem we are trying to solve can be formalized as

In this article, we set 𝐿 torch = 14 and 𝐿 min = 8, which are the same values as in Minecraft.

As hinted at in the introduction to this article, TorchPlacement lends itself to Qubo as its candidate solution space is the set of binary vectors B 𝑛 . In order to derive a Qubo formulation for TorchPlacement, we need to (1) embed the candidate solutions into binary vectors and (2) formulate a 2nd order polynomial whose minimizing binary vector corresponds to a solution of our original problem. The latter is done by computing the Qubo parameter values 𝑄 𝑖𝑗 (see Eq. ( 1)) from our problem instance at hand, which in our case is a heightmap with tiles 𝒮 and its corresponding distance function 𝑑 : 𝒮 × 𝒮 → N 0 as described in Section 2.

We firstly arrange the elements of 𝒮 in an arbitrary but fixed order 𝑆, such that 𝑆 𝑖 denotes the location of the 𝑖-th tile for all 𝑖 ∈ [𝑛] with 𝑛 . . = |𝒮|. A subset 𝒯 ⊆ 𝒮 then corresponds to a binary vector

for some Boolean expression B. Equation ( 3) can now be written as

It is easy to see that if we set 𝑄 𝑖𝑖 = 𝑃 ∀𝑖 ∈ [𝑛] with some arbitrary positive value 𝑃 > 0, the energy function 𝑓 𝑄 will only be minimal for the binary vector 0 with 𝑓 𝑄 (0) = 0 = ‖0‖ 1 .

Embedding the constraints from Eq. ( 4) into Qubo is far more challenging: Given a candidate solution 𝑥, we need to ensure that the light level is at least 𝐿 min , which is equivalent to saying that the distance to the nearest torch must be short enough that the light coming from it is still bright enough. To ensure this, the torch's distance can be at most 𝐿 torch − 𝐿 min :

There are two problems with this set of inequalities: Firstly, max is a non-linear operation, and Qubo can only represent quadratic energy functions. Secondly, Qubo is unconstrained by definition, which is why we need to employ techniques to embed the constraints directly into the weight matrix 𝑄 such that the unconstrained solution still obeys our constraints. In the following subsections we describe how we approached both of these challenges.

There are several smooth approximations of the max functions, such as the LogSumExp, 𝑝-norm or the Boltzmann operator. As an example, consider the first-mentioned function

We can re-write our inequality constraints in Eq. ( 5) by inverting the sign and incorporating the condition

Thanks to all 𝑥 𝑗 being binary, we can re-write 𝑒 𝑎𝑥 𝑗 as (𝑒 𝑎 − 1)𝑥 𝑗 + 1, which yields a linear constraint

where 𝑢

and 𝑣 𝑖 = 𝑒 𝛼(𝐿 min −𝐿 torch ) − 𝑛. LSE 𝛼 approaches max better the larger we choose 𝛼. We implemented these constraints and found that approximations of max lead to numerical instability due to the large magnitude differences between the coefficients, rendered solutions output from the Qubo solvers useless.

However, there is a simpler formulation that exploits the binary nature of our constraints. For that, we define the matrix 𝐷 ∈ {0, 1} 𝑛×𝑛 with entries 𝑑 𝑖𝑗 to be

In order to ensure that min 𝑗 𝑑(𝑆 𝑖 , 𝑆 𝑗 ) ≤ 𝐿 torch − 𝐿 min , we can check whether

which immediately yields linear constraints and circumvents the max function entirely. Using Eq. ( 6) the optimization problem in Eqs. ( 3) and ( 4) can be reformulated to

where 1 is the 𝑛-dimensional vector consisting only of ones, and ≥ is applied element-wise.

Realizing this, we find that TorchPlacement has striking similarity to the SetCover problem:

Theorem 1. TorchPlacement is a special case of SetCover.

Proof. In SetCover, we are given a set 𝐴 and a collection of subsets 𝐵 𝑖 with 𝐵 𝑖 ⊆ 𝐴 for each 𝑖 ∈ 𝐼, and ⋃︀ 𝑖∈𝐼 𝐵 𝑖 = 𝐴. The objective is to find a 𝐽 ⊆ 𝐼 such that |𝐽| is minimal and ⋃︀ 𝑗∈𝐽 𝐵 𝑗 = 𝐴. Given a heightmap with tiles 𝒮 and distance function 𝑑 as defined in Eq. ( 2), we set 𝐴 = 𝒮, 𝐼 = [𝑛] and 𝐵 𝑖 = {𝑠 ∈ 𝒮 : 𝑑(𝑆 𝑖 , 𝑠) ≤ 𝐿 torch − 𝐿 min } for all 𝑖 ∈ [𝑛]. Thus, a solution 𝐽 ⊆ 𝐼 with minimal |𝐽| is a minimal set of torches that illuminates all other tiles.

The question remains how to obtain a Qubo from the constrained formulation in Eqs. ( 7) and ( 8).

To answer this question, we remark that the linear inequality constraint in Eq. ( 8) can be reformulated with using an auxiliary vector 𝑧 ∈ N 𝑛 0 with positive integer entries

leading to the slightly different but equivalent problem formulation

A common way of solving an optimization problem with equality constraints as in Eqs. ( 9) and ( 10) is to introduce a matrix of binary slack variables 𝑆 ∈ {0, 1} 𝑛×𝑚 with 𝑚 . . = ⌈log 2 𝑛⌉ [18].

Considering the vector 𝑟 corresponding to all powers of two up to 2 𝑚 , i.e., 𝑟 = (1, 2, 4, . . . , 2 𝑚 ) ⊤ , we find that 𝑧 = 𝑆𝑟. The constrained problem in Eqs. ( 9) and ( 10) can then be reformulated to an equivalent unconstrained problem by introducing a penalty parameter 𝛽 > 0 min

Using this formulation, however, comes with the overhead of introducing 𝑛𝑚 additional binary variables leading to a total Qubo dimension of 𝑛(𝑚 + 1). As we are still in the era of noisy intermediate-scale quantum (NISQ) computers [19], it is better to resort to a Qubo formulation that uses fewer qubits.

To this end, we use an iterative method called Alternating Direction Method of Multipliers (ADMM) [20]. Firstly, we establish a new problem formulation min 𝑥∈{0,1} 𝑛 ,𝑧∈Z 𝑛

subject to 𝑐 (𝑥, 𝑧) = 0 ,

with 𝛾 > 0, 𝑐 (𝑥, 𝑧) . . = 𝐷𝑥 − 1 − 𝑧, and Θ being an element-wise step function defined as Θ(𝑧) . . = (1{𝑧 1 < 0}, . . . , 1{𝑧 𝑛 < 0}). The term 1 ⊤ Θ(𝑧) penalizes vectors 𝑧 ∈ Z 𝑛 with negative entries, since we want 𝑧 ∈ N 𝑛 0 . Note that optimal solution vectors 𝑥 ∈ {0, 1} 𝑛 , 𝑧 ∈ Z 𝑛 of Eq. ( 13) are also optimal for the problem in Eqs. ( 9) and (10). We then introduce the augmented Lagrangian [21,22] 𝐿 (𝑥, 𝑧, 𝜆, 𝜇)

with 𝜆 and 𝜇 being coefficients and multipliers for the penalty terms. For minimizing Eq. ( 14), we use ADMM, which is outlined in Algorithm 1. The vectors 𝑥 and 𝑧 are updated in an alternating fashion. In our case, line 5 can be written as arg min Update 𝜇 * 9: until a convergence criterium is met

corresponding to a Qubo formulation in Eq. ( 1), which can be solved with a quantum computer. Line 6 can be reduced to arg min

where 0 is the 𝑛-dimensional vector consisting only of zeros and max is taken element-wise. For solving our original problem in Eqs. ( 7) and ( 8) we solve a sequence of Qubo problems and update the other parameters according to Algorithm 1. Using a quantum computer for the Qubo instances results in a hybrid quantum-classical algorithm. Let the subscript 𝑘 denote the state of the parameters 𝑥 * , 𝑧, * 𝜆 * , 𝜇 * after the 𝑘-th iteration of ADMM. We choose the following update rule for 𝜇 * 𝑘 in line 8

with a fixed learning rate 𝜌 ≥ 1, following [20]. In place of a convergence criterium in line 9 we use a fixed budget of 𝑁 of calls to the quantum computer.

We conduct experiments on different exemplary heightmaps. Some heightsmaps are randomly generated from 2D Perlin noise [23], others are created from cave sections within a Minecraft Python package, parellelizing both methods, leading to better performance. For all solvers we use the standard parameters. As a pre-processing step we perform parameter compression [24], which leads to improved results for QA. The ADMM is repeated 10 times for every solver and heightmap and we plot the mean performance along with the 95%-confidence intervals. We found the hyperparameters 𝜇 0 = 0.01 and 𝜌 = 1.1 to yield the best results, hence we fix these values for the upcoming experiments. In Fig. 5, we compare the performances of the different Qubo solvers for one real Minecraft cave from Fig. 4 (right) with 𝑛 = 67. For this, we plot the number of torches as well as the number of violated constraints over the iterations of ADMM. We can see that the four Qubo solvers converge to fulfilling all constraints, while QA places the most torches. This indicates that its solution quality falls behind the other methods, which is a common problem of NISQ devices. However, in Fig. 6 we depict the result of ADMM with QA for a particular run, after 2, 5 and 10 iterations. After 10 iterations, an optimal solution is found, such that every block is lit.

From now on, we use TabuSA, since the dimension of the upcoming problems is too large to obtain useful results with QA. Fig. 7 depicts solutions after a certain number of ADMM iterations on the heightmaps of the other real Minecraft cave from Fig. 4 (left) with 𝑛 = 195. Again, we can see that with more iterations, more torches are placed and the constraints become fulfilled. In Figs. 8 to 11 we depict ADMM solutions for randomly generated heightmaps of varying sizes, using the TabuSA solver. For every map, two intermediate results during the Lagrangian learning phase are shown. We can see that fewer and fewer constraints are violated, until finally all tiles are lit with a small number of torches.

Analyzing games in terms of their computational complexity has been part of computer science research for decades [1,25,26]. Minecraft, in particular, has been used as a tool for research [2]. As mentioned in Section 3.1, it turns out that TorchPlacement is a special case of SetCover, where the subsets have a spatial interpretation in discrete 3D space. A Qubo formulation of SetCover is given in [27], where auxiliary qubits are used to encode inequality constraints. We chose a different strategy by employing ADMM [20] to learn the Lagrange multipliers 𝜆 iteratively in a hybrid quantum-classical fashion, which leads to smaller Qubo instances with fewer qubits. A similar approach is followed in [28] using a custom iterative Lagrangian algorithm, which we tried and found not to yield good results with our inequality constraints. ADMM, which we chose instead, is more firmly grounded in theory.

We also find that TorchPlacement and SetCover are similar to other problems such as MaximumCoverage, where an upper limit 𝑘 is given, and -staying in the context of TorchPlacement-we are looking to light up the largest possible area using at most 𝑘 torches.

In this article, we showed that the TorchPlacement problem arising from the video game Minecraft can be solved on quantum computers. To this end, we used an ADMM-based procedure to learn Lagrange multipliers in a Qubo formulation, which we then solved on a quantum annealer. In contrast to other methods for solving the more general SetCover problem we require no auxiliary variables. The results demonstrated that the method works well for heightmaps with up to 700 floor tiles. Due to limitations of today's noisy quantum hardware, we were able to solve the problem on an actual quantum annealer with heightmaps up to 𝑛 ≤ 100. While we considered TorchPlacement from a video game perspective, it generalizes to similar setups, where we want to cover a certain area by using as few resources as possible: Sensors or surveillance cameras with a fixed finite set of possible locations come to mind. When we can define a distance between these locations, and we require a maximum distance from each location to the nearest resource, our method is applicable.

To the best of our knowledge, this article is the first instance of quantum computing being applied to solving a problem arising from Minecraft. While this is a more lighthearted context to employ this relatively new computing resource, it has the potential to grant us insights that may be useful for applications to real-word problems, and serve as an illustrative example of how to approach problems from a quantum computing perspective.