arXiv:2111.12900

Quantum Speedup and Limitations on Matroid Property Problems

Xiaowei Huang, Jingquan Luo, Lvzhou Li

Published Nov 25, 2021• 0 citations

Abstract

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.

DOI: 10.48550/arxiv.2111.12900

Related papers

Quantum Speedup and Limitations on Matroid Properties.

Xiaowei Huang, Jingquan Luo, Lvzhou Li

Nov 25, 20211 citation

Quantum Speedups for Testing Similar Means

Chengshen Gao, Yongzhen Xu, Shenggen Zheng +1 more

quant-pharXiv:2608.00741Aug 4, 20260 citations

Quantum and classical query complexities for determining connectedness of matroids

Xiaowei Huang, Shiguang Feng, Lvzhou Li

arXiv:2306.12103Jun 21, 20230 citations

Quantum Query Complexity and Span Programs from Pre-Geometry

Justin Roy Cox, Neil Epstein, Zhirui Hu +2 more

quant-pharXiv:2610.03914Oct 6, 20260 citations

The Quantum Query Complexity of Algebraic Properties

Sebastian Doern, Thomas Thierauf

arXiv:0705.1446May 10, 20079 citations

Quadratic quantum speedup for perceptron training

Pengcheng Liao, Barry C. Sanders, Tim Byrnes

arXiv:2109.04695Physical Review ADec 9, 20246 citations

arXiv:2111.12900

Quantum Speedup and Limitations on Matroid Property Problems

Xiaowei Huang, Jingquan Luo, Lvzhou Li

Published Nov 25, 2021• 0 citations

arXiv HTML PDF

Abstract

Ω(\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.

DOI: 10.48550/arxiv.2111.12900

Related papers

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.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, 20211 citation

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.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.00741Aug 4, 20260 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.\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.12103Jun 21, 20230 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$ .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.03914Oct 6, 20260 citations

The Quantum Query Complexity of Algebraic Properties

Sebastian Doern, Thomas Thierauf

We present quantum query complexity bounds for testing algebraic properties. For a set S and a binary operation on S, we consider the decision problem whether $S$ is a semigroup or has an identity element. If S is a monoid, we want to decide whether S is a group. We present quantum algorithms for these problems that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by Magniez, Nayak, Roland, and Santha that improves the previous bounds by Ambainis and Szegedy. We also present several lower bounds for testing algebraic properties.We present quantum query complexity bounds for testing algebraic properties. For a set S and a binary operation on S, we consider the decision problem whether $S$ is a semigroup or has an identity element. If S is a monoid, we want to decide whether S is a group. We present quantum algorithms for these problems that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by Magniez, Nayak, Roland, and Santha that improves the previous bounds by Ambainis and Szegedy. We also present several lower bounds for testing algebraic properties.

arXiv:0705.1446May 10, 20079 citations

Quadratic quantum speedup for perceptron training

Pengcheng Liao, Barry C. Sanders, Tim Byrnes

Perceptrons, which perform binary classification, are the fundamental building blocks of neural networks. Given a data set of size $N$ and margin $\ensuremath{\gamma}$ (how well the given data are separated), the query complexity of the best-known quantum training algorithm scales as either $(\sqrt{N}/{\ensuremath{\gamma}}^{2})log(1/{\ensuremath{\gamma}}^{2})$ or $N/\sqrt{\ensuremath{\gamma}}$, which is achieved by a hybrid of classical and quantum search. In this paper, we improve the version space quantum training method for perceptrons such that the query complexity of our algorithm scales as $\sqrt{N/\ensuremath{\gamma}}$. This is achieved by constructing an oracle for the perceptrons using quantum counting of the number of data elements that are correctly classified. Once such an oracle is constructed, bounded-error quantum search can be used to search over the hyperplane instances. The optimality of our algorithm is proven by reducing the evaluation of a two-level and-or tree (for which the query complexity lower bound is known) to a multicriterion search. Our quantum training algorithm can be generalized to train more complex machine learning models such as neural networks, which are built on a large number of perceptrons.Perceptrons, which perform binary classification, are the fundamental building blocks of neural networks. Given a data set of size $N$ and margin $\ensuremath{\gamma}$ (how well the given data are separated), the query complexity of the best-known quantum training algorithm scales as either $(\sqrt{N}/{\ensuremath{\gamma}}^{2})log(1/{\ensuremath{\gamma}}^{2})$ or $N/\sqrt{\ensuremath{\gamma}}$, which is achieved by a hybrid of classical and quantum search. In this paper, we improve the version space quantum training method for perceptrons such that the query complexity of our algorithm scales as $\sqrt{N/\ensuremath{\gamma}}$. This is achieved by constructing an oracle for the perceptrons using quantum counting of the number of data elements that are correctly classified. Once such an oracle is constructed, bounded-error quantum search can be used to search over the hyperplane instances. The optimality of our algorithm is proven by reducing the evaluation of a two-level and-or tree (for which the query complexity lower bound is known) to a multicriterion search. Our quantum training algorithm can be generalized to train more complex machine learning models such as neural networks, which are built on a large number of perceptrons.

arXiv:2109.04695Physical Review ADec 9, 20246 citations

Ω(\sqrt{\binom{n}{\lfloor n/2\rfloor}})

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.

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

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.

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

\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

We present quantum query complexity bounds for testing algebraic properties. For a set S and a binary operation on S, we consider the decision problem whether

S

is a semigroup or has an identity element. If S is a monoid, we want to decide whether S is a group. We present quantum algorithms for these problems that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by Magniez, Nayak, Roland, and Santha that improves the previous bounds by Ambainis and Szegedy. We also present several lower bounds for testing algebraic properties.

Perceptrons, which perform binary classification, are the fundamental building blocks of neural networks. Given a data set of size

N

and margin $\ensuremath{\gamma}$ (how well the given data are separated), the query complexity of the best-known quantum training algorithm scales as either $(\sqrt{N}/{\ensuremath{\gamma}}^{2})log(1/{\ensuremath{\gamma}}^{2})$ or $N/\sqrt{\ensuremath{\gamma}}$, which is achieved by a hybrid of classical and quantum search. In this paper, we improve the version space quantum training method for perceptrons such that the query complexity of our algorithm scales as $\sqrt{N/\ensuremath{\gamma}}$. This is achieved by constructing an oracle for the perceptrons using quantum counting of the number of data elements that are correctly classified. Once such an oracle is constructed, bounded-error quantum search can be used to search over the hyperplane instances. The optimality of our algorithm is proven by reducing the evaluation of a two-level and-or tree (for which the query complexity lower bound is known) to a multicriterion search. Our quantum training algorithm can be generalized to train more complex machine learning models such as neural networks, which are built on a large number of perceptrons.