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

Frontiers of Computer Science

Quantum speedup and limitations on matroid property problems

Xiaowei Huang, Jingquan Luo, Lvzhou Li

Published Dec 17, 2023• 5 citations
Publisher
DOI
10.1007/s11704-023-3130-9

Related papers

Quantum Speedup and Limitations on Matroid Property Problems

Xiaowei Huang, Jingquan Luo, Lvzhou Li

•Jan 1, 2022•0 citations

Quantum algorithms for learning hidden strings with applications to matroid problems

Xiaowei Huang, Shihao Zhang, Lvzhou Li

arXiv:2211.10667•Theoretical Computer Science•Oct 13, 2023•8 citations

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

Quantum and Classical Query Complexities for Determining Connectedness of Matroids

Xiaowei Huang, Shiguang Feng, Lvzhou Li

•Jan 1, 2023•0 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 states supported by matroids

Xiaowei Huang, Fei Shi, Lijun Zhang +1 more

In this work, we establish a structural correspondence between quantum states and matroid theory. This connection demonstrates that key properties of quantum states, including entanglement and measurement, can be characterized in purely combinatorial terms via matroids, despite the apparent conceptual distance between these two fields. Using this framework, we show that a matroid-supported state is genuinely entangled when its underlying matroid is connected. Moreover, a uniform superposition over all bases of a matroid is genuinely entangled if and only if the matroid is connected. We also demonstrate that a local measurement in the $Z$-basis on such a state yields another matroid-supported state, whose underlying matroid is a minor of the original one. Inspired by matroid duality, we further propose a notion of quantum state duality, uncovering a deep structural symmetry in state transformations.

quant-pharXiv:2607.15548•Physical Review A•Jul 20, 2026•0 citations
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.
In this work, we establish a structural correspondence between quantum states and matroid theory. This connection demonstrates that key properties of quantum states, including entanglement and measurement, can be characterized in purely combinatorial terms via matroids, despite the apparent conceptual distance between these two fields. Using this framework, we show that a matroid-supported state is genuinely entangled when its underlying matroid is connected. Moreover, a uniform superposition over all bases of a matroid is genuinely entangled if and only if the matroid is connected. We also demonstrate that a local measurement in the ZZZ-basis on such a state yields another matroid-supported state, whose underlying matroid is a minor of the original one. Inspired by matroid duality, we further propose a notion of quantum state duality, uncovering a deep structural symmetry in state transformations.