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

Time-Space Tradeoffs and Query Complexity in Statistics, Coding Theory, and Quantum Computing

Widad Machmouchi

Computational complexity is the field that studies the computational resources needed by algorithms to correctly solve computational problems. In this thesis, we derive lower bounds on the computational complexity of different problems for different classes of algorithms. The computational resources we consider are the running time, the memory usage and the input query complexity; i.e., the number of positions in the input that the algorithm reads. While deriving upper bounds involves constructing algorithms that run efficiently in their computational resources, lower bounds for a computational problem establish limits on how fast or space-efficient any algorithm solving that problem can be. We consider two main themes of lower bounds: time-space tradeoffs and query complexity lower bounds. Time-space tradeoffs define a relation between the running time and space of any algorithm solving a certain problems. They give a complete picture of the hardness of a problem by deriving a lower bound on one resource when the other is limited. Query complexity measures the depth of a decision tree computing the problem. We derive several lower bounds and upper bounds for different problems on different types of classical computational models and on quantum computers, where the queries to the input are represented by quantum operations operating on the qubits of the algorithm: 1) We derive the largest time-space tradeoff known for a randomized algorithm solving an explicit problem. We consider the pointer jumping problem, also known as the outdegree-1 graph accessibility problem and derive a T in Ω(n log(n/S) log log(n/S)) time-space tradeoff for any randomized oblivious algorithm computing it. Oblivious algorithms have the property that the sequence of operations performed is independent of the value of the input. We derive a similar lower bound for randomized oblivious algorithms with boolean inputs. 2) Frequency moments and order statistics are attributes computed on a sequence of numbers and are extremely relevant in various data analysis settings. We consider computing several copies of these functions on overlapping sequences of numbers by considering a window of a fixed length and sliding it over the input; these versions are called sliding-window versions of these functions. We give hardness separations between the sliding-window versions of these statistics. On one hand, we give a TS in Ω(n 2 ) lower bounds for any algorithm computing sliding-window frequency moments. To complement our lower bound, we give a TS in O(n 2 log c n) comparison-based algorithm for sliding-window frequency moments. On the other hand we describe a T 2 S in O(n 3 log c n) algorithm for sliding-window element distinctness. For order statistics, we derive a similar lower bound of TS in Ω(n 2 ) for any algorithm computing a sliding-widow version of the median, while for the sliding window version of maximum (and minimum), we construct an O(n log n)-time, logarithmic space algorithm. 3) We study the increase in complexity on quantum computers when considering sliding-window frequency moments. We show that quantum computers do not require the same increase in complexity as their classical counterparts by constructing a quantum algorithm for sliding-window version of the zero th frequency moments running in time O(n 3/2 ) and logarithmic space, thus beating the classical lower bound for this problem. 4) In the area of error-correcting codes, we study the query complexity of error detection and correction algorithms. We prove that linear codes over large alphabets that are small in size and concentrated in terms of their codeword weights have testers and correctors that require only a constant number of queries to a word received across a noisy channel. Such codes are called locally-testable and self-correctable. As random codes of small size have the property that their codeword weights are concentrated in a small range of values, they are also locally-testable and self-correctable with high probability. 5) For linear codes with information-efficient encoding, we study the tradeoff between the time and space of their encoders, and their error-correction property. We derive properties on generator matrices of asymptotically good linear codes that guarantee an optimal time-space tradeoff of TS in Ω(n 2 ) for any algorithm encoding them. Moreover, we prove a first step in an approach to establish these properties for all generator matrices of such codes. 6) To compare classical computers to their quantum counterparts, we consider the query complexity of quantum algorithms computing frequency moments and the onto function that takes as input a function and determines whether it is surjective. We prove that any quantum computer computing the onto function or the parity of the zero th frequency moment requires a linear number of queries to the input. Since the onto function with boolean inputs has a simple polynomial-size, constant-depth circuit, we obtain an almost linear lower bound on the query complexity of AC 0 , a special class of circuits that have polynomial size, constant depth and unbounded fan-in for their gates.

•Jul 25, 2013•0 citations

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•6 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

Quantum Query Complexity in Computational Geometry

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

•Jan 1, 2006•1 citation

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•1 citation
Computational complexity is the field that studies the computational resources needed by algorithms to correctly solve computational problems. In this thesis, we derive lower bounds on the computational complexity of different problems for different classes of algorithms. The computational resources we consider are the running time, the memory usage and the input query complexity; i.e., the number of positions in the input that the algorithm reads. While deriving upper bounds involves constructing algorithms that run efficiently in their computational resources, lower bounds for a computational problem establish limits on how fast or space-efficient any algorithm solving that problem can be. We consider two main themes of lower bounds: time-space tradeoffs and query complexity lower bounds. Time-space tradeoffs define a relation between the running time and space of any algorithm solving a certain problems. They give a complete picture of the hardness of a problem by deriving a lower bound on one resource when the other is limited. Query complexity measures the depth of a decision tree computing the problem. We derive several lower bounds and upper bounds for different problems on different types of classical computational models and on quantum computers, where the queries to the input are represented by quantum operations operating on the qubits of the algorithm: 1) We derive the largest time-space tradeoff known for a randomized algorithm solving an explicit problem. We consider the pointer jumping problem, also known as the outdegree-1 graph accessibility problem and derive a T in Ω(n log(n/S) log log(n/S)) time-space tradeoff for any randomized oblivious algorithm computing it. Oblivious algorithms have the property that the sequence of operations performed is independent of the value of the input. We derive a similar lower bound for randomized oblivious algorithms with boolean inputs. 2) Frequency moments and order statistics are attributes computed on a sequence of numbers and are extremely relevant in various data analysis settings. We consider computing several copies of these functions on overlapping sequences of numbers by considering a window of a fixed length and sliding it over the input; these versions are called sliding-window versions of these functions. We give hardness separations between the sliding-window versions of these statistics. On one hand, we give a TS in Ω(n 2 ) lower bounds for any algorithm computing sliding-window frequency moments. To complement our lower bound, we give a TS in O(n 2 log c n) comparison-based algorithm for sliding-window frequency moments. On the other hand we describe a T 2 S in O(n 3 log c n) algorithm for sliding-window element distinctness. For order statistics, we derive a similar lower bound of TS in Ω(n 2 ) for any algorithm computing a sliding-widow version of the median, while for the sliding window version of maximum (and minimum), we construct an O(n log n)-time, logarithmic space algorithm. 3) We study the increase in complexity on quantum computers when considering sliding-window frequency moments. We show that quantum computers do not require the same increase in complexity as their classical counterparts by constructing a quantum algorithm for sliding-window version of the zero th frequency moments running in time O(n 3/2 ) and logarithmic space, thus beating the classical lower bound for this problem. 4) In the area of error-correcting codes, we study the query complexity of error detection and correction algorithms. We prove that linear codes over large alphabets that are small in size and concentrated in terms of their codeword weights have testers and correctors that require only a constant number of queries to a word received across a noisy channel. Such codes are called locally-testable and self-correctable. As random codes of small size have the property that their codeword weights are concentrated in a small range of values, they are also locally-testable and self-correctable with high probability. 5) For linear codes with information-efficient encoding, we study the tradeoff between the time and space of their encoders, and their error-correction property. We derive properties on generator matrices of asymptotically good linear codes that guarantee an optimal time-space tradeoff of TS in Ω(n 2 ) for any algorithm encoding them. Moreover, we prove a first step in an approach to establish these properties for all generator matrices of such codes. 6) To compare classical computers to their quantum counterparts, we consider the query complexity of quantum algorithms computing frequency moments and the onto function that takes as input a function and determines whether it is surjective. We prove that any quantum computer computing the onto function or the parity of the zero th frequency moment requires a linear number of queries to the input. Since the onto function with boolean inputs has a simple polynomial-size, constant-depth circuit, we obtain an almost linear lower bound on the query complexity of AC 0 , a special class of circuits that have polynomial size, constant depth and unbounded fan-in for their gates.
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.