Efficient Light Source Placement using Quantum Computing Sascha Mücke1 , Thore Gerlach2 1 Lamarr Institute, TU Dortmund University, Dortmund, Germany 2 Fraunhofer IAIS, Sankt-Augustin, Germany Abstract NP-hard problems regularly come up in video games, with interesting connections to real-world problems. In the game Minecraft, players place torches on the ground to light up dark areas. Placing them in a way that minimizes the total number of torches to save resources is far from trivial. In this paper, we use Quantum Computing to approach this problem. To this end, we derive a QUBO formulation of the torch placement problem, which we uncover to be very similar to another NP-hard problem. We employ a solution strategy that involves learning Lagrangian weights in an iterative process, adding to the ever growing toolbox of QUBO formulations. Finally, we perform experiments on real quantum hardware using real game data to demonstrate that our approach yields good torch placements. Keywords Quantum Computing, QUBO, Constrained Optimization, ADMM, Minecraft 1. Introduction 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 20101 . 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 LWDA’23: Lernen, Wissen, Daten, Analysen. October 09–11, 2023, Marburg, Germany $ sascha.muecke@tu-dortmund.de (S. Mücke); thore.gerlach@iais.fraunhofer.de (T. Gerlach) € https://smuecke.de/ (S. Mücke)  0000-0001-8332-6169 (S. Mücke); 0000-0001-7726-1848 (T. Gerlach) © 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings CEUR Workshop Proceedings (CEUR-WS.org) http://ceur-ws.org ISSN 1613-0073 1 https://www.minecraft.net/ CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings (a) Players approaching a village (b) Dimly lit cave with hostile creature Figure 1: Screenshots of Minecraft gameplay: In Fig. 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 (a) 20 × 15 (b) 20 × 15 (c) 40 × 30 (d) same as above, with torches (e) same as above, with torches (f) same as above, with torches Figure 2: Examples of heightmaps used as input data for our experiments. In the top row, lighter color indicates higher elevation 𝑧. In the bottom row, lighter color indicates light level, and the little torch symboles represent torches placed on the respective tiles. White tiles are walls (𝑧 = ∞). The data is randomly generated from 2D Perlin noise. 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 𝑥* = arg min 𝑓𝑄 (𝑥) 𝑥∈B𝑛 ∑︁ with 𝑓𝑄 (𝑥) .= 𝑥⊤ 𝑄𝑥 = . 𝑄𝑖𝑗 𝑥𝑖 𝑥𝑗 , (1) 1≤𝑖≤𝑗≤𝑛 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 opti- mization 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. 2. Problem Statement 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 𝑧(𝑠) ∈ N0 ∪ {∞}, where N0 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 (𝑖, 𝑗, 𝑘)⊤ ∈ Z3 . 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 3 1 2 1 2 3 1 2 5 4 2 4 6 Figure 3: Examples of distances in heightmaps: The number in the top right corner is the distance to the tile with the white circle. The distance is the shortest path through empty space moving from neighbor to neighbor. Left: All tiles have the same elevation. Right: The tile with distance 5 has elevation 2, the tile with distance 4 has elevation 1, all the others have elevation 0. A shortest path from the top left to the bottom right tile is indicated by the white line. Changes in elevation are drawn as smaller circles. The shortest path leads over the tile with elevation 1. The number of discrete steps taken gives the distance. share a face. The set of empty neighbors of 𝑝 is 𝒩 (𝑝) = {𝑝+𝑢 | 𝑢 ∈ Z3 , ‖𝑢‖1 = 1, E(𝑝+𝑢)}. Finally, the distance between two sites 𝑠 = (𝑖, 𝑗) and 𝑡 = (𝑖′ , 𝑗 ′ ), denoted by 𝑑(𝑠, 𝑡), is the shortest path from (𝑖, 𝑗, 𝑧(𝑠))⊤ to (𝑖′ , 𝑗 ′ , 𝑧(𝑡))⊤ moving through empty neighboring blocks: {︃ 0 if 𝑠 = 𝑡, 𝑑(𝑠, 𝑡) = ′ (2) 1 + min𝑠′ ∈𝒩 (𝑠) 𝑑(𝑠 , 𝑡) otherwise 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 𝑙 ∈ N0 , 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 𝑙(𝑠 | 𝒯 , 𝐿torch ) = max max{0, 𝐿torch − 𝑑(𝑠, 𝑡)} . 𝑡∈𝒯 If 𝒯 = ∅, then we set ∀𝑠 : 𝑙(𝑠 | ∅) = 0. Overall, the problem we are trying to solve can be formalized as min |𝒯 | with 𝒯 ⊆ 𝒮 (3) subject to 𝑙(𝑠 | 𝒯 , 𝐿torch ) ≥ 𝐿min ∀𝑠 ∈ 𝒮 . (4) In this article, we set 𝐿torch = 14 and 𝐿min = 8, which are the same values as in Minecraft. 3. A QUBO formulation for TorchPlacement 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 𝑑 : 𝒮 × 𝒮 → N0 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 𝑥 ∈ B𝑛 via 𝒯 = (1{𝑆𝑖 ∈ 𝒯 })⊤ ∧ 𝑖∈[𝑛] , where 1{·} is the indicator function defined as {︃ 1 if B ≡ ⊤, 1{B} .=. 0 otherwise . for some Boolean expression B. Equation (3) can now be written as min ‖𝑥‖1 with 𝑥 ∈ B𝑛 . 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 : min 𝑑(𝑆𝑖 , 𝑆𝑗 ) ≤ 𝐿torch − 𝐿min ∀𝑖 ∈ [𝑛] . (5) 𝑗∈[𝑛], 𝑥𝑗 =1 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. 3.1. Eliminating the Maximum Function 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 𝑛 1 ∑︁ LSE𝛼 (𝑎1 , . . . , 𝑎𝑛 ) ..= log 𝑒𝛼𝑎𝑖 . 𝛼 𝑖=1 We can re-write our inequality constraints in Eq. (5) by inverting the sign and incorporating the condition 𝑥𝑗 = 1 to max𝑗∈[𝑛] ((𝑃𝑖 − 𝑑(𝑆𝑖 , 𝑆𝑗 ))𝑥𝑗 − 𝑃𝑖 ) ≥ 𝐿min − 𝐿torch for some 𝑃𝑖 > min𝑗̸=𝑖 𝑑(𝑆𝑖 , 𝑆𝑗 ), which using LSE𝛼 yields 1 ∑︁ log 𝑒𝛼(𝑃𝑖 −𝑑(𝑆𝑖 ,𝑆𝑗 ))𝑥𝑗 −𝛼𝑃𝑖 ≥ 𝐿min − 𝐿torch 𝛼 𝑗 ∑︁ ⇔ 𝑒−𝛼𝑃𝑖 𝑒𝛼(𝑃𝑖 −𝑑(𝑆𝑖 ,𝑆𝑗 ))𝑥𝑗 ≥ 𝑒𝛼(𝐿min −𝐿torch ) 𝑗 Thanks to all 𝑥𝑗 being binary, we can re-write 𝑒𝑎𝑥𝑗 as (𝑒𝑎 − 1)𝑥𝑗 + 1, which yields a linear constraint ∑︁ 𝑛+ 𝑒−𝛼𝑃𝑖 (𝑒𝛼(𝑃𝑖 −𝑑(𝑆𝑖 ,𝑆𝑗 )) − 1)𝑥𝑗 ≥ 𝑒𝛼(𝐿min −𝐿torch ) 𝑗 ⇔ 𝑥⊤ 𝑢(𝑖) + 𝑣𝑖 ≤ 0 , (𝑖) 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 𝑑𝑖𝑗 = 1{𝑑(𝑆𝑖 , 𝑆𝑗 ) ≤ 𝐿torch − 𝐿min }, ∀𝑖, 𝑗 ∈ [𝑛] . In order to ensure that min𝑗 𝑑(𝑆𝑖 , 𝑆𝑗 ) ≤ 𝐿torch − 𝐿min , we can check whether ∑︁ 𝑥𝑗 𝑑𝑖𝑗 = (𝐷𝑥)𝑖 ≥ 1 , (6) 𝑗 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 min 1⊤ 𝑥 (7) 𝑥∈{0,1}𝑛 subject to 𝐷𝑥 ≥ 1 , (8) 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. ⋃︀ we are given a set 𝐴 and a collection of subsets 𝐵𝑖 with 𝐵𝑖 ⊆ 𝐴 for Proof. In SetCover, 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. 3.2. Handling Inequality Constraints 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 𝐷𝑥 ≥ 1 ⇔ 𝐷𝑥 − 1 = 𝑧 , leading to the slightly different but equivalent problem formulation min 1⊤ 𝑥 (9) 𝑥∈{0,1}𝑛 subject to 𝐷𝑥 − 1 − 𝑧 = 0, 𝑧 ∈ N𝑛0 . (10) 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 𝑚 ..= ⌈log2 𝑛⌉ [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 1⊤ 𝑥 + 𝛽 ‖𝐷𝑥 − 1 − 𝑆𝑟‖2 . (11) 𝑥∈{0,1}𝑛 ,𝑆∈{0,1}𝑛×𝑚 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 1⊤ 𝑥 + 𝛾1⊤ Θ(𝑧) (12) 𝑥∈{0,1}𝑛 ,𝑧∈Z𝑛 subject to 𝑐 (𝑥, 𝑧) = 0 , (13) 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] 𝜇 𝐿 (𝑥, 𝑧, 𝜆, 𝜇) ..= 1⊤ 𝑥 + 𝛾1⊤ Θ(𝑧) + 𝜆⊤ 𝑐 (𝑥, 𝑧) + ‖𝑐 (𝑥, 𝑧)‖2 , (14) 2 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 𝐿 (𝑥, 𝑧, 𝜆, 𝜇) = arg min 1⊤ 𝑥 + 𝜆⊤ 𝑐 (𝑥, 𝑧) + ‖𝑐 (𝑥, 𝑧)‖2 𝑥∈{0,1}𝑛 𝑥∈{0,1}𝑛 2 Algorithm 1 Alternating Direction Method of Multipliers (ADMM) Input: Initial 𝜇0 > 0, Output: 𝑥* , 𝑧 * , 𝜆* , 𝜇* optimizing 𝐿 (𝑥, 𝑧, 𝜆, 𝜇) 1: 𝑧 * ← 0 2: 𝜆* ← 0 3: 𝜇* ← 𝜇0 4: repeat 5: 𝑥* ← arg min𝑥 𝐿 (𝑥, 𝑧 * , 𝜆* , 𝜇* ) ◁ Quantum annealer can be used 6: 𝑧 * ← arg min𝑧 𝐿 (𝑥* , 𝑧, 𝜆* , 𝜇* ) 7: 𝜆* ← 𝜆* + 𝜇* 𝑐 (𝑥, 𝑧) 8: Update 𝜇* 9: until a convergence criterium is met 𝜇 (︁ ⊤ ⊤ )︁ = arg min 1⊤ 𝑥 + 𝜆⊤ 𝐷𝑥 + 𝑥 𝐷 𝐷𝑥 − (1 + 𝑧)⊤ 𝐷𝑥 , 𝑥∈{0,1}𝑛 2 corresponding to a Qubo formulation in Eq. (1), which can be solved with a quantum computer. Line 6 can be reduced to 𝜇 ‖𝑐 (𝑥, 𝑧)‖2 arg min 𝐿 (𝑥, 𝑧, 𝜆, 𝜇) = arg min 𝛾1⊤ Θ(𝑧) + 𝜆⊤ 𝑐 (𝑥, 𝑧) + 𝑧∈Z𝑛 𝑧∈Z𝑛 2 ⃦ ⃦2 ⊤ 𝜇⃦ 1 ⃦ = arg min 𝛾1 Θ(𝑧) + ⃦𝐷𝑥 − 1 − 𝑧 + 𝜆⃦ ⃦ 𝑧∈Z𝑛 2 𝜇 ⃦ = max{0, 𝐷𝑥 − 1} , 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 ⎧ ⎨𝜌𝜇𝑘 , if ‖𝑐 (𝑥𝑘 , 𝑧𝑘 )‖ > 10𝜇𝑘 ‖𝐷 (𝑧𝑘 − 𝑧𝑘+1 )‖ , ⎪ 𝜇𝑘+1 = 𝜇𝑘 /𝜌, if ‖𝐷 (𝑧𝑘 − 𝑧𝑘+1 )‖ > 10𝜇𝑘 ‖𝑐 (𝑥𝑘 , 𝑧𝑘 )‖ , ⎪ 𝜇𝑘 , else , ⎩ 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. 4. Experimental Evaluation 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 Figure 4: Screenshots of Minecraft caves. In Section 4 we use heightmaps based on these caves for our experiments. world. We compare four different Qubo solvers utilizing the D-Wave Ocean2 Python package: Simulated annealing (SA), Tabu search (Tabu), a combination of those two (TabuSA) and a real quantum annealer (QA), namely a D-Wave Advantage System 5.4 with 5614 qubits and 40,050 couplers. The combination of SA and Tabu is achieved by using the D-Wave Hybrid3 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. 2 https://docs.ocean.dwavesys.com/en/stable/ 3 https://docs.ocean.dwavesys.com/projects/hybrid/en/stable/ QA SA Tabu TabuSA 7.5 60 #Violated constraints 5.0 #Torches 40 2.5 20 0.0 0 0 5 10 15 20 0 5 10 15 20 Iterations Figure 5: Performance of the four Qubo solvers QA, SA, Tabu and TabuSA on the real Minecraft cave depicted in Fig. 4 (bottom). (a) Heightmap (b) 2 iterations, (20) (c) 5 iterations (3) (d) 10 iterations (0) Figure 6: Real Minecraft cave (Fig. 4, right) with 𝑛 = 67; white crosses signify light level below 𝐿min . Number of constraint violations in parentheses. The Qubo instances were solved using QA. 5. Related Work 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 (a) Heightmap (b) 2 iterations (23) (c) 5 iterations (14) (d) After 20 iterations (0) Figure 7: Real Minecraft cave (Fig. 4, left) with 𝑛 = 195; white crosses signify light level below 𝐿min . Number of constraint violations in parentheses. The Qubo instances were solved with TabuSA. (a) Heightmap (b) 2 iterations (128) (c) 10 iterations (3) (d) 20 iterations (0) Figure 8: Generated Minecraft cave with 𝑛 = 168; white crosses signify light level below 𝐿min . Number of constraint violations in parentheses. (a) Heightmap (b) 2 iterations (122) (c) 10 iterations (8) (d) 20 iterations (0) Figure 9: Generated Minecraft cave with 𝑛 = 169; white crosses signify light level below 𝐿min . Number of constraint violations in parentheses. 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. 6. Conclusion 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 (a) Heightmap (b) 2 iterations (243) (c) 10 iterations (16) (d) 30 iterations (0) Figure 10: Generated Minecraft cave with 𝑛 = 711; white crosses signify light level below 𝐿min . Number of constraint violations in parentheses. (a) Heightmap (b) 2 iterations (243) (c) 10 iterations (16) (d) 30 iterations (0) Figure 11: Generated Minecraft cave with 𝑛 = 708; white crosses signify light level below 𝐿min . Number of constraint violations in parentheses. 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. Acknowledgments This research has been funded by the Federal Ministry of Education and Research of Germany and the state of North Rhine-Westphalia as part of the Lamarr Institute for Machine Learning and Artificial Intelligence. References [1] R. Kaye, Minesweeper is NP-complete, Mathematical Intelligencer 22 (2000) 9–15. [2] S. Nebel, S. Schneider, G. D. Rey, Mining learning and crafting scientific experiments: A literature review on the use of minecraft in education and research, Journal of Educational Technology & Society 19 (2016) 355–366. [3] T. Kadowaki, H. Nishimori, Quantum annealing in the transverse Ising model, Physical Review E 58 (1998) 5355. [4] E. Farhi, J. Goldstone, S. Gutmann, M. Sipser, Quantum computation by adiabatic evolution, arXiv preprint quant-ph/0001106 (2000). arXiv:quant-ph/0001106. [5] DJ. Laughhunn, Quadratic binary programming with application to capital-budgeting problems, Operations research 18 (1970) 454–461. [6] P. L. Hammer, E. Shlifer, Applications of pseudo-Boolean methods to economic problems, Theory and decision 1 (1971) 296–308. [7] D. Biesner, T. Gerlach, C. Bauckhage, B. Kliem, R. Sifa, Solving subset sum problems using quantum inspired optimization algorithms with applications in auditing and financial data analysis, in: 2022 21st IEEE International Conference on Machine Learning and Applications (ICMLA), IEEE, 2022, pp. 903–908. [8] G. Kochenberger, F. Glover, B. Alidaee, K. Lewis, Using the unconstrained quadratic program to model and solve Max 2-SAT problems, International Journal of Operational Research 1 (2005) 89–100. [9] F. Neukart, G. Compostella, C. Seidel, D. von Dollen, S. Yarkoni, B. Parney, Traffic Flow Optimization Using a Quantum Annealer, Frontiers in ICT 4 (2017). [10] T. Stollenwerk, E. Lobe, M. Jung, Flight Gate Assignment with a Quantum An- nealer, in: Quantum Technology and Optimization Problems, Lecture Notes in Computer Science, Springer International Publishing, 2019, pp. 99–110. doi:10.1007/ 978-3-030-14082-3\_9. [11] C. Bauckhage, C. Ojeda, R. Sifa, S. Wrobel, Adiabatic quantum computing for kernel k= 2 means clustering., in: LWDA, 2018, pp. 21–32. [12] S. Mücke, N. Piatkowski, K. Morik, Learning Bit by Bit: Extracting the Essence of Machine Learning, in: Proceedings of the Conference on "Lernen, Wissen, Daten, Analysen" (LWDA), volume 2454 of CEUR Workshop Proceedings, 2019, pp. 144–155. [13] P. Date, D. Arthur, L. Pusey-Nazzaro, QUBO Formulations for Training Machine Learning Models, arXiv:2008.02369 (2020). [14] S. Mücke, R. Heese, S. Müller, M. Wolter, N. Piatkowski, Feature selection on quantum com- puters, Quantum Machine Intelligence 5 (2023). doi:10.1007/s42484-023-00099-z. [15] N. Piatkowski, T. Gerlach, R. Hugues, R. Sifa, C. Bauckhage, F. Barbaresco, Towards bundle adjustment for satellite imaging via quantum machine learning, in: 2022 25th International Conference on Information Fusion (FUSION), IEEE, 2022, pp. 1–8. [16] C. Bauckhage, N. Piatkowski, R. Sifa, D. Hecker, S. Wrobel, A qubo formulation of the k-medoids problem., in: LWDA, 2019, pp. 54–63. [17] K. Yonaga, M. J. Miyama, M. Ohzeki, Solving inequality-constrained binary optimization problems on quantum annealer, arXiv preprint arXiv:2012.06119 (2020). [18] T. Vyskočil, S. Pakin, H. N. Djidjev, Embedding inequality constraints for quantum annealing optimization, in: Quantum Technology and Optimization Problems: First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings 1, Springer, 2019, pp. 11–22. [19] J. Preskill, Quantum computing in the nisq era and beyond, Quantum 2 (2018) 79. [20] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, et al., Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends® in Machine learning 3 (2011) 1–122. [21] M. J. Powell, A method for nonlinear constraints in minimization problems, Optimization (1969) 283–298. [22] D. Gabay, B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers & mathematics with applications 2 (1976) 17–40. [23] K. Perlin, An image synthesizer, ACM Siggraph Computer Graphics 19 (1985) 287–296. [24] S. Mücke, T. Gerlach, N. Piatkowski, Optimum-preserving QUBO parameter compression, arXiv preprint arXiv:2307.02195 (2023). [25] G. Kendall, A. Parkes, K. Spoerer, A Survey of NP-Complete Puzzles, ICGA Journal 31 (2008) 13–34. doi:10.3233/ICG-2008-31103. [26] L. Gualà, S. Leucci, E. Natale, Bejeweled, Candy Crush and other match-three games are (NP-)hard, in: 2014 IEEE Conference on Computational Intelligence and Games, 2014, pp. 1–8. doi:10.1109/CIG.2014.6932866. [27] A. Lucas, Ising formulations of many NP problems, Frontiers in Physics 2 (2014). doi:10. 3389/fphy.2014.00005. [28] H. N. Djidjev, Quantum annealing with inequality constraints: The set cover problem, 2023.