Cheng Wang^1,2, Ri-Gui Zhou^,1,21College of Information Engineering, Shanghai Maritime University, Shanghai, 201306, China
²Research Center of Intelligent Information Processing and Quantum Intelligent Computing, Shanghai, 201306, China

Received:2021-06-11Revised:2021-08-13Accepted:2021-08-16Online:2021-09-14


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 ${M}_{p}$ value of the convex hull point is under a certain condition.
Keywords： quantum algorithm;convex hull;computational geometry;quantum searching


PDF (1015KB)MetadataMetricsRelated articlesExportEndNote|Ris|BibtexFavorite
Cite this article
Cheng Wang, Ri-Gui Zhou. A quantum search algorithm of two-dimensional convex hull. Communications in Theoretical Physics, 2021, 73(11): 115102- doi:10.1088/1572-9494/ac1da0

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 the case 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.
Table 1.The definitions of variables.

Notations
Symbol	Definition
${\mathop{o}\limits^{\wedge }}_{1},{\mathop{o}\limits^{\wedge }}_{2}$	Convex hull
${O}_{1},{O}_{2}$	Object
$S$	Point set
$P,{P}^{{\prime} }$	Convex polygon
${P}_{1},{P}_{2},{P}_{3},{P}_{4},{P}_{i}$	Convex hull point
$N$	Data size
$M$	Solution number
$\tilde{N},\tilde{M}$	Sample data size and solutions
P(x),$\tilde{P}(x)$	Cumulative distribution function
ϵ	failure rate
${v}_{0},{v}_{1}$	Coordinate values
	Convex hull point
$k$	A copy to store convex hull point values
${M}_{p}$	The number of convex hull point

New window|CSV

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 hulls ${{\rm{\unicode{x000F4}}}}_{1}$ and ${\rm{\unicode{x000F4}}}{\,}_{2}$ of two objects ${O}_{1}$ and ${O}_{2},$ and then determine whether ${O}_{1}$ and ${O}_{2}$ collide by whether the convex hulls ${{\rm{\unicode{x000F4}}}}_{1}$ and ${\rm{\unicode{x000F4}}}{\,}_{2}$ intersect. 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 all $n+1$ points in the point set S. For example, in a two-dimensional 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′, making $P\supseteq P^{\prime} \supseteq 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 is $O\left(n\right),$ so that the total time complexity reaches $O\left({n}^{3}\right).$ 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 point ${P}_{1},$ and rotate the horizontal line ${L}_{1}$ through the extreme point ${P}_{1}$ anticlockwise. In the process of rotation, the point with the minimum rotation angle θ on the line ${L}_{1}$ is the next convex hull point ${P}_{2}.$ Then, take ${P}_{1}$ and ${P}_{2}$ as a new line for the next round of rotation, and find the next convex hull point ${P}_{3}$ according to the previous provisions. The schematic diagram is shown in figure 1.

Figure 1.

New window|Download| PPT slide
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 is $O\left(nh\right),$ 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 is$O\left({n}^{2}\right).$ 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 points ${P}_{3}$ and ${P}_{4}$ at the bottom left and top right. The connection ${L}_{2}$ composed of ${P}_{3}$ and ${P}_{4}$ can 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.

New window|Download| PPT slide
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 point $O$ is found inside the convex hull. Let the $O$ point be the center point of polar coordinates. Then connect each point in the point set to $O,$ calculate the polar angle $\theta $ of the point, and then sort these points in order of angle from small to large. Afterwards, starting from an extreme point ${P}_{i}$ as the initial point, the adjacent points ${P}_{i+1}$ and ${P}_{i+2}$ can 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 still $O\left(n{\mathrm{log}}_{2}n\right).$

Figure 3.

New window|Download| PPT slide
Figure 3.Graham algorithm.

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 ${\left({\mathrm{log}}_{2}N\right)}^{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 value ${d}_{0}.$

Step 2:Map D to the initial state $\left|\psi \right\rangle .$

Step 3:Exploit quantum searching algorithm and obtain its result ${d}_{1},$ a data value of D.

Step 4:If ${d}_{1}\leqslant {d}_{0},$ quantum searching algorithm is performed successfully, then update ${d}_{0}$ with ${d}_{1}$ as 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), ${\rm{\Phi }}$ represents the required deflection angle, $\sin \,\beta =\sqrt{\left(M/N\right)},$ M 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 ${\rm{\Phi }}$ 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.(1)$\begin{eqnarray}{\rm{\Phi }}=2\arcsin \left(\displaystyle \frac{\sin \,\displaystyle \frac{\pi }{4{\rm{J}}+2}}{\sin \,\beta }\right){\rm{.}}\end{eqnarray}$

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, since ${d}_{0}$ varies with the number of main loops, M also correspondingly varies with ${d}_{0},$ 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).(2)$\begin{eqnarray}p\left(x\right)=\left\{\begin{array}{cc}\displaystyle \frac{1}{N} & {\rm{in}}\,{\rm{the}}\,\mathrm{database},\\ 0 & {\rm{not}}\,{\rm{in}}\,{\rm{the}}\,{\rm{database}}{\rm{.}}\end{array}\right.\end{eqnarray}$(3)$\begin{eqnarray}P\left(x\right)={\int }_{0}^{{d}_{0}}p\left(x\right){\rm{d}}x=\frac{M}{N},\end{eqnarray}$we randomly extract a small amount of data from the real database D as a sampling database $\tilde{D}.$ We also define $\tilde{M}$ is the number of solutions that are less than or equal to ${d}_{0}$ in the sampling database and $\tilde{N}$ is the sampling database size. We want to establish the relationship between the real database and the sampled database. through an intermediate parameter α. Namely, $\tilde{M}/\tilde{N}=\alpha =M/N,$ ideally. Similar to the real cumulative distribution function P(x), we can obtain the sampling cumulative distribution function $\tilde{P}(x).$ Next, they use the sample statistics theory to determine the minimum sampling database size $\tilde{N}\,{\rm{\min }}.$ Finally, because of the different minimum sampling database sizes $\tilde{N}\,{\rm{\min }},$ P(x) and $\tilde{P}(x)$ reflect different degrees of similarity. Namely $\tilde{M}/\tilde{N}\approx M/N.$ The analysis of the failure rate ϵ is mentioned in the Chen's paper, he lists some common minimum sampling sizes, the minimum sampling database size is easy to meet the $\tilde{M}/\tilde{N}\approx M/N.$ Therefore, through sampling estimation, we can efficiently reduce the failure rate of Grover–Long algorithm caused by parameters of Grover–Long algorithm.

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 is ${\mathrm{log}}_{2}n,$in theory. Regarding ${\mathrm{log}}_{2}n$ main 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 reaches ${\mathrm{log}}_{2}n.$ Therefore, in order to minimize the number of main loops, we set it to break out of the loop when ${d}_{1}={d}_{0}$ for 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 ${2}^{G}\times {2}^{G}.$(4)$\begin{eqnarray}\begin{array}{l}\left|I\right\rangle =\displaystyle \frac{1}{{2}^{G}}\displaystyle {\sum }_{Y=0}^{{2}^{G}}\displaystyle {\sum }_{X=0}^{{2}^{G}-1}\left|f\left(Y,X\right)\right\rangle \left|YX\right\rangle \\ \,\,=\,\displaystyle \frac{1}{{2}^{G}}\displaystyle {\sum }_{Y=0}^{{2}^{\left(G-1\right)}}\displaystyle {\sum }_{X=0\,i=0}^{{2}^{G}-1\,q-1}\otimes \left|{C}_{YX}^{i}\right\rangle \left|YX\right\rangle ,\end{array}\end{eqnarray}$where $\left|f\left(Y,X\right)\right\rangle \in \left\{0,1,\mathrm{...},{2}^{q}-1\right\}$ represents the gray value, and $| \left.YX\right\rangle $ 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, $\left|f\left(Y,X\right)\right\rangle $ can be represented by only one qubit. When $\left|f\left(Y,X\right)\right\rangle =\left|1\right\rangle ,$ it indicates that there is a point in the current pixel position. If it is equal to $\left|0\right\rangle ,$ it does not exist. The equation is as follows:(5)$\begin{eqnarray}\left|I\right\rangle =\displaystyle \frac{1}{{2}^{G}}\displaystyle {\sum }_{Y=0}^{{2}^{G}}\displaystyle {\sum }_{X=0}^{{2}^{G}-1}\left|f\left(Y,X\right)\right\rangle \left|YX\right\rangle \,,\,f\left(Y,X\right)=\left\{0,1\right\}{\rm{.}}\end{eqnarray}$

So, in this case just $1+2G$ qubits are used to represent a point set. Taking $G=1$ as an example, a 2×2 point set image and its NEQR representation are show in figure 4.

Figure 4.

New window|Download| PPT slide
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 is${2}^{G}\times {2}^{G},$ we should let ${2}^{G}\times {2}^{G}$ greater than N so that contain all points in one NEQR model. Therefore, it is calculated that G should be greater than $\displaystyle \frac{{\mathrm{log}}_{2}N}{2}.$

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 (Y-axis) coordinates, then the largest or smallest point on the Y-axis (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 as ${v}_{0}.$

Step 2:Map the points in the point concentration to the initial state $\left|I\right\rangle =\displaystyle \frac{1}{{2}^{G}}\displaystyle {\sum }_{Y=0}^{{2}^{G}}\displaystyle {\sum }_{X=0}^{{2}^{G}-1}\left|1\right\rangle \left|\left.YX\right\rangle \,\right..$

Step 3:Use Grover–Long search algorithm to search, measure a piece of data ${v}_{1}.$

Step 4:If ${v}_{1}$<${v}_{0},$ the retrieval is successful, then ${v}_{0}$ = ${v}_{1},$ otherwise repeat the second and third steps.

Step 5:Repeat steps 2–4 (loop ${\mathrm{log}}_{2}n+c$ times then break).

Output:The point ${p}_{0}$ that corresponds the minimum value ${v}_{0}$ is 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 condition ${v}_{1}$ < ${v}_{0}$ with ${v}_{1}$ > ${v}_{0}$ in the step 4. Since the extreme point ${p}_{0}$ is 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 point ${p}_{0}$ as the base point to search the next convex hull point. When the next convex hull point ${p}_{1}$ is found, then the line formed by ${p}_{1}$ and the base point ${p}_{0}$ is one of the convex hull edges, and then ${p}_{1}$ is 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 point ${p}_{0}$ with the smallest coordinate in the point set, that is, one of the points on the convex hull.

Step 3:Copy ${p}_{0}$ to k.

Step 4:Take point ${p}_{0}$ as the input value to enter C for iteration operation, find the next point ${p}_{1}$ of the convex hull edge and store it in the register, and judge whether ${p}_{1}$ and k are the same point, if they are equal, jump out of the whole step, otherwise assign ${p}_{1}$ to ${p}_{0}$ then 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 whether ${p}_{1}$ and 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 point ${p}_{0},$ 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 as $A=\left(1,0\right).$ The vectors formed by the points to be searched and the current convex hull point can be a vector group $B\,=\left\{\left(x-X,y-Y\right)\right\}$ (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 obtain $\cos \,\theta ,$ and then the maximum value search algorithm is used to find the maximum value of $\cos \,\theta .$ The point of the vector corresponding to $\cos \,\theta $ is the wanted convex hull point(6)$\begin{eqnarray}\cos \,\theta =\displaystyle \frac{A\cdot B}{| | {\rm{A}}| | | B| | }{\rm{.}}\end{eqnarray}$

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 that ${p}_{0}$ points to ${p}_{1}.$ 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 by $\cos \,\theta $ will only be in the range of 0–π, so the largest $\cos \,\theta $ 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 point ${p}_{i-1}$ to the direction of ${p}_{i}$ as 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.

New window|Download| PPT slide
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(7)$\begin{eqnarray}R=\displaystyle \frac{\displaystyle \frac{\pi }{2}\left(2+\sqrt{2}+c\right)\sqrt{N}+\left({\mathrm{log}}_{2}N+c\right){\mathrm{log}}_{2}N}{1-\varepsilon }{\rm{.}}\end{eqnarray}$The time of convex point found by the subsequent QCHA algorithm can be determined by the $O(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 is ${M}_{p}R$ when there are ${M}_{p}$ convex points. After adding the complexity of the two parts, total complexity T as show in equation (7)(7a)$\begin{eqnarray}\begin{array}{lll}O\left(T\right) & = & O\left(R\right)+O\left({M}_{p}O\left(1\right)\right)+O\left({M}_{P}R\right)\\ & = & O\left({M}_{p}\left(\sqrt{N}+{\left({\mathrm{log}}_{2}N\right)}^{2}\right)\right).\end{array}\end{eqnarray}$

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 of ${M}_{p}$ value, 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 points ${M}_{p}$ is fixed and the total number of point set is very large, QCHA shows its great advantages, as shown in figure 6(b).

Figure 6.

New window|Download| PPT slide
Figure 6.(a) The red line represents the change of ${M}_{p}\left(\sqrt{N}+{({\mathrm{log}}_{2}N)}^{2}\right)$ with ${M}_{p}$ from with 0 to 100, blue line is $N{\mathrm{log}}_{2}N.$ (b) M = 100, The maximum number of database points is 10 000.


In order to know more accurately what the value of ${M}_{p}$ is, the performance of QCHA is faster than the classical optimal algorithm, and the corresponding calculations are shown in equation (8)(8)$\begin{eqnarray}\begin{array}{lll}{M}_{p}\left(\sqrt{N}+{\left({\mathrm{log}}_{2}N\right)}^{2}\right) & = & N{\mathrm{log}}_{2}N\to \\ \,{M}_{p} & = & \displaystyle \frac{N{\mathrm{log}}_{2}N}{\sqrt{N}+{\left({\mathrm{log}}_{2}N\right)}^{2}},\end{array}\end{eqnarray}$${M}_{p}=\tfrac{N{\mathrm{log}}_{2}N}{\sqrt{N}+{\left({\mathrm{log}}_{2}N\right)}^{2}}$ is the critical value. Therefore, when ${M}_{p}\lt \tfrac{N{\mathrm{log}}_{2}N}{\sqrt{N}+{\left({\mathrm{log}}_{2}N\right)}^{2}},$ the time effect of QCHA performance is certainly stronger than the classical algorithm.

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 when ${M}_{p}\lt \tfrac{N{\mathrm{log}}_{2}N}{\sqrt{N}+{\left({\mathrm{log}}_{2}N\right)}^{2}}.$ We 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.

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.

Acknowledgments

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

Reference View Option By original order
By published year
By cited within times
By Impact factor

[1]Feynman R P 1982 Simulating physics with computers
Int. J. Theor. Phys. 21 467 488
DOI:10.1007/BF02650179 [Cited within: 1]

[2]Deutsch D 1985 Quantum theory, the church-turing principle and the universal quantum computer
Proc. R. Soc. A 400 97 117
DOI:10.1098/rspa.1985.0070 [Cited within: 1]

[3]Shor P 1994 Algorithms for quantum computation: discrete logarithms and factoring
Proc. of the 35th Annual Symp. on Foundations of Computer Science 124 134
DOI:10.1109/SFCS.1994.365700 [Cited within: 1]

[4]Grover L 1996 A fast quantum mechanical algorithm for database search
Proc. of the 28th Annual ACM Symp. on Theory of Computing 212 219https://arxiv.org/abs/quant-ph/9605043
[Cited within: 1]

[5]Vlasov A Y 1997 Quantum computations and images recognition
arXiv e-printsquant-ph/9703010
[Cited within: 1]

[6]Le P Dong F Hirota K 2011 A flexible representation of quantum images for polynomial preparation, image compression, and processing operations
Quantum Inf. Process. 10 63 84
DOI:10.1007/s11128-010-0177-y [Cited within: 1]

[7]Zhang Y Lu K Gao Y Mao W 2013 NEQR: a novel enhanced quantum representation of digital images
Quantum Inf. Process. 12 2833 2860
DOI:10.1007/s11128-013-0567-z [Cited within: 1]

[8]Sang J Wang S Li Q 2017 A novel quantum representation of color digital images
Quantum Inf. Process. 16 42
DOI:10.1007/s11128-016-1463-0 [Cited within: 1]

[9]Yuan S Z et al. 2016 Improved quantum dilation and erosion operations
Int. J. Quantum Inf. 14 1650036
DOI:10.1142/S0219749916500362 [Cited within: 1]

[10]Li P Shi T Lu A et al. 2019 Quantum circuit design for several morphological image processing methods
Quantum Inf. Process. 18 364
DOI:10.1007/s11128-019-2479-z [Cited within: 1]

[11]Jiang N Wang L 2015 Quantum image scaling using nearest neighbor interpolation
Quantum Inf. Process. 14 1559 1571
DOI:10.1007/s11128-014-0841-8 [Cited within: 1]

[12]Zhou R G Liu X A Luo J 2017 Quantum circuit realization of the bilinear interpolation method for GQIR
Int. J. Theor. Phys. 56 2966 2980
DOI:10.1007/s10773-017-3463-y

[13]Zhou R G Cheng Y Qi X Yu H Jiang N 2020 Asymmetric scaling scheme over the two dimensions of a quantum image
Quantum Inf. Process. 19 1 20
DOI:10.1007/s11128-020-02837-9 [Cited within: 1]

[14]Harrow A W Hassidim A Lloyd S 2009 Quantum algorithm for linear systems of equations
Phys. Rev. Lett. 103 150502
DOI:10.1103/PhysRevLett.103.150502 [Cited within: 1]

[15]Rebentrost P Mohseni M Lloyd S 2014 Quantum support vector machine for big data classification
Phys. Rev. Lett. 113 130503
DOI:10.1103/PhysRevLett.113.130503 [Cited within: 1]

[16]Lloyd S Mohseni M Rebentrost P 2014 Quantum principal component analysis
Nat. Phys. 10 631 633
DOI:10.1038/nphys3029 [Cited within: 1]

[17]Chao-Hua Y Gao F Qiao-Yan W 2017 An improved quantum algorithm for ridge regression
arXiv:1707.09524
[Cited within: 1]

[18]Schuld M Sinayskiy I Petruccione F 2016 Prediction by linear regression on a quantum computer
Phys. Rev. A 94 022342
DOI:10.1103/PhysRevA.94.022342 [Cited within: 1]

[19]Li Y Zhou R G Xu R Luo J Hu W 2020 A quantum deep convolutional neural network for image recognition
Quantum Sci. Technol. 5
DOI:10.1088/2058-9565/ab9f93 [Cited within: 1]

[20]Lanzagorta M Uhlmann J 2010 Quantum algorithmic methods for computational geometry
Math.Struct.Comput.Sci. 20 1117 1125
DOI:10.1017/S0960129510000411 [Cited within: 1]

[21]Zhang D Lu G 2004 Review of shape representation and description techniques
Pattern Recognit. 37 1 19
DOI:10.1016/j.patcog.2003.07.008 [Cited within: 1]

[22]Chand D R Kapur S S 1970 An algorithm for convex polytopes
J. ACM 17 78 86
DOI:10.1145/321556.321564 [Cited within: 1]

[23]Preparata F P Shamos M I 1985 Computational Geometry: An Introduction Berlin Springer
[Cited within: 1]

[24]Graham R L 1972 An efficient algorithm for determining the convex hill of a finite planar set
Inform. Process. Lett. 1 132 133
DOI:10.1016/0020-0190(72)90045-2 [Cited within: 1]

[25]Grover L K 1996 A fast quantum mechanical algorithm for database search
Proc. of the Annual ACM Symp. on Theory of Computinghttps://arxiv.org/abs/quant-ph/9605043
[Cited within: 1]

[26]Biham E Biham O Biron D Grassl M Lidar D A 1999 Grover's quantum search algorithm for an arbitrary initial amplitude distribution
Phys. Rev. A 60 2742
DOI:10.1103/PhysRevA.60.2742 [Cited within: 1]

[27]GuiLu L WeiLin Z YanSong L Li N 1999 Arbitrary phase rotation of the marked state cannot be used for grover's quantum search algorithm
Commun. Theor. Phys. 32 335
DOI:10.1088/0253-6102/32/3/335 [Cited within: 1]

[28]Long G L Li X Sun Y 2002 Phase matching condition for quantum search with a generalized initial state
Phys. Lett. A 294 143 152
DOI:10.1016/S0375-9601(02)00055-5

[29]Long G L 2001 Grover algorithm with zero theoretical failure rate
Phys. Rev. A 64 022307
DOI:10.1103/PhysRevA.64.022307 [Cited within: 1]

[30]Durr C Hoyer P 1996A Quantum algorithm for finding the minimum pp 1–2 quant-ph/9607014
[Cited within: 1]

[31]Chen Y Wei S Gao X Wang C Tang Y Wu J Guo H 2020 A low failure rate quantum algorithm for searching maximum or minimum
Quantum Inf. Process. 19 1 28
DOI:10.1007/s11128-020-02773-8 [Cited within: 2]