Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction

In classical computing, divide and conquer is an algorithm design pardigm that is usually described in terms of the following three steps:

1. 1.

   Divide: divide a problem into two or more subproblems.

2. 2.

   Conquer: solve the subproblems, typically using recursion.

3. 3.

   Combine: combine subproblem solutions into a solution to the original problem.

Perhaps because of the wide applicability of algorithm design paradigms, like divide and conquer, there is interest in adapting classical paradigms to the quantum setting. For example, Childs, Kothari, Kovacs-Deak, Sundaram, and Wang [9] describe an adaptation of the divide-and-conquer technique to quantum computing that in some cases results in query complexities better than what is possible classically. Likewise, Allcock, Bao, Belovs, Lee, and Santha [3] study the time complexity of a number of quantum divide-and-conquer algorithms, establishing conditions under which search and minimization problems with classical divide-and-conquer algorithms are amenable to quantum speedups. Akmal and Jin [2] adapt classical divide-and-conquer approaches for string problems to the quantum setting. There is also related work by many others; see, e.g., [4, 25, 37, 8, 6, 14, 35].

A well-known problem that can be solved classically using the divide-and-conquer paradigm is the convex hull problem; e.g., see Seidel [34]. In the two-dimensional version of this problem, one is given a set, $S$, of $n$ points in the plane and asked to output a representation of the smallest convex polygon that contains the points in $S$. (See Figure 1.)

Asymptotically fast classical convex hull algorithms are output sensitive, meaning that their running times depend on both the input size, $n$, and output size, $h$, and there are well-known examples that run in $O(n\log h)$ time; e.g., see Kirkpatrick and Seidel [22], Chan [7], and Afshani, Barbay, and Chan [1]. In this paper, we are interested in studying how to efficiently adapt classical output-sensitive divide-and-conquer algorithms, e.g., for convex hull and related problems, to quantum computing models.

We assume basic familiarity with quantum computing; see, e.g., Nielsen and Chuang [28]. A quantum state over $n$ qubits is a unit vector of length $2^n$ with complex entries. The computational basis ${\{|j⟩\}}_{j\in [0,\mathrm{\dots },2^n-1]}$ is a basis over quantum states where $|j⟩$ represents the unit vector of length $n$ with a 1 in the $j$-th index and 0 elsewhere. A computational basis state can be used as a classical bit string to simulate any classical algorithm. We can express any quantum state as a weighted sum of these classical basis states,

If at least two ${\alpha }_j$ in the above are nonzero, we say the state is in superposition. A measurement of the state $|\mathrm{\Psi }⟩$ will collapse the state to $|j⟩$ with probability ${|{\alpha }_j|}^2$. The measurement is destructive in the sense that once it is collapsed, there is no way to go back to $|\mathrm{\Psi }⟩$ without running the circuit to prepare that state. The state where all ${\alpha }_j=\frac{1}{\sqrt{2^n}}$ can be prepared by a circuit of depth 1.

We will assume an input model where the input data $[p_0,p_1,\mathrm{\dots },p_{n-1}]$ is accessible by a unitary $U_{in}$ that maps an index $i$ to the corresponding element in the array $p_i$. Since quantum operations must be reversible, it is standard to model the action of this unitary by using an index and data register as $|i⟩|0⟩\stackrel{U_{in}}{\to }|i⟩|p_i⟩$. We can use linearity to examine the action of this unitary to a state in superposition

from which the data point $p_j$ can be retrieved with probability ${|{\alpha }_j|}^2$ upon measurement of the index register. Therefore, in this model, we assume that a quantum state representing a distribution of our inputs is preparable in time proportional to the time it takes to prepare the distribution. A transformation from the $n$-bit zero string $|0^n⟩$ to a uniform superposition over all $n$-bit strings can be accomplished by a depth 1 circuit where a Hadamard gate is applied to each qubit in parallel.

Much of the existing literature on this subject assumes access to multiple copies of the state in (2). Our assumption of access to $U_{in}$ is at least as strong of an assumption as having multiple copies of the state. At the same time, it is a standard assumption for states in the form of (2) are generated using access to a unitary like $U_{in}$. We therefore compare the performance of our algorithm against the existing literature under equal access to $U_{in}$, and we summarize the performance of each in Table 1 under this model.

In this section, we present a quantum algorithm to solve the maxima set problem using the combine-and-conquer paradigm. In the maxima set problem, we are given a set, $S$, of $n$ points in the plane and are tasked with finding the subset of points in $S$ that are not dominated by any other points in $S$. We say that a point $p$ dominates a point $q$ if $p.x>q.x$ and $p.y>q.y$. Note that the output size, $h$, can be as small as $1$ or as large as $n$.

We assume that the input set is sorted in lexicographic order (first by $x$-coordinates and then by $y$-coodinates in the case of ties), as discussed in the introduction.

Let us begin by reviewing a simple divide-and-conquer algorithm in the classical computing model, which is provided the set, $S$, of $n$ points as input in sorted order, and returns the maxima set, $M$ (see Preparata and Shamos [30]). The algorithm splits $S$ into left and right sets, $S_1$ and $S_2$, and recursively finds the maxima sets of each. Then it prunes away each point in $S_1$ with smaller $y$-coordinate than the point, $p_{\max }$, in $S_2$ with maximum $y$-coordinate. The resulting maxima set algorithm, which we give in detail in an appendix, takes $\mathrm{\Theta }(n\log n)$ time, even when $S$ is sorted [30]. Kirkpatrick and Seidel [21] show that if the combine step of finding $p_{\max }$ is performed before the divide and conquer steps, and used to prune points in recursive subproblems, then the running time can be improved to $O(n\log h)$.

For our output-sensitive quantum algorithm, we also perform the combine step before the conquer step, but our goal is to design a quantum algorithm that runs in $\tilde{O}(\sqrt{nh})$ time without recursion, which requires a more sophisticated approach. We first describe an algorithm where the output size, $h$, is known in advance and later show how to use this algorithm to solve the case where the output size is not known.

At a high level, the combine-and-conquer approach performs the combine step first before conquering the subproblems. In the maxima set problem, this is achieved in the following way. We begin by dividing our set $S$ into $h$ different blocks using Algorithm 1. The key observation we use is that we can isolate the problem of finding the maxima set to each of the local blocks once we identify representative information from each block. This representative information is used globally, so we describe the process of finding such information as the combine step. The combine-and-conquer paradigm works for problems where, once the global information is identified, the blocks do not need to communicate with each other for the remainder of the algorithm. In the case of computing the maxima set, the combine step consists of searching for the set $T$ of the $h$ highest points in each block. Once the set $T$ is found, we classically compute the maxima set $M_T$ of $T$. Note that $M_T$ cannot contain more than $h$ points, and if a block does not share a point with $M_T$ no points in that block can be in the final output set. Once the points in $M_T$ are identified, we begin the conquer step of the algorithm to find the points in each block that appear in the maxima set. Block number $j$ uses information from two points identified in the combine step to restrict the search region. The first is the $y$ coordinate $T_j$ of the tallest point within the $j$-th block, which immediately removes all points to the left of it inside block $j$ out of the candidate set. The second is the $y$ coordinate $R_j$ of the highest point that appears in any of the blocks to the right of block $j$. Note that $R_j$ is left-most point from $M_T$ that is to the right of block $j$. See Figure 2.

Using $T_j$ and $R_j$, we can define a Boolean function $f$ that takes as input a point $p$ and returns 1 if $p$ is not dominated by either of $T_j$ and $R_j$. We then apply Theorem 1 to search for the maximum element in lexicographic order subject to this Boolean function. It turns out that this point is part of the final output set, as $R_j$ tells us it is not dominated by any point in blocks to the right of $j$ and $T_j$ tells us it is not dominated by any point in block $j$. We then update $R_j$ to equal this maximal point we found, and repeat this process in block $j$ until the Boolean function does not mark any elements in the set. We illustrate the first iteration of this process in Figure 3. Since the output size is $h$, it suffices to run this process $O(h)$ times in total across all blocks. Finally, we collect the outputs in the blocks that contain a point in $M_T$, which takes at most $O(h)$ time. See Algorithm 2.

Finally, the case where $h$ is unknown can be handled using an approach where we start with a small estimate of $h$, then repeat the procedure using $h=2h$ if we discover more than $h$ points. Thus, the running time forms a geometric sum that is $\tilde{O}(\sqrt{nh})$. See Algorithm 3.

In this section, we describe a quantum algorithm to construct the convex hull of $n$ points in the plane in $\tilde{O}(\sqrt{nh})$ time, where $h$ is the size of the output. Again, we assume that the input set is sorted in lexicographic order. We follow our combine-and-conquer paradigm, where we use some global properties that can be computed from our subsets to prune off points that do not appear in the output, then use these values to isolate the problem solving within each block. Here, however, the combine step is more complicated that simply finding a point, $p_{\max }$, with maximum $y$-coordinate.

We begin by reviewing a well-known classical divide-and-conquer algorithm for 2D convex hulls (see, e.g., [11, 33, 30, 29]). The convex hull $CH(S)$ of a set, $S$, of $n$ points in the plane can be described as a union of the polygonal chains that form the upper hull $UH(S)$ and lower hull $LH(S)$ of the points, where $UH(S)$ (resp., $LH(S)$) is the set of edges of $CH(S)$ with positive (negative) normals. For completeness, we provide a description of a classical divide-and-conquer algorithm for computing $UH(S)$ in appendix D, which divides $S$ into a left set, $S_1$, and right set, $S_2$, and recursively finds $UH(S_1)$ and $UH(S_2)$. Then it finds the tanget segment bridge between $UH(S_1)$ and $UH(S_2)$ and prunes away the points under the bridge, resulting in an algorithm running in $O(n\log n)$ time. By a well-known point-line duality, which we also review in an appendix, the bridge edge can be found by a solving a two-dimensional linear program; see, e.g., [11, 33, 29].

If we use linear-time 2D linear programming for the bridge-finding step, then the running time for this classical divide-and-conquer algorithm is $O(n\log n)$, even if the points are sorted by $x$-coordinate. Kirkpatrick and Seidel [22] show that this classical running time can be improved to $O(n\log h)$ by performing the bridge-finding step before the (recursive) conquer steps. Likewise, our quantum convex hull algorithm also performs this combine step before the conquer steps, but avoids recursion.

Before we give our algorithm, let us review another well-known classical algorithm for computing a two-dimensional convex hull – the Jarvis march algorithm; see, e.g., [11, 33, 30]. In this algorithm, we start with a point, $p$, known to be on the convex hull, such as a point with smallest $y$-coordinate. Then, we find the next point on the convex hull in a clockwise order, by a simple linear-time maximum-finding step. We iterate this search, winding around the convex hull, until we return to the starting point. Since each iteration takes $O(n)$ time, this algorithm runs in $O(nh)$ time. Lanzagorta and Uhlmann [24] describe a quantum assisted version of the Jarvis march algorithm that runs in $\tilde{O}(h\sqrt{n})$ time, which we review in an appendix.

Let $S$ be a set of $n$ points in the plane sorted lexicographically. For simplicity of expression, let us assume that the points have distinct $x$-coordinates and we are interested in computing the upper hull, $UH(S)$, of $S$. As in our maxima set algorithm, let us assume for now that we know the value of $h$, the number of points on the upper hull of $S$ to simplify the presentation. We divide $S$ into $h$ blocks, $S_0,S_1,\mathrm{\dots },S_{h-1}$, of size $O(n/h)$ each by vertical lines, $L_1,L_2,\mathrm{\dots },L_{h-1}$, arranged left-to-right. This is achieved by using Algorithm 1 to partition the input.

At a high level, our quantum combine-and-conquer upper hull algorithm first computes all the bridge edges that are intersected by one of the vertical lines, $L_i$. This amounts to the combine step of our quantum combine-and-conquer algorithm. Each of these bridge edges belong to the upper hull of $S$; hence, there are at most $h$ such bridges. Importantly, we show how to compute all these bridges in $\tilde{O}(\sqrt{nh})$ time. Each block of points, $S_j$, has $O(n/h)$ points, and, of course, there may be remaining upper hull points to compute for each such $S_j$ (between points of tangency for the bridges computed in the combine step). Note that the conquer step for block $S_j$ will return in $O(1)$ time if $S_j$ does not contain any endpoints of a bridge edge or if it contains a single point where two bridge edges meet. See Figure 5 showing the edges that come from the combine step and the edges that come from the conquer step.

To compute the remaining convex hull points, then, we perform a modified quantum Jarvis march for each subset, $S_j$, which runs in time $\tilde{O}(h_j\sqrt{n/h})$ time, where $h_j$ is the number of additional upper hull points found for $S_j$. Thus, the total time for this second (conquer) phase of our algorithm is

Given this overview, let us next describe how to perform the different steps of our algorithm, beginning with our quantum algorithm for finding all the bridge edges intersecting the vertical lines, $L_1,L_2,\mathrm{\dots },L_{h-1}$, which separate the subsets, $S_0,S_1,\mathrm{\dots },S_{h-1}$, of $S$. At a high level, our combine-step method can be viewed as a quantum adaptation of a classical algorithm by Goodrich [15] for computing the upper hull of a partially sorted set of points.

As mentioned above, by point-line duality, bridge finding is dual to two-dimensional linear programming. In more detail, let $S$ be a set of $n$ points in the plane, and $L$ be a vertical line in this plane. Let $S^{\prime }$ be the same set of points after shifting the plane horizontally so that $L$ is the $y$-axis. We define a dual plane by taking each point $p=(a,b)$ and mapping it to a line $y=ax-b$. A standard result in computational geometry is that the points in the upper hull of $S^{\prime }$ correspond to the lower envelope of the set of lines in the dual plane; see, e.g., [11, 33, 30]. Furthermore, by the duality transformation, the highest point in the lower envelope is the intersection of two lines in the envelope whose slopes transition from positive to negative. Mapping this point to the primal plane gives us the bridge edge we are looking for. Thus, we can reduce the problem of finding a bridge edge to the problem of finding the largest point in the intersection of $n$ lower-halfplanes. We also use the following lemma due to Sadakane et al. showing that the problem of computing the highest point in the intersection of $n$ halfplanes efficiently using a quantum algorithm.

The linear constraints in superposition refers to a state in the following form:

where $p_i$ are the coordinates of each of the $n$ points. By point-line duality, the coordinates fully describe the halfplanes in the dual plane.

The output element is a point in the dual plane, which maps back to a line in the primal plane. To determine which points this line intersects, we can run two iterations of minimum finding to find the points in $S$ that are on the resulting line by minimizing by the distance to the line. We combine the above two lemmas to a function with the signature,

and it returns the endpoints $p_s,p_f\in S$ of the bridge edge as a tuple. This process will also call $\text{qPrep}($i,h$)$ as needed.

We are now ready to describe the full algorithm. The first step will be to divide our input set into $h$ blocks, each containing $n/h$ points. We define a bridge edge to be an edge in the upper hull of $S$ whose endpoints are in two different blocks.

To find the bridge edges, we take inspiration from the classical Graham scan algorithm for computing the convex hull. We will be using the fact that if we traverse the convex hull in the clockwise direction, each edge makes a right turn from its previous edge. Since bridge edges are edges in the upper hull, this is true for them as well. We will compute bridge edges between consecutive pairs, but if at any point a left turn is formed between two bridge edges, we know that these edges will not be a part of the upper hull. Critically, this allows us to ignore an entire block of points, and move on to find the bridge edge between the remaining blocks. The details of the above approach are outlined in Algorithm 5.

Afshani, Peyman, and Chan [1] give an instance-optimal classical algorithm for finding 2D convex hulls, which adapts the algorithm by Kirkpatrick and Seidel [22] to run in $O(n(\mathscr{H}(S)+1))$ time, where $\mathscr{H}(S)$ is a classical-computing structural entropy measure that is never more than $O(\log h)$. An interesting direction for future work would be to determine if there is a quantum convex hull algorithm that is instance optimal based on a quantum structural entropy measure.