Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Communications in Theoretical Physics

A quantum search algorithm of two-dimensional convex hull

Cheng Wang, Ri‐Gui Zhou

Published Aug 16, 2021• 5 citations
Publisher

Abstract

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.

DOI
10.1088/1572-9494/ac1da0

Related papers

Quantum computational geometry

Marco O. Lanzagorta, Jeffrey K. Uhlmann

The prospects for practical quantum computing have improved significantly over the past few years, and there is an increasing motivation for developing quantum algorithms to address problems that are presently impractical to solve using classical computing. In previous work we have indentified such problems in the areas of computer graphics applications, and we have derived quantum-based solutions. In this paper we examine quantum-based solutions to problems arising in the area of computational geometry. These types of problems are important in a variety of scientific, industrial and military applications such as large scale multi-object simulation, virtual reality systems, and multi-target tracking. In particular, we present quantum algorithms for multidimensional searches, convex hull construction, and collision detection.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 24, 2004•8 citations

Quantum algorithmic methods for computational geometry

Marco O. Lanzagorta, Jeffrey K. Uhlmann

In this paper we develop novel quantum algorithms based on Quantum Multi-Object Search (QMOS) for convex hulls and general object intersection reporting, with applications to computer graphics. These algorithms are developed and described using standard concepts from computer science by encapsulating the physics of quantum computation within black-box subroutines.

Mathematical Structures in Computer Science•Nov 8, 2010•19 citations

Quantum Computation in Computational Geometry

Kunihiko Sadakane, Noriko SUGAWARA, Takeshi Tokuyama

We discuss applications of quantum computation to geometric data processing. These applications include problems on convex hulls, minimum enclosing balls, linear programming, and intersection problems. Technically, we apply well-known Grover’s algorithm (and its variants) combined with geometric algorithms, and no further knowledge of quantum computing is required. However, revealing these applications and emphasizing potential usefulness of quantum computation in geometric data processing will promote research and development of quantum computers and algorithms.

Interdisciplinary Information Sciences•Jan 1, 2002•9 citations

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

Fukuzawa, Shion, Michael T. Goodrich, Irani, Sandy

We introduce a quantum algorithm design paradigm called combine and conquer, which is a quantum version of the "marriage-before-conquest" technique of Kirkpatrick and Seidel. In a quantum combine-and-conquer algorithm, one performs the essential computation of the combine step of a quantum divide-and-conquer algorithm prior to the conquer step while avoiding recursion. This model is better suited for the quantum setting, due to its non-recursive nature. We show the utility of this approach by providing quantum algorithms for 2D maxima set and convex hull problems for sorted point sets running in Õ(√{nh}) time, w.h.p., where h is the size of the output.

Leibniz international proceedings in informatics•Jan 1, 2025•0 citations

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

Shion Fukuzawa, Michael T. Goodrich, Sandy Irani

We introduce a quantum algorithm design paradigm called combine and conquer, which is a quantum version of the "marriage-before-conquest" technique of Kirkpatrick and Seidel. In a quantum combine-and-conquer algorithm, one performs the essential computation of the combine step of a quantum divide-and-conquer algorithm prior to the conquer step while avoiding recursion. This model is better suited for the quantum setting, due to its non-recursive nature. We show the utility of this approach by providing quantum algorithms for 2D maxima set and convex hull problems for sorted point sets running in $\tilde{O}(\sqrt{nh})$ time, w.h.p., where $h$ is the size of the output.

arXiv:2504.06376•Apr 8, 2025•0 citations

Entanglement measurement based on convex hull properties

Hao-Nan Qiang, Jing‐Ling Chen

Quantum entanglement is a unique correlation phenomenon in quantum mechanics, and the measurement of quantum entanglement plays an important role in quantum computing and quantum communication. Many mainstream entanglement criteria and measurement methods currently known have shortcomings in certain aspects, such as not being sufficient or necessary conditions for entanglement, or only being effective in simple cases such as 2-qubits or pure states. In this work, we will propose a scheme for measuring quantum entanglement, which starts with treating the set of quantum separable states as a convex hull of quantum separable pure states, and analyzes the properties of the convex hull to obtain a new form of entanglement measurement. Although a large amount of data is required in the measurement process, this method is not only applicable to 2-qubit quantum states, but also a entanglement measurement method that can be applied to any dimension and any fragment. We will provide several examples to compare their results with other entanglement metrics and entanglement determination methods to verify their feasibility.

arXiv:2411.05389•Nov 8, 2024•0 citations
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.
The prospects for practical quantum computing have improved significantly over the past few years, and there is an increasing motivation for developing quantum algorithms to address problems that are presently impractical to solve using classical computing. In previous work we have indentified such problems in the areas of computer graphics applications, and we have derived quantum-based solutions. In this paper we examine quantum-based solutions to problems arising in the area of computational geometry. These types of problems are important in a variety of scientific, industrial and military applications such as large scale multi-object simulation, virtual reality systems, and multi-target tracking. In particular, we present quantum algorithms for multidimensional searches, convex hull construction, and collision detection.
We discuss applications of quantum computation to geometric data processing. These applications include problems on convex hulls, minimum enclosing balls, linear programming, and intersection problems. Technically, we apply well-known Grover’s algorithm (and its variants) combined with geometric algorithms, and no further knowledge of quantum computing is required. However, revealing these applications and emphasizing potential usefulness of quantum computation in geometric data processing will promote research and development of quantum computers and algorithms.
We introduce a quantum algorithm design paradigm called combine and conquer, which is a quantum version of the "marriage-before-conquest" technique of Kirkpatrick and Seidel. In a quantum combine-and-conquer algorithm, one performs the essential computation of the combine step of a quantum divide-and-conquer algorithm prior to the conquer step while avoiding recursion. This model is better suited for the quantum setting, due to its non-recursive nature. We show the utility of this approach by providing quantum algorithms for 2D maxima set and convex hull problems for sorted point sets running in Õ(√{nh}) time, w.h.p., where h is the size of the output.
We introduce a quantum algorithm design paradigm called combine and conquer, which is a quantum version of the "marriage-before-conquest" technique of Kirkpatrick and Seidel. In a quantum combine-and-conquer algorithm, one performs the essential computation of the combine step of a quantum divide-and-conquer algorithm prior to the conquer step while avoiding recursion. This model is better suited for the quantum setting, due to its non-recursive nature. We show the utility of this approach by providing quantum algorithms for 2D maxima set and convex hull problems for sorted point sets running in O~(nh)\tilde{O}(\sqrt{nh})O~(nh​) time, w.h.p., where hhh is the size of the output.
Quantum entanglement is a unique correlation phenomenon in quantum mechanics, and the measurement of quantum entanglement plays an important role in quantum computing and quantum communication. Many mainstream entanglement criteria and measurement methods currently known have shortcomings in certain aspects, such as not being sufficient or necessary conditions for entanglement, or only being effective in simple cases such as 2-qubits or pure states. In this work, we will propose a scheme for measuring quantum entanglement, which starts with treating the set of quantum separable states as a convex hull of quantum separable pure states, and analyzes the properties of the convex hull to obtain a new form of entanglement measurement. Although a large amount of data is required in the measurement process, this method is not only applicable to 2-qubit quantum states, but also a entanglement measurement method that can be applied to any dimension and any fragment. We will provide several examples to compare their results with other entanglement metrics and entanglement determination methods to verify their feasibility.