A matroid is a set of elements together with a rule saying which subsets are "independent", in the way that linearly independent columns of a matrix or cycle-free sets of graph edges are. Deciding whether a matroid is connected, meaning it cannot be split into two independent pieces, is the matroid analogue of graph connectivity. The best quantum algorithm uses $O(n^{3/2})$ calls to an independence oracle (a black box that answers "is this subset independent?"). It works by converting the matroid into an auxiliary bipartite graph and running a quantum graph-connectivity search. The best lower bound is only $\Omega(n)$ (Quantum and classical query complexities for determining connectedness of matroids). Because graph connectivity itself needs $\Omega(n^{1.5})$ quantum adjacency queries (Quantum query complexity of graph connectivity), the natural guess is that the $n^{3/2}$ algorithm is optimal.
This note argues that the guess rests on a false intuition, and proposes the polynomial method as the tool to settle the question. The polynomial method lower-bounds quantum algorithms by the degree of polynomials that approximate the function they compute. The false intuition is that a matroid oracle is no stronger than a graph adjacency oracle. In fact one independence query can reveal global linear-algebraic information. The standard hard instances for graph connectivity, one long cycle versus two short cycles, become decidable with a single matroid query. The core claim is that matroid connectivity is governed by how much global information each oracle answer "leaks" about the hidden structure. A polynomial-degree accounting that tracks this leakage is the right instrument for both directions of the gap. On the lower-bound side, it lets us build hard families that defeat leakage. On the upper-bound side, it lets us find low-degree approximations that point to a faster algorithm.
The Observation That Motivates the Program
Take a binary matroid given by the matrix $[I \mid A]$ over the two-element field. Here $I$ is the identity on a basis $B$ of size $m$, and $A$ is an $m \times m$ zero-one matrix. The bipartite graph whose adjacency matrix is $A$ is the matroid's fundamental graph. With no loops or coloops, the matroid is connected exactly when this graph is connected. This is the correspondence the $O(n^{3/2})$ algorithm exploits.
Every bipartite graph arises this way, so arbitrary graph instances can be embedded. It is therefore tempting to transfer the graph lower bound directly.
Now take the classic hard pair: $A$ is the adjacency matrix of either one $2m$-cycle or two $m$-cycles. Each cycle component of $k$ rows and $k$ columns has columns summing to zero, so it has rank $k-1$. Removing any single column from the column block therefore leaves an independent set if and only if there is exactly one cycle. One independence query separates the two cases.
The reverse reduction flagged as problematic in the research file is thus not just unproven. The most natural embedding is actively broken by the oracle's ability to test linear dependence across many elements at once. Any Ω(n^{3/2}) lower bound must use instances where such global tests carry little information. Conversely, if no such instances exist, a faster algorithm should exist.
Core Claim and Formal Object
The object of study is the approximate degree of connectivity measured in the oracle's own language. We do not count degree in the hidden graph bits. Let $\mathcal{A}$ be a family of hidden matrices, let $o_S(A) \in \{0,1\}$ be the independence answer on subset $S$, and let $g(A)$ indicate connectivity. We define the oracle-restricted approximate degree
$$\widetilde{\deg}_{\mathcal{O}}(g;\mathcal{A}) = \min\Big\{d : \exists\, p \in \mathrm{span}\Big\{\textstyle\prod_{S\in T} o_S : |T|\le d\Big\},\ |p(A)-g(A)|\le \tfrac13\ \ \forall A\in\mathcal{A}\Big\}.$$
This is the smallest number of oracle answers whose products can approximate connectivity on the family. The standard argument gives $Q(g) \ge \tfrac12 \widetilde{\deg}_{\mathcal{O}}(g;\mathcal{A})$ for any promise family: amplitudes after $t$ queries are degree-$t$ polynomials in oracle bits, and acceptance probability has degree $2t$.
If instead we count degree in the entries of $A$, as in an adjacency-matrix model, we recover graph connectivity. The difference between the two degrees is exactly the leakage. The proposal is to compute this quantity exactly on small instances, then prove its asymptotic behaviour on a well-chosen family. The target is either $\widetilde{\Omega}(n^{3/2})$, which would close the gap and yield robust corollaries, or $O(n \cdot \mathrm{polylog}\, n)$ on every candidate family, which would indicate the $n^{3/2}$ algorithm is beatable.
Research Program
Machinery. The method comes from the dual-polynomial approach of The Polynomial Method Strikes Back. That work phrases approximate degree as a linear program and proves lower bounds by exhibiting a dual witness. A dual witness is a signed weighting of inputs that is orthogonal to all low-degree polynomials yet correlates with the target function. Its "refined dual block" step places zero weight on inputs that violate a promise. We reuse this machinery, with two changes. Orthogonality is required against products of oracle answers rather than monomials in input bits. The promise is that inputs are genuine matroids of a chosen class.
Symmetrization. We apply this over the group of row and column permutations of $A$, which relabels the ground set while preserving the class. The same move collapsed multivariate polynomials to bivariate ones in Quantum Lower Bound for the Collision Problem and to Chebyshev-type univariate problems in Exact quantum query complexity of weight decision problems via Chebyshev polynomials. After averaging, a product of oracle answers becomes a function of how the queried sets cut the fundamental graph. The central technical lemma to prove is a leakage bound. For a candidate family, the symmetrized degree-$d$ span in oracle answers should be contained in the symmetrized span of degree $O(d\cdot \mathrm{polylog}\, n)$ in edge bits, restricted to hard inputs.
Candidate hard families. The cycle example shows sparse fundamental graphs leak badly. We therefore target families built so that every column is spread across many dependencies. One example is dense random fundamental graphs, where connectivity is decided by whether a small hidden set of cross edges exists between two dense halves. Rank tests on such instances look the same in both cases unless they happen to straddle the hidden bridge. This is where the $n^{3/2}$ structure of graph connectivity should reappear if it survives at all.
Upper-bound side. We look for explicit low-degree approximating polynomials built from global independence tests on column blocks. Such polynomials can be read as candidate algorithms that combine Grover search with rank-style probes.
Corollaries. A dual witness would give more than a bound on bounded-error query complexity. Approximate degree lower bounds for oracle identification problems shows degree bounds persist when the error probability approaches one half, where adversary arguments weaken. The dual-polynomial literature also lifts such witnesses to communication lower bounds. Both would be new for any matroid problem.
Constraint from prior work. The Polynomial Method Strikes Back shows approximate degree can fall strictly below quantum query complexity: Surjectivity has degree $\widetilde{\Theta}(n^{3/4})$ but query complexity $\Theta(n)$. A degree upper bound would therefore suggest, not prove, a faster algorithm. We treat that as a signal to be tested, not a result.
Baselines
Naive reference point. This is the current state: the $O(n^{3/2})$ Grover-over-fundamental-graph algorithm and the $\Omega(n)$ adversary bound of Quantum and classical query complexities for determining connectedness of matroids. The classical randomized $\Omega(n^2)$ from the same paper sits alongside it. Any lower bound exceeding $\Omega(n)$ by a polynomial factor, or any algorithm or degree upper bound below $n^{3/2}$ by a polynomial factor, beats it.
Strongest existing lower-bound method. This is the Ambainis adversary with the minimal-matroid and base-deletion hard family from that paper. We rerun it on exactly the small instance families used in our computations, with the same instance sizes. This lets us see whether its weights grow like $n$ or faster there. Because the classical bound on that family is $\Omega(n^2)$ and looks like search over $n^2$ pairs, we expect it to cap at $\Theta(n)$ quantumly. Showing this explicitly would explain why a new family is needed.
Graph-reduction reference. Graph connectivity in the matrix model has quantum lower bound $\Omega(n^{1.5})$ and upper bound $O(n^{1.5}\log n)$ (Quantum query complexity of graph connectivity). We take this as the benchmark of what "full inheritance" of graph hardness would look like.
Ablation isolating the key ingredient. We compute the ordinary approximate degree in the entries of $A$ on the same family, which treats the oracle as an adjacency oracle. We compare it to $\widetilde{\deg}_{\mathcal{O}}$. The gap between the two numbers is the leakage the proposal is built around. If the gap is negligible on dense families, the reduction is essentially fine there and the difficulty is purely technical. If it is large, leakage is the real obstacle.
Why not just…?
Why not just strengthen the adversary method, which is already used for matroids? This is a real threat. The general negative-weight adversary is known to characterize bounded-error quantum query complexity up to constants. A clever adversary construction could therefore settle the question without polynomials. Our computations include the exact adversary value on small instances for this reason. If it grows like $n^{3/2}$ while the restricted degree stays near $n$, we have found a Surjectivity-type separation and will pursue the adversary route. The polynomial method remains worthwhile where it is at least as strong. There it delivers symmetrization-based proofs that scale, plus the weakly-unbounded-error and communication corollaries the adversary does not give.
Why not just reduce from graph connectivity, since every bipartite graph is a fundamental graph? The single-query observation above refutes the naive reduction. Oracle answers are high-degree functions of the adjacency bits and expose global rank. Any reduction must come with a leakage bound, and proving that bound is the content of this proposal. The ablation measures directly how much leakage a given embedding suffers.
Why not just look for a faster algorithm directly? We do, and that outcome is equally welcome. Searching for algorithms blindly is hard, though. Low-degree approximating polynomials found by the linear program are concrete, inspectable hints about which combinations of global independence tests suffice. The Surjectivity example warns that such hints can mislead. So any candidate algorithm is validated by exact simulation of its query count on small instances before an asymptotic analysis is attempted.
Proposed Experiments and Decisive Checks
Setup. The benchmarks are the formal query-complexity quantities in the file. There is no empirical dataset: Lacuna reports no measured results for any quantum matroid-connectivity algorithm, only asymptotic bounds.
Computations. We enumerate binary matroids $[I\mid A]$ with $m$ up to about 5, giving hidden matrices of up to 25 bits and ground sets of up to 10 elements. On each family we solve the approximate-degree linear program in the oracle-restricted and edge-bit versions. We reduce by the row and column permutation symmetry, which has order up to $(5!)^2$, and use column generation over products of oracle answers. We solve the adversary semidefinite program on the same instances and fit growth exponents in $n$ across three families: sparse cycles, the base-deletion family, and dense bridged graphs.
First decisive check. The oracle-restricted degree on sparse cycle families should be $O(1)$, confirming the leakage observation. If it is not, our reasoning about the oracle is wrong.
Second decisive check. On dense bridged families, compare the fitted exponent of $\widetilde{\deg}_{\mathcal{O}}$ against 1 and 1.5. An exponent near 1.5, matched by the adversary value, triggers the analytical dual-witness proof. An exponent near 1 for both, on every family we can construct, is strong evidence for an $O(n\cdot\mathrm{polylog}\,n)$ algorithm, which we would then attempt to extract from the approximating polynomials.
Third decisive check. A degree exponent near 1 with an adversary exponent near 1.5 would exhibit the first matroid problem where approximate degree and quantum query complexity separate. That would be a result in its own right, in the spirit of Surjectivity.
References
- Quantum and classical query complexities for determining connectedness of matroids
- Quantum query complexity of graph connectivity
- The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
- Quantum lower bound for the collision problem
- Exact quantum query complexity of weight decision problems via Chebyshev polynomials
- Approximate Degree Lower Bounds for Oracle Identification Problems