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

Information Processing Letters

The quantum query complexity of the determinant

Sebastian Dörn, Thomas Thierauf

Published Nov 20, 2008• 8 citations
Publisher
DOI
10.1016/j.ipl.2008.11.006

Related papers

On Exact Quantum Query Complexity

Ashley Montanaro, Richard Jozsa, Graeme Mitchison

arXiv:1111.0475•Algorithmica•Aug 29, 2013•48 citations

Parameterized Quantum Query Algorithms for Graph Problems

Tatsuya Terao, Ryuhei Mori

In this paper, we consider the parameterized quantum query complexity for graph problems. We design parameterized quantum query algorithms for k-vertex cover and k-matching problems, and present lower bounds on the parameterized quantum query complexity. Then, we show that our quantum query algorithms are optimal up to a constant factor when the parameters are small. Our main results are as follows. Parameterized quantum query complexity of vertex cover. In the k-vertex cover problem, we are given an undirected graph G with n vertices and an integer k, and the objective is to determine whether G has a vertex cover of size at most k. We show that the quantum query complexity of the k-vertex cover problem is O(√kn + k^{3/2}√n) in the adjacency matrix model. For the design of the quantum query algorithm, we use the method of kernelization, a well-known tool for the design of parameterized classical algorithms, combined with Grover’s search. Parameterized quantum query complexity of matching. In the k-matching problem, we are given an undirected graph G with n vertices and an integer k, and the objective is to determine whether G has a matching of size at least k. We show that the quantum query complexity of the k-matching problem is O(√kn + k²) in the adjacency matrix model. We obtain this upper bound by using Grover’s search carefully and analyzing the number of Grover’s searches by making use of potential functions. We also show that the quantum query complexity of the maximum matching problem is O(√pn + p²) where p is the size of the maximum matching. For small p, it improves known bounds Õ(n^{3/2}) for bipartite graphs [Blikstad-v.d.Brand-Efron-Mukhopadhyay-Nanongkai, FOCS 2022] and O(n^{7/4}) for general graphs [Kimmel-Witter, WADS 2021]. Lower bounds on parameterized quantum query complexity. We also present lower bounds on the quantum query complexities of the k-vertex cover and k-matching problems. The lower bounds prove the optimality of the above parameterized quantum query algorithms up to a constant factor when k is small. Indeed, the quantum query complexities of the k-vertex cover and k-matching problems are both Θ(√k n) when k = O(√n) and k = O(n^{2/3}), respectively.

arXiv:2408.03864•Leibniz international proceedings in informatics•Jan 1, 2024•2 citations

Query Complexity with Unknowns

Nikhil S. Mande, Karteek Sreenivasaiah

We initiate the study of a new model of query complexity of Boolean functions where, in addition to 0 and 1, the oracle can answer queries with ``unknown''. The query algorithm is expected to output the function value if it can be conclusively determined by the partial information gathered, and it must output ``unknown'' if not. We formalize this model by using Kleene's strong logic of indeterminacy on three variables to capture unknowns. We call this model the `u-query model'. We relate the query complexity of functions in the new u-query model with their analogs in the standard query model. We show an explicit function that is exponentially harder in the u-query model than in the usual query model. We give sufficient conditions for a function to have u-query complexity asymptotically the same as its query complexity. Using u-query analogs of the combinatorial measures of sensitivity, block sensitivity, and certificate complexity, we show that deterministic, randomized, and quantum u-query complexities of all total Boolean functions are polynomially related to each other, just as in the usual query models.

arXiv:2412.06395•Dec 9, 2024•1 citation

The Quantum Query Complexity of Algebraic Properties

Sebastian Dörn, Thomas Thierauf

Lecture notes in computer science•Aug 27, 2007•20 citations

Answer Partitions and Oracle Access Determine Quantum Query Complexity

Karl Svozil

An answer partition specifies which oracle instances share an output, while query complexity also depends on how those instances are accessed. We formulate exact one-query answer-partition resolution as block discrimination of a unitary oracle family. Applied to Deutsch's problem with a controlled response unitary V, the criterion shows that one query suffices if and only if -1 is an eigenvalue of V; cyclic addition in odd response dimension therefore raises the exact quantum cost to two queries, matching the classical cost while preserving the same computational-basis point values. Holding the standard Boolean point oracle fixed, we further show that balanced answer partitions with equal-sized cells can have different exact classical and quantum query complexities. A complete exact classification is given for all 35 balanced three-bit partitions, while the unresolved four-bit cases are reported explicitly as numerical candidates. These results separate the combinatorial specification of an answer from the oracle-dependent distinguishability that determines query complexity.

quant-pharXiv:2605.12675•May 14, 2026•1 citation

Quantum Query Complexity of Dyck Languages with Bounded Height

Kamil Ravilevich Khadiev, Yixin Shen

We consider the problem of determining if a sequence of parentheses is well parenthesized, with a depth of at most h. We denote this language as $Dyck_h$. We study the quantum query complexity of this problem for different h as function of the length n of the word. It has been known from a recent paper by Aaronson et al. that, for any constant h, since $Dyck_h$ is star-free, it has quantum query complexity $\tildeΘ(\sqrt{n})$, where the hidden logarithm factors in $\tildeΘ$ depend on h. Their proof does not give rise to an algorithm. When h is not a constant, $Dyck_h$ is not even context-free. We give an algorithm with $O\left(\sqrt{n}\log(n)^{0.5h}\right)$ quantum queries for $Dyck_h$ for all h. This is better than the trival upper bound $n$ when $h=o(\frac{\log(n)}{\log\log n})$. We also obtain lower bounds: we show that for every $00$ such that $Q(\text{Dyck}_{c\log(n)}(n))=Ω(n^{1-ε})$. When $h=ω(\log(n))$, the quantum query complexity is close to $n$, i.e. $Q(\text{Dyck}_h(n))=ω(n^{1-ε})$ for all $ε>0$. Furthermore when $h=Ω(n^ε)$ for some $ε>0$, $Q(\text{Dyck}_{h}(n))=Θ(n)$.

arXiv:1912.02176•Dec 4, 2019•0 citations
In this paper, we consider the parameterized quantum query complexity for graph problems. We design parameterized quantum query algorithms for k-vertex cover and k-matching problems, and present lower bounds on the parameterized quantum query complexity. Then, we show that our quantum query algorithms are optimal up to a constant factor when the parameters are small. Our main results are as follows. Parameterized quantum query complexity of vertex cover. In the k-vertex cover problem, we are given an undirected graph G with n vertices and an integer k, and the objective is to determine whether G has a vertex cover of size at most k. We show that the quantum query complexity of the k-vertex cover problem is O(√kn + k^{3/2}√n) in the adjacency matrix model. For the design of the quantum query algorithm, we use the method of kernelization, a well-known tool for the design of parameterized classical algorithms, combined with Grover’s search. Parameterized quantum query complexity of matching. In the k-matching problem, we are given an undirected graph G with n vertices and an integer k, and the objective is to determine whether G has a matching of size at least k. We show that the quantum query complexity of the k-matching problem is O(√kn + k²) in the adjacency matrix model. We obtain this upper bound by using Grover’s search carefully and analyzing the number of Grover’s searches by making use of potential functions. We also show that the quantum query complexity of the maximum matching problem is O(√pn + p²) where p is the size of the maximum matching. For small p, it improves known bounds Õ(n^{3/2}) for bipartite graphs [Blikstad-v.d.Brand-Efron-Mukhopadhyay-Nanongkai, FOCS 2022] and O(n^{7/4}) for general graphs [Kimmel-Witter, WADS 2021]. Lower bounds on parameterized quantum query complexity. We also present lower bounds on the quantum query complexities of the k-vertex cover and k-matching problems. The lower bounds prove the optimality of the above parameterized quantum query algorithms up to a constant factor when k is small. Indeed, the quantum query complexities of the k-vertex cover and k-matching problems are both Θ(√k n) when k = O(√n) and k = O(n^{2/3}), respectively.
We initiate the study of a new model of query complexity of Boolean functions where, in addition to 0 and 1, the oracle can answer queries with ``unknown''. The query algorithm is expected to output the function value if it can be conclusively determined by the partial information gathered, and it must output ``unknown'' if not. We formalize this model by using Kleene's strong logic of indeterminacy on three variables to capture unknowns. We call this model the `u-query model'. We relate the query complexity of functions in the new u-query model with their analogs in the standard query model. We show an explicit function that is exponentially harder in the u-query model than in the usual query model. We give sufficient conditions for a function to have u-query complexity asymptotically the same as its query complexity. Using u-query analogs of the combinatorial measures of sensitivity, block sensitivity, and certificate complexity, we show that deterministic, randomized, and quantum u-query complexities of all total Boolean functions are polynomially related to each other, just as in the usual query models.
An answer partition specifies which oracle instances share an output, while query complexity also depends on how those instances are accessed. We formulate exact one-query answer-partition resolution as block discrimination of a unitary oracle family. Applied to Deutsch's problem with a controlled response unitary V, the criterion shows that one query suffices if and only if -1 is an eigenvalue of V; cyclic addition in odd response dimension therefore raises the exact quantum cost to two queries, matching the classical cost while preserving the same computational-basis point values. Holding the standard Boolean point oracle fixed, we further show that balanced answer partitions with equal-sized cells can have different exact classical and quantum query complexities. A complete exact classification is given for all 35 balanced three-bit partitions, while the unresolved four-bit cases are reported explicitly as numerical candidates. These results separate the combinatorial specification of an answer from the oracle-dependent distinguishability that determines query complexity.
We consider the problem of determining if a sequence of parentheses is well parenthesized, with a depth of at most h. We denote this language as DyckhDyck_hDyckh​. We study the quantum query complexity of this problem for different h as function of the length n of the word. It has been known from a recent paper by Aaronson et al. that, for any constant h, since DyckhDyck_hDyckh​ is star-free, it has quantum query complexity Θ~(n)\tildeΘ(\sqrt{n})Θ~(n​), where the hidden logarithm factors in Θ~\tildeΘΘ~ depend on h. Their proof does not give rise to an algorithm. When h is not a constant, DyckhDyck_hDyckh​ is not even context-free. We give an algorithm with O(nlog⁡(n)0.5h)O\left(\sqrt{n}\log(n)^{0.5h}\right)O(n​log(n)0.5h) quantum queries for DyckhDyck_hDyckh​ for all h. This is better than the trival upper bound nnn when h=o(log⁡(n)log⁡log⁡n)h=o(\frac{\log(n)}{\log\log n})h=o(loglognlog(n)​). We also obtain lower bounds: we show that for every 000000 such that Q(Dyckclog⁡(n)(n))=Ω(n1−ε)Q(\text{Dyck}_{c\log(n)}(n))=Ω(n^{1-ε})Q(Dyckclog(n)​(n))=Ω(n1−ε). When h=ω(log⁡(n))h=ω(\log(n))h=ω(log(n)), the quantum query complexity is close to nnn, i.e. Q(Dyckh(n))=ω(n1−ε)Q(\text{Dyck}_h(n))=ω(n^{1-ε})Q(Dyckh​(n))=ω(n1−ε) for all ε>0ε>0ε>0. Furthermore when h=Ω(nε)h=Ω(n^ε)h=Ω(nε) for some ε>0ε>0ε>0, Q(Dyckh(n))=Θ(n)Q(\text{Dyck}_{h}(n))=Θ(n)Q(Dyckh​(n))=Θ(n).