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 Speedup and Limitations on Matroid Properties.

Xiaowei Huang, Jingquan Luo, Lvzhou Li

Published Nov 25, 2021• 1 citation
OpenAlex

Abstract

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.

Related papers

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•0 citations

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

Can graph properties have exponential quantum speedup?

Andrew M. Childs, Daochen Wang

Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity $R$ of any graph property $\mathcal{P}$ has $R(\mathcal{P}) = O(Q(\mathcal{P})^{6})$, where $Q$ is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove $R(\mathcal{P}) = O(Q(\mathcal{P})^{3l})$ for any $l$-uniform hypergraph property $\mathcal{P}$ in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.

arXiv:2001.10520•Jan 28, 2020•2 citations

Quantum Speedups for Testing Similar Means

Chengshen Gao, Yongzhen Xu, Shenggen Zheng +1 more

Property testing of distributions is a central topic in information theory, learning theory, and statistics. While quantum algorithms are known to offer significant speedups for property testing of a single distribution or a pair of distributions, it is unclear whether quantum algorithms provide speedups for property testing of $m$ ($m\geq 3$) distributions. This work focuses on quantum algorithms for testing whether $m$ distributions have similar means or are $ε$-far from mean similarity under two models. In the query model, the algorithm can choose which distribution to sample from, whereas in the sampling model, the distributions are selected uniformly. We design quantum algorithms with complexities $\tilde{O}(1/ε)$ (the $\tilde{O}$ notation hides poly-logarithmic factors) and $\tilde{O}(\sqrt{m}/ε)$ in the query and sampling models, respectively, achieving quadratic speedups over the classical counterparts. We further establish quantum lower bounds of $Ω\left(1/ε\right)$ and $Ω\rbra{m^{1/3}+\frac{m^{1/4}}ε}$ for the query model and the sampling model, demonstrating the optimality of our quantum algorithms in terms of the dependence on $ε$ up to logarithmic factors.

quant-pharXiv:2608.00741•Aug 4, 2026•0 citations

Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks

Harry Buhrman, Bruno Loff, Subhasree Patro +1 more

Many computational problems are subject to a quantum speed-up: one might find that a problem having an O(n^3)-time or O(n^2)-time classic algorithm can be solved by a known O(n^1.5)-time or O(n)-time quantum algorithm. The question naturally arises: how much quantum speed-up is possible? The area of fine-grained complexity allows us to prove optimal lower-bounds on the complexity of various computational problems, based on the conjectured hardness of certain natural, well-studied problems. This theory has recently been extended to the quantum setting, in two independent papers by Buhrman, Patro, and Speelman (arXiv:1911.05686), and by Aaronson, Chia, Lin, Wang, and Zhang (arXiv:1911.01973). In this paper, we further extend the theory of fine-grained complexity to the quantum setting. A fundamental conjecture in the classical setting states that the 3SUM problem cannot be solved by (classical) algorithms in time O(n^{2-a}), for any a>0. We formulate an analogous conjecture, the Quantum-3SUM-Conjecture, which states that there exist no sublinear O(n^{1-b})-time quantum algorithms for the 3SUM problem. Based on the Quantum-3SUM-Conjecture, we show new lower-bounds on the time complexity of quantum algorithms for several computational problems. Most of our lower-bounds are optimal, in that they match known upper-bounds, and hence they imply tight limits on the quantum speedup that is possible for these problems.

arXiv:2106.02005•Leibniz international proceedings in informatics•Jun 3, 2021•9 citations
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.
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.
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 computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity RRR of any graph property P\mathcal{P}P has R(P)=O(Q(P)6)R(\mathcal{P}) = O(Q(\mathcal{P})^{6})R(P)=O(Q(P)6), where QQQ is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove R(P)=O(Q(P)3l)R(\mathcal{P}) = O(Q(\mathcal{P})^{3l})R(P)=O(Q(P)3l) for any lll-uniform hypergraph property P\mathcal{P}P in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.
Property testing of distributions is a central topic in information theory, learning theory, and statistics. While quantum algorithms are known to offer significant speedups for property testing of a single distribution or a pair of distributions, it is unclear whether quantum algorithms provide speedups for property testing of mmm (m≥3m\geq 3m≥3) distributions. This work focuses on quantum algorithms for testing whether mmm distributions have similar means or are εεε-far from mean similarity under two models. In the query model, the algorithm can choose which distribution to sample from, whereas in the sampling model, the distributions are selected uniformly. We design quantum algorithms with complexities O~(1/ε)\tilde{O}(1/ε)O~(1/ε) (the O~\tilde{O}O~ notation hides poly-logarithmic factors) and O~(m/ε)\tilde{O}(\sqrt{m}/ε)O~(m​/ε) in the query and sampling models, respectively, achieving quadratic speedups over the classical counterparts. We further establish quantum lower bounds of Ω(1/ε)Ω\left(1/ε\right)Ω(1/ε) and $Ω\rbra{m^{1/3}+\frac{m^{1/4}}ε}$ for the query model and the sampling model, demonstrating the optimality of our quantum algorithms in terms of the dependence on εεε up to logarithmic factors.
Many computational problems are subject to a quantum speed-up: one might find that a problem having an O(n^3)-time or O(n^2)-time classic algorithm can be solved by a known O(n^1.5)-time or O(n)-time quantum algorithm. The question naturally arises: how much quantum speed-up is possible? The area of fine-grained complexity allows us to prove optimal lower-bounds on the complexity of various computational problems, based on the conjectured hardness of certain natural, well-studied problems. This theory has recently been extended to the quantum setting, in two independent papers by Buhrman, Patro, and Speelman (arXiv:1911.05686), and by Aaronson, Chia, Lin, Wang, and Zhang (arXiv:1911.01973). In this paper, we further extend the theory of fine-grained complexity to the quantum setting. A fundamental conjecture in the classical setting states that the 3SUM problem cannot be solved by (classical) algorithms in time O(n^{2-a}), for any a>0. We formulate an analogous conjecture, the Quantum-3SUM-Conjecture, which states that there exist no sublinear O(n^{1-b})-time quantum algorithms for the 3SUM problem. Based on the Quantum-3SUM-Conjecture, we show new lower-bounds on the time complexity of quantum algorithms for several computational problems. Most of our lower-bounds are optimal, in that they match known upper-bounds, and hence they imply tight limits on the quantum speedup that is possible for these problems.