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

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE

Quantum query complexity in computational geometry revisited

Abhinav Bahadur, Christoph Dürr, Thibault Lafaye, Raghav Kulkarni

Published May 5, 2006• 2 citations
Publisher

Abstract

We are interested in finding quantum algorithms for problems in the area of computation geometry. Many of the problems we study have already polynomial time algorithms. Bounded error quantum algorithms can actually have sublinear running time.
DOI
10.1117/12.661591

Related papers

Quantum Algorithms and Lower Bounds for Independent Set and Subgraph Isomorphism Problem

Sebastian Doern

The study of the quantum query complexity for some graph problems is an interesting area in quantum computing. Only for a few graph problems there are quantum algorithms and lower bounds known. We present some new quantum query and quantum time algorithms and quantum query complexity bounds for the maximal and maximum independent set problem and the graph and subgraph isomorphism problem.

•Oct 12, 2005•1 citation

Cost-Based Query Optimization for Quantum Computation

Immanuel Trummer

Prior work explores the use of quantum computing to solve variants of query optimization.Instead, I propose using query optimization techniques to make quantum computation more efficient.

Workshop on Quantum Computing and Quantum-Inspired Technology for Data-Intensive Systems and Applications (Q-Data)•Jun 22, 2025•4 citations

Constant-Time Algorithms for Monomer-Dimer Systems on Bounded Degree Graphs

Marc Lelarge, Hang Zhou

For a graph G on n vertices, let Z(G, λ) be the partition function of the monomer-dimer system defined by: Z(G, λ) = ∑ k mk(G)λk, where mk(G) is the number of matchings of cardinality k in G. We develop a constant-time algorithm for approximating log Z(G, λ) at an arbitrary point λ ≥ 0 with additive error ɛn. In the bounded degree model, the query complexity of our algorithm is polynomial in 1/ɛ, and we provide a lower bound quadratic in 1/ɛ for this problem. This is the first analysis of a sublinear-time algorithm for a #P-complete problem. Our approach is based on the correlation decay of the Gibbs distribution associated with Z(G, λ). We show that our algorithm approximates the probability for a vertex to be covered by a matching sampled according to this Gibbs distribution in a near-optimal sublinear-time. We extend our results to approximate the average size and the entropy of such a matching with an additive error in constant time, where again the query complexity is polynomial in 1/ɛ and the lower bound is quadratic in 1/ɛ. Our algorithms are simple to implement and of practical use when dealing with massive datasets. Our results extend to many other problems where the correlation decay is known to hold as for independent sets or the Ising model up to the critical activity.

•Aug 17, 2012•1 citation

A sublinear time quantum algorithm for longest common substring problem between run-length encoded strings

Tzu-Ching Lee, Han-Hsuan Lin

We give a sublinear quantum algorithm for the longest common substring (LCS) problem on the run-length encoded (RLE) inputs, under the assumption that the prefix-sums of the runs are given. Our algorithm costs $\tilde{O}(n^{5/6})\cdot O(\mathrm{polylog}(\tilde{n}))$ time, where $n$ and $\tilde{n}$ are the encoded and decoded length of the inputs, respectively. We justify the use of the prefix-sum oracles by showing that, without the oracles, there is a $Ω(n/\log^2n)$ lower-bound on the quantum query complexity of finding LCS given two RLE strings due to a reduction of $\mathsf{PARITY}$ to the problem.

arXiv:2310.00966•Oct 2, 2023•0 citations

On the Complexity of Quantum Searching Using Complex Queries

Markus Grassl, Thomas Beth

We discuss the quantum search algorithm using complex queries that has recently been published by Grover (quant-ph/9706005). We recall the algorithm adding some details showing which complex query has to be evaluated. Based on this version of the algorithm we discuss its complexity.

arXiv:quant-ph/9706052•Jun 23, 1997•0 citations

Quantum Query Complexity in Computational Geometry

Abhinav Bahadur, Christoph Dürr, Raghav Kulkarni +1 more

•Jan 1, 2006•1 citation
For a graph G on n vertices, let Z(G, λ) be the partition function of the monomer-dimer system defined by: Z(G, λ) = ∑ k mk(G)λk, where mk(G) is the number of matchings of cardinality k in G. We develop a constant-time algorithm for approximating log Z(G, λ) at an arbitrary point λ ≥ 0 with additive error ɛn. In the bounded degree model, the query complexity of our algorithm is polynomial in 1/ɛ, and we provide a lower bound quadratic in 1/ɛ for this problem. This is the first analysis of a sublinear-time algorithm for a #P-complete problem. Our approach is based on the correlation decay of the Gibbs distribution associated with Z(G, λ). We show that our algorithm approximates the probability for a vertex to be covered by a matching sampled according to this Gibbs distribution in a near-optimal sublinear-time. We extend our results to approximate the average size and the entropy of such a matching with an additive error in constant time, where again the query complexity is polynomial in 1/ɛ and the lower bound is quadratic in 1/ɛ. Our algorithms are simple to implement and of practical use when dealing with massive datasets. Our results extend to many other problems where the correlation decay is known to hold as for independent sets or the Ising model up to the critical activity.
We give a sublinear quantum algorithm for the longest common substring (LCS) problem on the run-length encoded (RLE) inputs, under the assumption that the prefix-sums of the runs are given. Our algorithm costs O~(n5/6)⋅O(polylog(n~))\tilde{O}(n^{5/6})\cdot O(\mathrm{polylog}(\tilde{n}))O~(n5/6)⋅O(polylog(n~)) time, where nnn and n~\tilde{n}n~ are the encoded and decoded length of the inputs, respectively. We justify the use of the prefix-sum oracles by showing that, without the oracles, there is a Ω(n/log⁡2n)Ω(n/\log^2n)Ω(n/log2n) lower-bound on the quantum query complexity of finding LCS given two RLE strings due to a reduction of PARITY\mathsf{PARITY}PARITY to the problem.