Reframing Matroid Intersection as a Quantum Query Complexity Problem

Abstract

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 f_k(M1, M2):= [v >= k], because v is the common refinement of all {f_k}. 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 f_k 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 f_k, 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 nr²  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.