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

Query complexity of matroids.

Raghav Kulkarni, Miklós Sántha

Published Jan 1, 2012• 3 citations
OpenAlex

Abstract

Let \(\mathcal{M}\) be a bridgeless matroid on ground set {1,...,n} and \(f_{\mathcal{M}}: \{0,1\}^n \to \{0, 1\}\) be the indicator function of its independent sets. A folklore fact is that \(f_\mathcal{M}\) is evasive, i.e., \(D(f_\mathcal{M}) = n\) where D(f) denotes the deterministic decision tree complexity of f. Here we prove query complexity lower bounds for \(f_\mathcal{M}\) in three stronger query models: (a) \(D_\oplus(f_\mathcal{M}) = \Omega(n),\) where D ⊕ (f) denotes the parity decision tree complexity of f; (b) \(R(f_\mathcal{M}) = \Omega(n / \log n),\) where R(f) denotes the bounded error randomized decision tree complexity of f; and (c) \(Q(f_\mathcal{M}) = \Omega(\sqrt n),\) where Q(f) denotes the bounded error quantum query complexity of f.

Related papers

Reframing Matroid Intersection as a Quantum Query Complexity Problem

Sumer Chaudhary, Thomas Patrick De Mastri, Michael Jarret

A matroid generalizes linear independence, being constructed on (E, I) with ground set E and independent sets I as a subset of 2E. Matroid intersection looks for the largest independent set in two matroids on E. Classical algorithms, like Edmonds’ and Cunningham’s, solve this using independence queries, but the minimum needed is unestablished. To establish this, we selected a target function, constructed query gates for non-adaptive query words, and introduced adaptivity, where the next query depends on previous answers. Using v(M1, M2) as the largest common independent set’s size, we examine fk(M1, M2):= [v >= k], because v is the common refinement of all {fk}. Independence queries have three models: onesided (tests one matroid), pair-valued (tests both matroids), and common-independence (tests independence in both). In the non-adaptive query-only model, one fk needs 2 (n/k) one-sided queries but only (n/k) jointly, while v needs 2(2n - 1) one-sided queries, an exact exponential lower bound. This common-independence oracle computes every fk, yet cannot reconstruct the exchange graph classical algorithms depend on, implying other types of algorithms. We recovered Edmonds’ algorithm as an adaptive query word matching its known nr2 bound, then built optimal decision trees for small ground sets. We found that, at n = 4, the optimal worst case is 5 queries versus 17 and 18 for Edmonds’ and Cunningham’s, demonstrating that classical algorithms are not query-optimal despite running in polynomial time. We are working to generalize this classical workflow to discover quantum query circuits.

Journal of Student-Scientists' Research•Sep 21, 2026•0 citations

Lower bounds on quantum query complexity for read-once decision trees with parity nodes

Hideaki Fukuhara, Eiji Takimoto

We introduce a complexity measure for decision trees called the soft rank, which measures how well-balanced a given tree is. The soft rank is a somehow relaxed variant of the rank. Among all decision trees of depth d, the complete binary decision tree (the most balanced tree) has maximum soft rank d, the decision list (the most unbalanced tree) has minimum soft rank √d, and any other trees have soft rank between √d and d. We show that, for any decision tree T in some class G of decision trees which includes all read-once decision trees, the soft rank of T is a lower bound on the quantum query complexity of the Boolean function that T represents. This implies that for any Boolean function f that is represented by a decision tree in G, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f.

Computing: The Australasian Theory Symposium•Jan 1, 2009•0 citations

Randomized query complexity can beat certificate complexity

Shalev Ben-David, Robin Kothari

A long-standing open question in query complexity asks whether there is a total Boolean function f with R(f) << C(f), where R(f) and C(f) denote its bounded-error randomized query complexity and certificate complexity, respectively. We construct a function with R(f) = O~(sqrt{C(f)}), which is optimal up to log factors. The same function also has $Q(f) = O~(C(f)^{1/4}), where Q(f) is the bounded-error quantum query complexity of f, which is also nearly optimal.

cs.CCCross-listedarXiv:2609.15063•Sep 15, 2026•0 citations

Quantum Speedup and Limitations on Matroid Properties.

Xiaowei Huang, Jingquan Luo, Lvzhou Li

In this paper, we study for the first time how well quantum algorithms perform on matroid properties. We show that quadratic quantum speedup is possible for the calculation problem of finding the girth or the number of circuits (bases, flats, hyperplanes) of a matroid, and the decision problem of deciding whether a matroid is uniform or Eulerian, by giving a uniform lower bound $\Omega(\sqrt{\binom{n}{\lfloor n/2\rfloor}})$ on the query complexity for all these problems. On the other hand, for the uniform matroid decision problem, we present an asymptotically optimal quantum algorithm which achieves the lower bound, and for the girth problem, we give an almost optimal quantum algorithm with query complexity $O(\log n\sqrt{\binom{n}{\lfloor n/2\rfloor}})$. In addition, for the paving matroid decision problem, we prove a lower bound $\Omega(\sqrt{\binom{n}{\lfloor n/2\rfloor}/n})$ on the query complexity, and give an $O(\sqrt{\binom{n}{\lfloor n/2\rfloor}})$ quantum algorithm.

•Nov 25, 2021•1 citation

Models of Query Complexity for Boolean Functions

Sourav Chakraborty

In this thesis we study various models of query complexity. A query algorithm computes a function under the restriction that the input can be accessed only by making probes to the the bits of the input. The query complexity of a function f is the minimum number of probes made by any query algorithm that computes f. In this thesis, we consider three different models of query complexity, (1) deterministic decision tree complexity (query complexity when the underlying algorithm is deterministic), (2) approximate decision tree complexity aka. property testing (query complexity when the underlying algorithm is probabilistic and only expected to ”approximately ” compute f) and quantum query complexity (query complexity when the underlying algorithm is allowed to make quantum queries). The main results in this thesis are: • We study the relation between deterministic decision tree complexity and other combinatorial measures of complexity measures like sensitivity and block sensitivity. We prove that for minterm-transitive functions the sensitivity is quadratically related to block sensitivity which is polynomially

•Aug 6, 2010•0 citations

Quantum Query Complexity and Span Programs from Pre-Geometry

Justin Roy Cox, Neil Epstein, Zhirui Hu +2 more

Span programs provide a general method for designing quantum query algorithms, and for Boolean coordinate queries their optimum cost agrees with the general adversary bound. We develop a matroidal organization of this optimization that separates dependence data determined by the query problem from the dependence structure chosen by a span program. The resulting source matroid records query dependence, target determination, and separation data, while a program matroid records dependencies among the target and response-labeled input elements of a candidate program. When a query problem admits a source matroid, we use its structure to organize adversary upper and lower bounds. For separating binary query sets in this setting, the global matroid-span-program optimum equals $\mathrm{Adv}^{\pm}_{\mathcal Q}(f)$. For a fixed regular program matroid, projective uniqueness reduces optimization over real representations to positive element weights. We express positive and negative costs as weighted basis ratios and derive exact $1$-, $2$-, and $3$-sum reductions, giving a compositional evaluation of the fixed-weight objective along a Seymour decomposition. For pointed $R_{10}$ closure, exact certificates give $3.9087553<\mathrm{Adv}^{\pm}_{\mathcal Q_R}(f_R)<3.9301$. The natural $R_{10}$ program has optimized cost $5$, while another regular program has cost at most $\sqrt{87/5}$. Recursive self-composition yields a family on $N$ input bits with randomized query complexity $Ω(N^{0.7324867\ldots})$, an explicit quantum algorithm using $O(N^{0.6500178\ldots})$ queries, and $Q(F)=Θ(N^α)$ for $0.6204277\ldots<α<0.6229063\ldots$.

quant-pharXiv:2610.03914•Oct 6, 2026•0 citations
Let (\mathcal{M}) be a bridgeless matroid on ground set {1,...,n} and (f_{\mathcal{M}}: {0,1}^n \to {0, 1}) be the indicator function of its independent sets. A folklore fact is that (f_\mathcal{M}) is evasive, i.e., (D(f_\mathcal{M}) = n) where D(f) denotes the deterministic decision tree complexity of f. Here we prove query complexity lower bounds for (f_\mathcal{M}) in three stronger query models: (a) (D_\oplus(f_\mathcal{M}) = \Omega(n),) where D ⊕ (f) denotes the parity decision tree complexity of f; (b) (R(f_\mathcal{M}) = \Omega(n / \log n),) where R(f) denotes the bounded error randomized decision tree complexity of f; and (c) (Q(f_\mathcal{M}) = \Omega(\sqrt n),) where Q(f) denotes the bounded error quantum query complexity of f.
A matroid generalizes linear independence, being constructed on (E, I) with ground set E and independent sets I as a subset of 2E. Matroid intersection looks for the largest independent set in two matroids on E. Classical algorithms, like Edmonds’ and Cunningham’s, solve this using independence queries, but the minimum needed is unestablished. To establish this, we selected a target function, constructed query gates for non-adaptive query words, and introduced adaptivity, where the next query depends on previous answers. Using v(M1, M2) as the largest common independent set’s size, we examine fk(M1, M2):= [v >= k], because v is the common refinement of all {fk}. Independence queries have three models: onesided (tests one matroid), pair-valued (tests both matroids), and common-independence (tests independence in both). In the non-adaptive query-only model, one fk needs 2 (n/k) one-sided queries but only (n/k) jointly, while v needs 2(2n - 1) one-sided queries, an exact exponential lower bound. This common-independence oracle computes every fk, yet cannot reconstruct the exchange graph classical algorithms depend on, implying other types of algorithms. We recovered Edmonds’ algorithm as an adaptive query word matching its known nr2 bound, then built optimal decision trees for small ground sets. We found that, at n = 4, the optimal worst case is 5 queries versus 17 and 18 for Edmonds’ and Cunningham’s, demonstrating that classical algorithms are not query-optimal despite running in polynomial time. We are working to generalize this classical workflow to discover quantum query circuits.
We introduce a complexity measure for decision trees called the soft rank, which measures how well-balanced a given tree is. The soft rank is a somehow relaxed variant of the rank. Among all decision trees of depth d, the complete binary decision tree (the most balanced tree) has maximum soft rank d, the decision list (the most unbalanced tree) has minimum soft rank √d, and any other trees have soft rank between √d and d. We show that, for any decision tree T in some class G of decision trees which includes all read-once decision trees, the soft rank of T is a lower bound on the quantum query complexity of the Boolean function that T represents. This implies that for any Boolean function f that is represented by a decision tree in G, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f.
In this paper, we study for the first time how well quantum algorithms perform on matroid properties. We show that quadratic quantum speedup is possible for the calculation problem of finding the girth or the number of circuits (bases, flats, hyperplanes) of a matroid, and the decision problem of deciding whether a matroid is uniform or Eulerian, by giving a uniform lower bound Ω((n⌊n/2⌋))\Omega(\sqrt{\binom{n}{\lfloor n/2\rfloor}})Ω((⌊n/2⌋n​)​) on the query complexity for all these problems. On the other hand, for the uniform matroid decision problem, we present an asymptotically optimal quantum algorithm which achieves the lower bound, and for the girth problem, we give an almost optimal quantum algorithm with query complexity O(log⁡n(n⌊n/2⌋))O(\log n\sqrt{\binom{n}{\lfloor n/2\rfloor}})O(logn(⌊n/2⌋n​)​). In addition, for the paving matroid decision problem, we prove a lower bound Ω((n⌊n/2⌋)/n)\Omega(\sqrt{\binom{n}{\lfloor n/2\rfloor}/n})Ω((⌊n/2⌋n​)/n​) on the query complexity, and give an O((n⌊n/2⌋))O(\sqrt{\binom{n}{\lfloor n/2\rfloor}})O((⌊n/2⌋n​)​) quantum algorithm.
In this thesis we study various models of query complexity. A query algorithm computes a function under the restriction that the input can be accessed only by making probes to the the bits of the input. The query complexity of a function f is the minimum number of probes made by any query algorithm that computes f. In this thesis, we consider three different models of query complexity, (1) deterministic decision tree complexity (query complexity when the underlying algorithm is deterministic), (2) approximate decision tree complexity aka. property testing (query complexity when the underlying algorithm is probabilistic and only expected to ”approximately ” compute f) and quantum query complexity (query complexity when the underlying algorithm is allowed to make quantum queries). The main results in this thesis are: • We study the relation between deterministic decision tree complexity and other combinatorial measures of complexity measures like sensitivity and block sensitivity. We prove that for minterm-transitive functions the sensitivity is quadratically related to block sensitivity which is polynomially
Span programs provide a general method for designing quantum query algorithms, and for Boolean coordinate queries their optimum cost agrees with the general adversary bound. We develop a matroidal organization of this optimization that separates dependence data determined by the query problem from the dependence structure chosen by a span program. The resulting source matroid records query dependence, target determination, and separation data, while a program matroid records dependencies among the target and response-labeled input elements of a candidate program. When a query problem admits a source matroid, we use its structure to organize adversary upper and lower bounds. For separating binary query sets in this setting, the global matroid-span-program optimum equals AdvQ±(f)\mathrm{Adv}^{\pm}_{\mathcal Q}(f)AdvQ±​(f). For a fixed regular program matroid, projective uniqueness reduces optimization over real representations to positive element weights. We express positive and negative costs as weighted basis ratios and derive exact 111-, 222-, and 333-sum reductions, giving a compositional evaluation of the fixed-weight objective along a Seymour decomposition. For pointed R10R_{10}R10​ closure, exact certificates give 3.9087553<AdvQR±(fR)<3.93013.9087553<\mathrm{Adv}^{\pm}_{\mathcal Q_R}(f_R)<3.93013.9087553<AdvQR​±​(fR​)<3.9301. The natural R10R_{10}R10​ program has optimized cost 555, while another regular program has cost at most 87/5\sqrt{87/5}87/5​. Recursive self-composition yields a family on NNN input bits with randomized query complexity Ω(N0.7324867…)Ω(N^{0.7324867\ldots})Ω(N0.7324867…), an explicit quantum algorithm using O(N0.6500178…)O(N^{0.6500178\ldots})O(N0.6500178…) queries, and Q(F)=Θ(Nα)Q(F)=Θ(N^α)Q(F)=Θ(Nα) for 0.6204277…<α<0.6229063…0.6204277\ldots<α<0.6229063\ldots0.6204277…<α<0.6229063….