A quantum search algorithm of twodimensional convex hull

Cheng Wang and Ri-Gui Zhou

1 College of Information Engineering，Shanghai Maritime University，Shanghai，201306，China

2 Research Center of Intelligent Information Processing and Quantum Intelligent Computing，Shanghai，201306，China

Abstract Despite the rapid development of quantum research in recent years，there is very little research in computational geometry.In this paper，to achieve the convex hull of a point set in a quantum system，a quantum convex hull algorithm based on the quantum maximum or minimum searching algorithm(QUSSMA)is proposed.Firstly，the novel enhanced quantum representation of digital images is employed to represent a group of point set，and then the QUSSMA algorithm and vector operation are used to search the convex hull of the point set.In addition，the algorithm is simulated and compared with the classical algorithm.It is concluded that the quantum algorithm accelerates the classical algorithm when the Mp value of the convex hull point is under a certain condition.

Keywords: quantum algorithm，convex hull，computational geometry，quantum searching

1.Introduction

In 1982，Feynman proposed the first new computational model，named quantum computer[1].With the continuous development of quantum computers，many scholars have proposed many algorithms，among which Deutsch’s quantum [2]，Shor algorithm[3]and Grover algorithm[4]are especially researched and applied by scholars.In recent decades，the development of quantum computing has been very rapid.Scholars from all walks of life have transplanted classical problem methods to quantum mechanics，such as quantum images，quantum machine learning，etc.For example，quantum images are currently a relatively active field in quantum computing and quantum information processing.Its concept was first proposed by Russian scholar Vlasov in 1997 [5].After more than 20 years of development，quantum image processing has made great progress in quantum image representation [6–8]，quantum image morphology operations[9，10]，quantum image scaling[11–13]，etc.In terms of quantum machine learning，Harrow proposed the HHL algorithm [14] in 2009，and Rebentrost proposed the quantum support vector machine QSVM algorithm [15].Based on the HHL algorithm model to achieve the exponential acceleration of the classic algorithm under certain conditions，the quantum principal component analysis QPCA algorithm proposed by Lloyd et al in 2014[16].After that，quantum machine learning ushered in a research boom，with various algorithms emerging in an endless stream，various classifications，regression[17，18]，clustering，neural networks [19]，deep learning，reinforcement learning，and recommendation systems applied to quantum versions，etc.

However，there are very few quantum studies in computational geometry.The term‘computational geometry’was used in different academic fields in the 1970s，such as pattern recognition，free-form curve and surface design，and algorithm design and analysis of discrete geometric problems.After more than 30 years of rapid development，its research content has continued to expand，involving convex hulls，Voronoi，triangulation，polygon subdivision，set search，intersection，visibility calculation，path planning，collision detection and many other contents.In 2010，MARCO and JEFFREY proposed a paper on quantum computational geometry，which put forward a general optical quantum multi-object search algorithm [20] based on Grover algorithm.The algorithm can achieve very good results in the face of solutions with multiple problems and further elaborates the application of the algorithm in computational geometry.In the meantime，it has inspired the future research on the geometry of quantum computing.

In this paper，we study the two-dimensional convex hull problem in computational geometry and explore how to implement the quantum convex hull algorithm(QCHA)in thecase of quantum mechanics.Section 2 briefly introduces the related works，including definition of two-dimensional convex hull，classical convex hull algorithm and quantum maximum or minimum searching algorithm (QUSSMA).The process of QCHA is presented in section 3.The analysis of the complexity of the algorithm and the comparison with the complexity of the classic algorithm are in section 4.The conclusions are drawn in section 5.The concrete notations used hereafter are shown in table 1.

Table 1.The definitions of variables.

2.Related works

2.1.Definition of convex hull and classic algorithm

Convex hull is one of the important objects of computational geometry research，and it is also a very common geometric structure.For example，we can use the convex hullsandof two objectsO1andO2，and then determine whetherO1andO2collide by whether the convex hulls ?1and ?2intersect.Another example is when the shapes of objects are matched，the convex hulls can establish the convex defect tree of the object，and then use the convex defect tree to analyze the similarity of the two objects [21].

Before understanding convex hull，it is important to know what a convex polygon is.From an intuitive point of view，a convex polygon is a polygon without any depression.The regular triangles，regular quadrilaterals，regular pentagons，etc，are all convex polygons.The convex hull of a set of points is the union of all possible convex combinations of all points in the set.In order to better understand the meaning of convex hull，the 2D convex hull is defined from different aspects:

(i) The convex hull of the point set S in the n-dimensional space is the union of the convex combination of alln+1 points in the point set S.For example，in a twodimensional space，the convex hull of a point set S is the union of all triangles covered by any three vertices in S.

(ii) The convex hull of the point set S is the intersection of all convex sets containing S.

(iii) The convex hull of the point set S is the intersection of all half spaces containing S.

(iv) The convex hull of a point set S containing a finite number of points on the plane is the smallest convex polygon P containing S.The smallest meaning is that there is no polygon P′，makingP?P′ ?S.

(v) The convex hull of a point set S containing a finite number of points on the plane is a convex polygon with the smallest area on the plane containing these points.

(vi) The convex hull of a point set S containing a finite number of points on the plane is a convex polygon with the smallest perimeter surrounding these points on the plane.

In the two-dimensional Euclidean space，the convex hull can be imagined as a rubber ring just wrapped.At present，the classical convex hull algorithm has experienced decades of development.The first algorithm proposed is the extreme edge method.，which has three levels of loop nesting，and the complexity of each level of loop isO(n) ，so that the total time complexity reachesO(n)3.In order to further improve the efficiency of the algorithm，Chand and Kapur proposed the gift-wrapping algorithm in 1970[22].The principle of the algorithm is just as easy to understand as its name.First，find an extreme pointP，1and rotate the horizontal lineL1through the extreme pointP1anticlockwise.In the process of rotation，the point with the minimum rotation angle θ on the lineL1is the next convex hull pointP2.Then，takeP1andP2as a new line for the next round of rotation，and find the next convex hull pointP3according to the previous provisions.The schematic diagram is shown in figure 1.

Figure 1.Gift wrapping algorithm.

After that，the same operation is used for subsequent operations，and finally the convex hull is obtained.Compared with the previous three-layer loop nesting method，the time complexity of the gift-wrapping method has been greatly improved.Its time complexity isO(nh) ，and h is the number of edges of the convex hull.When the worst case is infinite number of convex hull edges，the time complexity of the algorithm isO(n)2.Subsequently，an algorithm independently proposed by several scholars in the late 1970s was called Quick Hull[23]by Preparata and Shamos because it was very similar to the quick sort algorithm.The core idea of the algorithm is to only focus on the points near the convex hull，and gradually discard the points inside the convex hull.Figure 2 shows this algorithm that first takes two pointsP3andP4at the bottom left and top right.The connectionL2composed ofP3andP4can combine the entire convex hull.It is divided into upper convex hull and lower convex hull，and the upper and lower convex hulls can be obtained by the convex hull recursive process of the next level.

Figure 2.Quick sort algorithm.

The last classic convex hull algorithm was proposed by Graham in 1972 [24] and was shown in figure 3.The basic idea of the algorithm is to assume that a pointOis found inside the convex hull.Let theOpoint be the center point of polar coordinates.Then connect each point in the point set toO，calculate the polar angleθof the point，and then sort these points in order of angle from small to large.Afterwards，starting from an extreme pointPias the initial point，the adjacent pointsPi+1andPi+2can be connected in turn to obtain the convex hull.Other algorithms have been proposed in the following years，(e.g.divide-and-conquer，incremental algorithms) but the lower limit of their time complexity is stillO(nlog2n).

2.2.Quantum maximum or minimum searching algorithm

Among quantum algorithms，there are many articles about search algorithm.The beginning of quantum search algorithm is Grover search algorithm [25]proposed by Grover in 1996，and then scholars have explored the improvement and modification of Grover search algorithm.Eli Biham team proposed an improved version of Grover algorithm with arbitrary initial state amplitude [26]，The arbitrary phase rotation and phase matching proposed by Long’s group extends the original Grover operator to the search algorithm with 100%success rate [27–29].Durr and Hoyer proposed a quantum algorithm DHA [30]，which is used to search for the minimum value.However，with the increase of the number of iterations，the accuracy rate of DHA algorithm drops exponentially，and the lower limit of accuracy rate can only reach 1/2，and the initial copies needed by DHA algorithm need(log2N)2.According to the above defects of DHA，in 2020，Chen’s group proposed a quantum algorithm QUMMSA[31]to search the maximum and minimum value with low failure rate，and the improved Grover algorithm proposed by Long’s group is used in this paper.Let us review the QUMMSA algorithm below:

Step 1:Randomly choose a data value from D as the reference valued.0

Step 2:Map D to the initial state∣ψ〉.

Step 3:Exploit quantum searching algorithm and obtain its resultd，1a data value of D.

Step 4:Ifd1≤d0，quantum searching algorithm is performed successfully，then updated0withd1as a new reference value.Otherwise，repeat steps 2–3.

Step 5:Repeat steps 2–4.

The quantum search algorithm used in the third step of the above steps is the Grover–Long algorithm.The advantage of the Grover–Long algorithm is that it can perform phase flip at any angle，and the deflection angle can be obtained according to the relationship between the database size and the mark solution.As shown in equation(1)，Φ represents the required deflection angle，sinM represents the number of solutions，N represents the size of the database，and J represents the number of loops performed.So，knowing the above parameters，the deflection angleΦ is easy to obtain.When the exact value of the angle of each deflection is known，the final result will not be the same as the classic Grover algorithm，which will cause the accuracy decline due to the excessive deflection angle.

The algorithm also makes two optimizations: one is that in Grover–Long algorithm，the parameter of deflection angle is incorrect，which will cause failure rate.The most important thing to calculate the parameter is to know the database size N and the number M to be solved，which is often unknown in the actual operation.Therefore，in order to solve this problem，the sample estimation method is introduced to approximate the original parameters.The specific estimation method is given in Chen’s paper[31]，the following is a brief of this method.First，one parameter α is used to estimate M/N，it is easy to know the range of M/N is (0，1].However，sinced0varies with the number of main loops，M also correspondingly varies withd0，we should make α always close to M/N in all main loops of QUMMSA.The changing trend of M/N should be considered as a function.the probability of choosing a value x from the real database D is p(x)，as shown in formula (2).So when database size becomes infinity，the changing trend of M/N is the same as the real cumulative distribution function P(x) as show in formula (3).

The second optimization is when to end the loop.If you do not set a proper limit for jumping out of the loop，the redundancy of the main loop will affect the success rate of the search results.Because each solution is obtained with equal probability by Grover–Long algorithm，the number of solutions will be reduced by half on average，after one main loop.Therefore，the mathematical expectation of main loops to find the minimum islog2n，in theory.Regardinglog2nmain loops as the interrupt condition of QUMMSA is unreasonable，since it is difficult to know whether the final result is the minimum value or a minor value when the number of main loops reacheslog2n.Therefore，in order to minimize the number of main loops，we set it to break out of the loop whend1=d0for c (a constant) consecutive times.

3.Quantum convex hull algorithm (QCHA)

3.1.Quantum representation of point set

To deal with points by quantum mechanics，the information of point set should be stored in quantum state first.The preparation process for QCHA will be described as follow.

In view of the large number of point sets，it is impossible to use one single qubit to represent one single point，so the representation of quantum image is reasonable.The representation method used in this paper is novel enhanced quantum representation (NEQR) model [7].Equation (4)show the representation of a gray-scale image with size of 2G×2G.

where∣f(Y，X)〉 ∈ {0 ，1，...，2q-1} represents the gray value，and∣YX〉 represents the position information of the pixel.

For NEQR model，it is not need to know the gray value in QCHA algorithm，but only know whether there is a point at the current pixel position.Therefore，the NEQR model can be simplified，that is，∣f(Y，X)〉can be represented by only one qubit.When∣f(Y，X)〉 = ∣1〉 ，it indicates that there is a point in the current pixel position.If it is equal to∣0〉 ，it does not exist.The equation is as follows:

So，in this case just 1 +2Gqubits are used to represent a point set.TakingG= 1 as an example，a 2 × 2 point set image and its NEQR representation are show in figure 4.

Figure 4.A 2 × 2 point set image，and it’s NEQR representation，in which the white square represents a point.

In order to determine the size of G when the data size is N，since the size of NEQR model is2G×2G，we should let 2G×2Ggreater than N so that contain all points in one NEQR model.Therefore，it is calculated that G should be greater than

3.2.Design of QCHA

So far，the steps of representing a set of classical points with quantum information have been completed.In order to facilitate the subsequent operation，the first step is to find an extreme point in the point set.And according to the properties of extreme points，extreme points must be convex envelope points，that is，in two-dimensional space，they are usually the largest and smallest points on the X-axis or Y-axis coordinates.If there are points of the same size on the X-axis (Yaxis) coordinates，then the largest or smallest point on the Yaxis(X-axis)can be determined as extreme points.Therefore，it is necessary to use the maximum or minimum search algorithm to find the extreme point.Here，the QUSSMA algorithm described above can be used to search.The steps are as follows:

Step 1:Randomly select a point and record its X-axis coordinate asv0.

Step 2:Map the points in the point concentration to the initial state

Step 3:Use Grover–Long search algorithm to search，measure a piece of datav.1

Step 4:Ifv1＜v0，the retrieval is successful，thenv0=v1，otherwise repeat the second and third steps.

Step 5:Repeat steps 2–4 (loop log2n+ctimes then break).

Output:The pointp0that corresponds the minimum valuev0is the extreme point.

Note that extreme points are not unique.The above steps are to find the smallest extreme point.If you want to find the largest extreme point on the plane point set，then replace the judgment conditionv1＜v0withv1＞v0in the step 4.Since the extreme pointp0is obtained，it is easy to construct the solution to the subsequent convex hull points.At present，the work we have completed is to represent the classic point set with the NEQR model，and then use QUMMSA to find the extreme points.In the next step，assume that there is an operation C that can use the extreme pointp0as the base point to search the next convex hull point.When the next convex hull pointp1is found，then the line formed byp1and the base pointp0is one of the convex hull edges，and thenp1is used as the next base point to perform the C operation cycle.Finally，the entire convex hull can be found.The whole step can be as follows:

Step 1:Convert the scatter graph stored in classical information into a quantum state by NEQR model.

Step 2:Use the minimum search algorithm to find the pointp0with the smallest coordinate in the point set，that is，one of the points on the convex hull.

Step 3:Copyp0to k.

Step 4:Take pointp0as the input value to enter C for iteration operation，find the next pointp1of the convex hull edge and store it in the register，and judge whetherp1and k are the same point，if they are equal，jump out of the whole step，otherwise assignp1top0then continue the loop.

Step 5:Read the value in the register，and the edge composed of its sequence is the convex hull.

The QCHA is used to find the points on the edge of the convex hull，and every time a point is found，it will be stored in the classical register in order.The final order of these points is the result which is wanted.Note that the reason for judging whetherp1and k are the same in the step 4 is that the ending condition of the loop is the last found point should be the same as the initial extreme pointp0，so that forming a closed loop.Therefore，a judgment statement needs to be added in each loop to judge whether the point is the initial extreme point.

3.3.Design of operation C

The design of operation C is one of the key points of QCHA algorithm.The previous convex point can get the latter convex point through the iteration of C operation.The convex hull edge is a closed loop composed of convex hull points，which is solved through continuous loops.Finally，the last convex hull point is found which is the same as the first point，so that the order of their composition is the complete convex hull edge.The purpose of operation C is to find the relationship between the current input convex hull point and the next one.Here we find the angle relationship between the baseline where the current convex hull point is located (the baseline will be explained later) and the lines connecting the current convex hull point and other points to be searched.The line with the smallest angle formed with the baseline，then the point to be searched on this line is the next convex hull point.The relationship between the included angles can be expressed by vectors.The horizontal direction of the current point can be used as a basis vector(the baseline is the line where this vector is)，and the vector can be set asA=(1 ，0) .The vectors formed by the points to be searched and the current convex hull point can be a vector groupB={(x-X，y-Y)}(X，Y is the coordinate value of the point to be searched，and x，y is the value of the current convex hull point).After the vectorization process，the two vectors are calculated using equation (6) to obtaincosθ，and then the maximum value search algorithm is used to find the maximum value ofcosθ.The point of the vector corresponding to cosθis the wanted convex hull point

Note that in the second round of operation，the chosen basis vector is not the unit vector in the horizontal direction of the convex hull point in the first round，but the vector thatp0points top1.Because in this way，all the point sets will be on the side of the line where the vector is located.When performing the equation(4)，the angle range represented bycosθwill only be in the range of 0–π，so the largestcosθvalue can be found to represent the vector with the smallest angle to be correct.The selection of the basis vector for all subsequent rounds is the same as the second round.The selection of the basis vector for the ith round is to select the vector from the convex hull pointpi-1to the direction ofpias the baseline for operation.

4.Simulation and time complexity analysis

4.1.Simulation

Here，since physical quantum computers are not currently under our control，we perform simulations on classical computers.The realization of all quantum schemes in the simulation is designed by linear algebra of complex vectors.The unitary matrix is used as the unitary transformation，and MATLAB 9.8.0(r2020a)is used for calculation.We randomly selected 10 000 random points on the two-dimensional coordinates for the experiment.The final simulation effect is shown in the figure 5，where the red wire frame is convex hull.

Figure 5.The simulation of QCHA.

4.2.Time complexity analysis

The time complexity of QCHA consists of two parts:the time required to search for the first extreme point，and the time for subsequent convex hull point queries.The first extreme point mainly uses QUMMSA algorithm，whose time complexity R is by following equation

The time of convex point found by the subsequent QCHA algorithm can be determined by theO( 1) time required to construct vector group and need R time required to find the maximum cosine value through QUSSMA algorithm.

Therefore，the time complexity of the convex point isMpRwhen there areMpconvex points.After adding the complexity of the two parts，total complexity T as show in equation (7)

This time complexity is greatly improved compared to the lower limit of the classic algorithm.As shown in the figure 6，the time complexity of QCHA algorithm will change with the change ofMpvalue，and the time complexity of some positions is better than that of the optimal classical algorithm，as shown in figure 6(a).However，when the number of convex hull pointsMpis fixed and the total number of point set is very large，QCHA shows its great advantages，as shown in figure 6(b).

Figure 6.(a)The red line represents the change of +(l og2 N)2 )with Mp from with 0 to 100，blue line is Nlog 2 N.(b)M=100，The maximum number of database points is 10 000.

In order to know more accurately what the value ofMpis，the performance of QCHA is faster than the classical optimal algorithm，and the corresponding calculations are shown in equation (8)

5.Conclusion and discussion

In this paper，a search algorithm is proposed to solve convex hull in quantum state.Firstly，we use the modified NEQR model to express the classical point set information as quantum information.Secondly，the QUMMSA algorithm is used to solve the key extreme points.Finally，we design a C operation to solve the subsequent convex hull points.The performance of the algorithm is better than classical algorithm whenWe hope that our research can make contribution to the direction of quantum computational geometry and further break the speed limit in the classical world.Although our proposed algorithm can break through the lower limit of the classical algorithm in part，we still need to explore whether the speed of the algorithm can continue to be improved without restrictions.Next，our team will continue to explore.

Acknowledgments

This work is supported by the Shanghai Science and Technology Project in 2020 under Grant No.20040501500.

Conflict of interest

The authors declare that there is no conflict of interest.

Authors’ contributions

Cheng Wang and Ri-Gui Zhou conceived the theory and designed the algorithm.Cheng Wang wrote the paper and contributed algorithm analysis.