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

arXiv:2211.10667 · Theoretical Computer Science

Quantum algorithms for learning hidden strings with applications to matroid problems

Xiaowei Huang, Shihao Zhang, Lvzhou Li

Published Oct 13, 2023• 8 citations
arXivHTMLPDF
DOI
10.1016/j.tcs.2023.114255

Related papers

Quantum speedup and limitations on matroid property problems

Xiaowei Huang, Jingquan Luo, Lvzhou Li

Frontiers of Computer Science•Dec 17, 2023•5 citations

Quantum Speedup and Limitations on Matroid Property Problems

Xiaowei Huang, Jingquan Luo, Lvzhou Li

•Jan 1, 2022•0 citations

Quantum algorithm for learning secret strings and its experimental demonstration

Yongzhen Xu, Shihao Zhang, Lvzhou Li

arXiv:2206.11221•Physica A Statistical Mechanics and its Applications•Dec 5, 2022•6 citations

Learning quantum symmetries

Isaac Holt, Sathyawageeswar Subramanian

Quantum algorithms are powerful tools for finding symmetries of classical objects, most famously through Shor's algorithm and the Hidden Subgroup Problem (HSP). In this work, we study quantum algorithms for learning symmetries of \emph{quantum} objects. Existing work in this area centres on the recently introduced State Hidden Subgroup Problem (StateHSP), a quantum generalisation of HSP in which the task is to learn the symmetry subgroup of a quantum state. We develop efficient quantum algorithms for non-abelian StateHSP when the hidden subgroup is normal and the ambient group belongs to a broad class of non-abelian groups, extending the previous general theory beyond the abelian setting. StateHSP learns \emph{Bose} symmetries, under which a state must be invariant exactly under the action of the symmetry group. In quantum mechanics, however, physically equivalent pure states are defined only up to global phase. Motivated by this, we introduce a natural notion of \emph{Anyonic} state symmetry learning, based on invariance up to global phase. We give an efficient quantum algorithm by reducing the problem to StateHSP, where the reduction rests on a new correspondence between linearisations of projective representations and linear error-correcting codes. As an application, we obtain an improved algorithm for learning stabiliser groups of mixed qudit states of arbitrary local dimension. Finally, we introduce symmetry learning problems for other quantum objects, including unitaries, Hamiltonians, and finite collections of states, and give efficient algorithms for them by reduction to state symmetry learning. Together, these results broaden the scope of state symmetry learning as a common algorithmic primitive for learning quantum symmetries.

quant-pharXiv:2609.38085•Sep 30, 2026•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 Algorithms for String Processing

Farid Mansurovich Ablayev, Marat Ablayev, Kamil Ravilevich Khadiev +2 more

arXiv:2012.00372•Lecture notes in computational science and engineering•Oct 21, 2021•19 citations
Quantum algorithms are powerful tools for finding symmetries of classical objects, most famously through Shor's algorithm and the Hidden Subgroup Problem (HSP). In this work, we study quantum algorithms for learning symmetries of \emph{quantum} objects. Existing work in this area centres on the recently introduced State Hidden Subgroup Problem (StateHSP), a quantum generalisation of HSP in which the task is to learn the symmetry subgroup of a quantum state. We develop efficient quantum algorithms for non-abelian StateHSP when the hidden subgroup is normal and the ambient group belongs to a broad class of non-abelian groups, extending the previous general theory beyond the abelian setting. StateHSP learns \emph{Bose} symmetries, under which a state must be invariant exactly under the action of the symmetry group. In quantum mechanics, however, physically equivalent pure states are defined only up to global phase. Motivated by this, we introduce a natural notion of \emph{Anyonic} state symmetry learning, based on invariance up to global phase. We give an efficient quantum algorithm by reducing the problem to StateHSP, where the reduction rests on a new correspondence between linearisations of projective representations and linear error-correcting codes. As an application, we obtain an improved algorithm for learning stabiliser groups of mixed qudit states of arbitrary local dimension. Finally, we introduce symmetry learning problems for other quantum objects, including unitaries, Hamiltonians, and finite collections of states, and give efficient algorithms for them by reduction to state symmetry learning. Together, these results broaden the scope of state symmetry learning as a common algorithmic primitive for learning quantum symmetries.
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.