Related papers: Quantum algorithms for Hopcroft's problem

Quantum algorithms for Hopcroft's problem

URL: http://arxiv.org/abs/2405.01160v1
Date: Thu, 2 May 2024 10:29:06 GMT
Title: Quantum algorithms for Hopcroft's problem
Authors: Vladimirs Andrejevs, Aleksandrs Belovs, Jevgēnijs Vihrovs,
Abstract summary: We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
Score: 45.45456673484445
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this work we study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. Given $n$ points and $n$ lines in the plane, the task is to determine whether there is a point-line incidence. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n^{4/3})$ time, with matching lower bounds in some restricted settings. Our results are two different quantum algorithms with time complexity $\widetilde O(n^{5/6})$. The first algorithm is based on partition trees and the quantum backtracking algorithm. The second algorithm uses a quantum walk together with a history-independent dynamic data structure for storing line arrangement which supports efficient point location queries. In the setting where the number of points and lines differ, the quantum walk-based algorithm is asymptotically faster. The quantum speedups for the aforementioned data structures may be useful for other geometric problems.

Related papers

Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z)
Quantum optimization algorithm based on multistep quantum computation [0.0]
We present a quantum algorithm for finding the minimum of a function based on multistep quantum computation. In this algorithm, the dimension of the search space of the problem can be reduced exponentially step by step. We have tested the algorithm for some continuous test functions.
arXiv Detail & Related papers (2023-06-30T01:58:23Z)
Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z)
Manifold Learning for Dimensionality Reduction: Quantum Isomap algorithm [15.622577797491788]
Isomap algorithm is widely used in neuroimaging, spectral analysis and other fields. We propose the quantum Isomap algorithm, which consists of two sub-algorithms. The time complexity of quantum Isomap algorithm is $O(dNpolylogN)$.
arXiv Detail & Related papers (2022-12-07T12:29:41Z)
Quantum algorithms and the power of forgetting [1.5791732557395555]
We show that a natural class of efficient quantum algorithms provably cannot find a path from ENTRANCE to EXIT. While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is unclear how an algorithm could benefit from this behavior.
arXiv Detail & Related papers (2022-11-22T18:04:10Z)
Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z)
Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z)
Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
Existing quantum walk-based search algorithms suffer from the souffl'e problem. We present a new quantum walk-based search framework that achieves robustness without sacrificing the quantum speedup.
arXiv Detail & Related papers (2021-11-17T10:04:44Z)
On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z)
Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
We show that a quantum algorithm can be implemented in time $tilde O(sqrtGT)$. Our algorithm is based on non-binary span programs and their efficient implementation.
arXiv Detail & Related papers (2021-05-18T06:51:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.