=Paper=
{{Paper
|id=Vol-3630/paper42
|storemode=property
|title=Efficient Light Source Placement using Quantum Computing
|pdfUrl=https://ceur-ws.org/Vol-3630/LWDA2023-paper42.pdf
|volume=Vol-3630
|authors=Sascha Mücke,Thore Gerlach
|dblpUrl=https://dblp.org/rec/conf/lwa/MuckeG23
}}
==Efficient Light Source Placement using Quantum Computing==
https://ceur-ws.org/Vol-3630/LWDA2023-paper42.pdf
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.