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

Quantum and Classical Query Complexities for Determining Connectedness of Matroids

Xiaowei Huang, Shiguang Feng, Lvzhou Li

Published Jan 1, 2023• 0 citations
Publisher
DOI
10.2139/ssrn.4641131

Related papers

Quantum and classical query complexities for determining connectedness of matroids

Xiaowei Huang, Shiguang Feng, Lvzhou Li

arXiv:2306.12103•Journal of Computer and System Sciences•Jan 7, 2026•3 citations

Query Complexity of Matroids

Raghav Kulkarni, Miklós Sántha

Lecture notes in computer science•Jan 1, 2013•13 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

The quantum query complexity of the determinant

Sebastian Dörn, Thomas Thierauf

Information Processing Letters•Nov 20, 2008•8 citations

Quantum Speedup and Limitations on Matroid Property Problems

Xiaowei Huang, Jingquan Luo, Lvzhou Li

This paper initiates the study of quantum algorithms for matroid property problems. It is shown 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 for the decision problem of deciding whether a matroid is uniform or Eulerian, by giving a uniform lower bound $Ω(\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, an asymptotically optimal quantum algorithm is proposed which achieves the lower bound, and for the girth problem, an almost optimal quantum algorithm is given with query complexity $O(\log n\sqrt{\binom{n}{\lfloor n/2\rfloor}})$. In addition, for the paving matroid decision problem, a lower bound $Ω(\sqrt{\binom{n}{\lfloor n/2\rfloor}/n})$ on the query complexity is obtained, and an $O(\sqrt{\binom{n}{\lfloor n/2\rfloor}})$ quantum algorithm is presented.

arXiv:2111.12900•Nov 25, 2021•2 citations

Quantum Speedup and Limitations on Matroid Property Problems

Xiaowei Huang, Jingquan Luo, Lvzhou Li

•Jan 1, 2022•0 citations
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….
This paper initiates the study of quantum algorithms for matroid property problems. It is shown 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 for the decision problem of deciding whether a matroid is uniform or Eulerian, by giving a uniform lower bound Ω((n⌊n/2⌋))Ω(\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, an asymptotically optimal quantum algorithm is proposed which achieves the lower bound, and for the girth problem, an almost optimal quantum algorithm is given 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, a lower bound Ω((n⌊n/2⌋)/n)Ω(\sqrt{\binom{n}{\lfloor n/2\rfloor}/n})Ω((⌊n/2⌋n​)/n​) on the query complexity is obtained, and an O((n⌊n/2⌋))O(\sqrt{\binom{n}{\lfloor n/2\rfloor}})O((⌊n/2⌋n​)​) quantum algorithm is presented.