Quantum speedup and limitations on matroid property problems

Abstract

Matroid theory has been developed to be a mature branch of mathematics and has extensive applications in combinatorial optimization, algorithm design and so on. On the other hand, quantum computing has attracted much attention and has been shown to surpass classical computing on solving some computational problems. Surprisingly, crossover studies of the two fields seem to be missing in the literature. 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 \mathrm{\Omega }(\sqrt{(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })}) on the query complexity of 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{(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })}). In addition, for the paving matroid decision problem, a lower bound \mathrm{\Omega }(\sqrt{(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })/n}) on the query complexity is obtained, and an O(\sqrt{(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })}) quantum algorithm is presented.

Graphical abstract

Keywords

quantum computing / matroid / quantum algorithm / quantum query complexity

Xiaowei Huang received his BS degree in computer science and technology from East China University Of Science and Technology, China in 2010. He is currently pursuing his PhD degree in computer science at Sun Yat-sen University, China. His main research include quantum computing, query complexity and matroid theory

Jingquan Luo obtained his bachelor’s degree from Sun Yat-sen University, China. His research interests include quantum computing and quantum algorithms

Lvzhou Li received his PhD degree in Computer Science from Sun Yat-sen University, China in 2009 and then worked in Sun Yat-sen University, China. Now he is a professor of the School of Computer Science and Engineering, Sun Yat-sen University, China. His research interests are quantum algorithm and complexity, quantum machine learning, quantum circuit synthesis and optimization

References

[1] Whitney H . On the abstract properties of linear dependence. American Journal of Mathematics, 1935, 57( 3): 509–533

[2] Edmonds J . Matroids and the greedy algorithm. Mathematical Programming, 1971, 1( 1): 127–136

[3] Lawler E L. Combinatorial Optimization: Networks and Matroids. New York: Holt, Rinehart and Winston, 1976

[4] Bassoli R, Marques H, Rodriguez J, Shum K W, Tafazolli R . Network coding theory: a survey. IEEE Communications Surveys & Tutorials, 2013, 15( 4): 1950–1978

[5] Iri M. Applications of matroid theory. In: Bachem A, Korte B, Grötschel M, eds. Mathematical Programming the State of the Art. Berlin: Springer, 1982, 158−201

[6] Kulkarni R, Santha M. Query complexity of matroids. In: Proceedings of the 8th International Conference on Algorithms and Complexity. 2013, 300−311

[7] Aghaei M R S, Zukarnain Z A, Mamat A, Zainuddin H. A quantum algorithm for minimal spanning tree. In: Proceedings of 2008 International Symposium on Information Technology. 2008, 1−6

[8] O’Quinn W, Mao S. Solving the minimum spanning tree problem with a quantum annealer. In: Proceedings of 2020 IEEE Globecom Workshops (GC Wkshps). 2020, 1−6

[9] Ambainis A, Špalek R. Quantum algorithms for matching and network flows. In: Proceedings of the 23rd Annual Conference on Theoretical Aspects of Computer Science. 2006, 172−183

[10] Dörn S . Quantum algorithms for matching problems. Theory of Computing Systems, 2009, 45( 3): 613–628

[11] Hamoudi Y, Rebentrost P, Rosmanis A, Santha M. Quantum and classical algorithms for approximate submodular function minimization. Quantum Information and Computation, 2019, 19(15−16): 1325−1349

[12] Amy M, Maslov D, Mosca M . Polynomial-time T-depth optimization of clifford+T circuits via matroid partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014, 33( 10): 1476–1489

[13] Mann R L . Simulating quantum computations with tutte polynomials. npj Quantum Information, 2021, 7: 141

[14] Oxley J. Matroid Theory. 2nd ed. New York: Oxford University Press, 2011

[15] Knuth D E . The asymptotic number of geometries. Journal of Combinatorial Theory, Series A, 1974, 16( 3): 398–400

[16] Piff M J, Welsh D J A . On the number of combinatorial geometries. Bulletin of the London Mathematical Society, 1971, 3( 1): 55–56

[17] Piff M J . An upper bound for the number of matroids. Journal of Combinatorial Theory, Series B, 1973, 14( 3): 241–245

[18] Mayhew D . Matroid complexity and nonsuccinct descriptions. SIAM Journal on Discrete Mathematics, 2008, 22( 2): 455–466

[19] Robinson G C, Welsh D J A . The computational complexity of matroid properties. Mathematical Proceedings of the Cambridge Philosophical Society, 1980, 87( 1): 29–45

[20] Jensen P M, Korte B . Complexity of matroid property algorithms. SIAM Journal on Computing, 1982, 11( 1): 184–190

[21] Hausmann D, Korte B . Lower bounds on the worst-case complexity of some oracle algorithms. Discrete Mathematics, 1978, 24( 3): 261–276

[22] Nielsen M A, Chuang I L. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge: Cambridge University Press, 2010

[23] Beals R, Buhrman H, Cleve R, Mosca M, De Wolf R. Quantum lower bounds by polynomials. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science. 1998, 352−361

[24] Grover L K. A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing. 1996, 212−219

[25] Boyer M, Brassard G, Høyer P, Tapp A. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics, 1998, 46(4−5): 493−505

[26] Ambainis A. Quantum lower bounds by quantum arguments. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. 2000, 636−643

[27] Blackburn J E, Crapo H H, Higgs D A . A catalogue of combinatorial geometries. Mathematics of Computation, 1973, 27( 121): 155–166

[28] Crapo H H, Rota G C. On the Foundations of Combinatorial Theory: Combinatorial Geometries. Cambridge: MIT Press, 1970

[29] Mayhew D, Newman M, Welsh D, Whittle G . On the asymptotic proportion of connected matroids. European Journal of Combinatorics, 2011, 32( 6): 882–890

[30] Zalka C . Grover’s quantum searching algorithm is optimal. Physical Review A, 1999, 60( 4): 2746–2751

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant Nos. 62272492, 61772565), and the Guangdong Basic and Applied Basic Research Foundation (No. 2020B1515020050).

RIGHTS & PERMISSIONS

2024 Higher Education Press