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

Journal of Student-Scientists' Research

Reframing Matroid Intersection as a Quantum Query Complexity Problem

Sumer Chaudhary, Thomas Patrick De Mastri, Michael Jarret

Published Sep 21, 2026• 0 citations
Publisher

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 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.

DOI
10.13021/jssr2026.5652

Related papers

Quantum and classical query complexities for determining connectedness of matroids

Xiaowei Huang, Shiguang Feng, Lvzhou Li

Connectivity is a fundamental structural property of matroids, and has been studied algorithmically over 50 years. In 1974, Cunningham proposed a deterministic algorithm consuming $O(n^{2})$ queries to the independence oracle to determine whether a matroid is connected. Since then, no algorithm, not even a random one, has worked better. To the best of our knowledge, the classical query complexity lower bound and the quantum complexity for this problem have not been considered. Thus, in this paper we are devoted to addressing these issues, and our contributions are threefold as follows: (i) First, we prove that the randomized query complexity of determining whether a matroid is connected is $Ω(n^2)$ and thus the algorithm proposed by Cunningham is optimal in classical computing. (ii) Second, we present a quantum algorithm with $O(n^{3/2})$ queries, which exhibits provable quantum speedups over classical ones. (iii) Third, we prove that any quantum algorithm requires $Ω(n)$ queries, which indicates that quantum algorithms can achieve at most a quadratic speedup over classical ones. Therefore, we have a relatively comprehensive understanding of the potential of quantum computing in determining the connectedness of matroids.\

arXiv:2306.12103•Jun 21, 2023•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

Simultaneously Query-Optimal Quantum Linear-System Algorithm

Minbo Gao, Zhengfeng Ji, Chenghua Liu

Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle $U_A$ and the right-hand side through a state-preparation oracle $U_b$. The optimal query complexities of these two oracles are known separately: $O(κ\log(1/\varepsilon))$ queries to $U_A$ and $O(κ/s)$ queries to $U_b$, where $s=α\|A^{-1}b\|$. Whether a single algorithm can achieve both bounds simultaneously has remained open. We resolve this question affirmatively. Given a constant-factor estimate of $s$, we give a quantum linear-system algorithm that prepares the normalized solution to error $\varepsilon$ using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to $U_A$ and $O\left(κ/{s}\right)$ queries to $U_b$. The algorithm separates state preparation from precision refinement, so only the matrix-query count depends on the target accuracy. We also prove a matching same-instance worst-case lower bound: for every quantum linear-system algorithm and every solution-norm scale, there exists a single Hermitian instance on which that algorithm requires both $Ω(κ\log(1/\varepsilon))$ matrix queries and $Ω(κ/s)$ state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.

quant-pharXiv:2609.33686•Sep 29, 2026•0 citations

Query complexity of matroids.

Raghav Kulkarni, Miklós Sántha

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.

•Jan 1, 2012•3 citations

Quantum Query Complexity of Persistence Statistics in Graph Zigzags

Cheng Xin

We study the query complexity of estimating scalar summaries of zigzag bar lifetimes from snapshot-adjacency bits. For graphs $G_1,\ldots,G_m$ on $n$ labeled vertices, let $\ell_b$ be the snapshot lifetime of a degree-one bar $b$ of the intersection zigzag. For a probability generating function $φ(x)=\mathbb{E}[x^R]$, the statistic $F_φ=\sum_bφ(\ell_b/m)$ includes normalized degree-$r$ total persistence and the mean generalized rank over a uniform time window. An exact identity underlies our algorithm: sample $R$ uniform times; the expected generalized rank between their minimum and maximum equals $F_φ$. For graphs that rank is the circuit rank of an intersection graph, so a nonlinear barcode functional becomes an average of edge and component counts, and no barcode is computed. Without spectral-gap, homology-state, or QRAM assumptions, this gives a quantum estimator with additive error $\varepsilon n$ and $\widetilde O(\sqrt{m(K+n)}/\varepsilon)$ queries when a bound $K\ge F_φ$ is supplied, against $\widetilde O(m\min\{n^2,(K+n)/\varepsilon^2\})$ classically, and an adaptive quantum variant with the same instance dependence. These estimators are optimal in two regimes. For every fixed power weight $x^r$, $r\ge2$, and for the uniform-window mean, the worst-case complexities are $\widetildeΘ(n\sqrt m/\varepsilon)$ quantum and $Θ(n^2m)$ classical. On sparse instances, under an explicit split-leakage promise met by power and binomial weights of logarithmic degree and the promise $F_φ\le K$, they are $\widetildeΘ(\sqrt{mK}/\varepsilon)$ and $\widetildeΘ(m\min\{n^2,K/\varepsilon^2\})$. The classical lower bounds hold against fully adaptive algorithms, and fewer than $m$ such statistics cannot determine the positive-lifetime histogram. All bounds concern snapshot access; with an explicit update stream, near-linear full-barcode algorithms are known.

quant-pharXiv:2609.05813•Sep 8, 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
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.
Connectivity is a fundamental structural property of matroids, and has been studied algorithmically over 50 years. In 1974, Cunningham proposed a deterministic algorithm consuming O(n2)O(n^{2})O(n2) queries to the independence oracle to determine whether a matroid is connected. Since then, no algorithm, not even a random one, has worked better. To the best of our knowledge, the classical query complexity lower bound and the quantum complexity for this problem have not been considered. Thus, in this paper we are devoted to addressing these issues, and our contributions are threefold as follows: (i) First, we prove that the randomized query complexity of determining whether a matroid is connected is Ω(n2)Ω(n^2)Ω(n2) and thus the algorithm proposed by Cunningham is optimal in classical computing. (ii) Second, we present a quantum algorithm with O(n3/2)O(n^{3/2})O(n3/2) queries, which exhibits provable quantum speedups over classical ones. (iii) Third, we prove that any quantum algorithm requires Ω(n)Ω(n)Ω(n) queries, which indicates that quantum algorithms can achieve at most a quadratic speedup over classical ones. Therefore, we have a relatively comprehensive understanding of the potential of quantum computing in determining the connectedness of matroids.\
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….
Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle UAU_AUA​ and the right-hand side through a state-preparation oracle UbU_bUb​. The optimal query complexities of these two oracles are known separately: O(κlog⁡(1/ε))O(κ\log(1/\varepsilon))O(κlog(1/ε)) queries to UAU_AUA​ and O(κ/s)O(κ/s)O(κ/s) queries to UbU_bUb​, where s=α∥A−1b∥s=α\|A^{-1}b\|s=α∥A−1b∥. Whether a single algorithm can achieve both bounds simultaneously has remained open. We resolve this question affirmatively. Given a constant-factor estimate of sss, we give a quantum linear-system algorithm that prepares the normalized solution to error ε\varepsilonε using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to UAU_AUA​ and O(κ/s)O\left(κ/{s}\right)O(κ/s) queries to UbU_bUb​. The algorithm separates state preparation from precision refinement, so only the matrix-query count depends on the target accuracy. We also prove a matching same-instance worst-case lower bound: for every quantum linear-system algorithm and every solution-norm scale, there exists a single Hermitian instance on which that algorithm requires both Ω(κlog⁡(1/ε))Ω(κ\log(1/\varepsilon))Ω(κlog(1/ε)) matrix queries and Ω(κ/s)Ω(κ/s)Ω(κ/s) state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.
Let M\mathcal{M}M be a bridgeless matroid on ground set {1,...,n} and fM:{0,1}n→{0,1}f_{\mathcal{M}}: \{0,1\}^n \to \{0, 1\}fM​:{0,1}n→{0,1} be the indicator function of its independent sets. A folklore fact is that fMf_\mathcal{M}fM​ is evasive, i.e., D(fM)=nD(f_\mathcal{M}) = nD(fM​)=n where D(f) denotes the deterministic decision tree complexity of f. Here we prove query complexity lower bounds for fMf_\mathcal{M}fM​ in three stronger query models: (a) D⊕(fM)=Ω(n),D_\oplus(f_\mathcal{M}) = \Omega(n),D⊕​(fM​)=Ω(n), where D ⊕ (f) denotes the parity decision tree complexity of f; (b) R(fM)=Ω(n/log⁡n),R(f_\mathcal{M}) = \Omega(n / \log n),R(fM​)=Ω(n/logn), where R(f) denotes the bounded error randomized decision tree complexity of f; and (c) Q(fM)=Ω(n),Q(f_\mathcal{M}) = \Omega(\sqrt n),Q(fM​)=Ω(n​), where Q(f) denotes the bounded error quantum query complexity of f.
We study the query complexity of estimating scalar summaries of zigzag bar lifetimes from snapshot-adjacency bits. For graphs G1,…,GmG_1,\ldots,G_mG1​,…,Gm​ on nnn labeled vertices, let ℓb\ell_bℓb​ be the snapshot lifetime of a degree-one bar bbb of the intersection zigzag. For a probability generating function φ(x)=E[xR]φ(x)=\mathbb{E}[x^R]φ(x)=E[xR], the statistic Fφ=∑bφ(ℓb/m)F_φ=\sum_bφ(\ell_b/m)Fφ​=∑b​φ(ℓb​/m) includes normalized degree-rrr total persistence and the mean generalized rank over a uniform time window. An exact identity underlies our algorithm: sample RRR uniform times; the expected generalized rank between their minimum and maximum equals FφF_φFφ​. For graphs that rank is the circuit rank of an intersection graph, so a nonlinear barcode functional becomes an average of edge and component counts, and no barcode is computed. Without spectral-gap, homology-state, or QRAM assumptions, this gives a quantum estimator with additive error εn\varepsilon nεn and O~(m(K+n)/ε)\widetilde O(\sqrt{m(K+n)}/\varepsilon)O(m(K+n)​/ε) queries when a bound K≥FφK\ge F_φK≥Fφ​ is supplied, against O~(mmin⁡{n2,(K+n)/ε2})\widetilde O(m\min\{n^2,(K+n)/\varepsilon^2\})O(mmin{n2,(K+n)/ε2}) classically, and an adaptive quantum variant with the same instance dependence. These estimators are optimal in two regimes. For every fixed power weight xrx^rxr, r≥2r\ge2r≥2, and for the uniform-window mean, the worst-case complexities are Θ~(nm/ε)\widetildeΘ(n\sqrt m/\varepsilon)Θ(nm​/ε) quantum and Θ(n2m)Θ(n^2m)Θ(n2m) classical. On sparse instances, under an explicit split-leakage promise met by power and binomial weights of logarithmic degree and the promise Fφ≤KF_φ\le KFφ​≤K, they are Θ~(mK/ε)\widetildeΘ(\sqrt{mK}/\varepsilon)Θ(mK​/ε) and Θ~(mmin⁡{n2,K/ε2})\widetildeΘ(m\min\{n^2,K/\varepsilon^2\})Θ(mmin{n2,K/ε2}). The classical lower bounds hold against fully adaptive algorithms, and fewer than mmm such statistics cannot determine the positive-lifetime histogram. All bounds concern snapshot access; with an explicit update stream, near-linear full-barcode algorithms are known.
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.