CS Paper Radar

Quantum Algorithms for Minimum Generating Set

Bireswar Das, Udit Kumar, Kavita Samant, Dhara Thakkar

cs.CC quant-phmath.GR ·submitted 2026-09-30 17:41 UTC · v1

Abstract

In this paper, we present a polynomial-time quantum algorithm for computing a minimum-sized generating set of solvable black-box groups. Next, we consider the class $Γ_d$ of black-box groups, where every non-abelian composition factor is isomorphic to a subgroup of the symmetric group $S_d$ for a fixed $d$. We design polynomial-time quantum algorithms to compute the direct product decomposition of abelian factor groups and solve the constructive membership problem for factor groups of groups from $Γ_d$. With the help of these algorithms, we design a quantum algorithm for computing a chief series of black-box groups from $Γ_d$. Using the chief series, we construct a polynomial-time quantum algorithm for computing minimum generating sets of black-box groups from $Γ_d$. Finally, we show that the minimum generating set problem for general black-box groups is in $\textrm{NP} \cap \textrm{coAM}$.

Closest papers

Nearest neighbours by meaning across the whole index.

Quantum Inversion of Units in Group Rings: Block Dimension, Not Commutativity, Governs Hardness

cs.CR quant-ph ·2026-09-07 ·Bhanwar Gupta
theory similarity 0.60
Abstract · 29 pages, 7 tables, 5 figures

Several public-key schemes base their security on the belief that inverting a unit of a group ring is hard. A recent result showed that this belief is false on a quantum computer when the group is abelian. To restore security, designers moved to non-abelian groups, especially dihedral groups, believing that the hardness of the dihedral hidden subgroup problem (HSP) would protect the scheme. This paper shows that unit inversion is a different problem and does not require an HSP solver. Instead, it can be solved by a change of basis that splits the group ring into small matrix blocks. We prove that unit inversion is polynomial-time, classically and quantumly, when an efficient generalized Fourier transform exists, the group ring is semisimple, and the largest matrix block has polynomial size. Dihedral group rings satisfy these conditions because their irreducible representations have dimension at most 2 and an efficient Fourier transform exists. We give an explicit reversible quantum circuit for the block-inversion step and validate it in a register-level simulator. We also identify the exact structural boundary where the method stops and propose a candidate construction in the surviving regime under a new, clearly stated security assumption. The constructive results are supported by reproducible software artifacts and experiments.

0.27

Coset Lifted Product Codes: Constructing Quantum LDPC Codes from Non-Normal Subgroup Actions

cs.IT quant-ph ·2026-10-08 ·Rajendra Prasad Rajpurohit, V. Lalitha, Shayan Srinivasa Garani
similarity 0.58
Abstract

We introduce coset lifted product (CLP) codes, a family of quantum LDPC codes that combine the protograph structure of lifted product codes with the coset action of Aydin, Tamo, and Barg \cite{AydinTamoBarg2026}. Given a finite group $G$, a subgroup $H \le G$ that need not be normal, a protograph $A$ over $\mathbb F_2[G]$, and a protograph $B$ over $\mathbb F_2[N_G(H)]$, the two protographs act on the cosets $G/H$ from the left and from the right to produce quantum CSS codes. Further, for groups of odd order, we give an explicit formula for the dimension as a sum over the irreducible representations $ρ$ of $G$ of hypergraph product dimensions. A search over $14,843$ pairs $(G,H)$ with $H$ restricted to be non-normal and $120 \le n \le 400$ yields certified codes that exceed the best published value of $Q=kd^2/n$ at check weights $6,7$ and $9$, i.e., we obtain $[[360,20,20]]$ at $w=6$, a $[[360,24,20]]$ code at $w=7$, and codes $[[252,16,18]]$ and $[[288,16,20]]$ at $w=9$. Our search also produce high-distance codes with parameters $[[168,10,14]], [[240,8,20]]$ at $w=6$ and $[[216,8,18]]$ at $w=7$.

0.18

Constructive Arithmetic Regularity for Abelian Groups

cs.DS ·2026-10-19 ·Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manmatha Roy
similarity 0.57
Abstract

The arithmetic regularity lemma of Green is a fundamental tool in additive combinatorics, providing a decomposition of arbitrary subsets of finite Abelian groups into pseudorandom pieces with respect to Fourier analysis. Over the years, it has found numerous applications in combinatorics, property testing, and theoretical computer science. However, Green's proof is existential, and many algorithmic applications require an efficient procedure for constructing the underlying regular decomposition. De, Nadimpalli, and Servedio (SODA 2022) developed a query-efficient constructive regularity framework over $\mathbb{F}_2^n$ and explicitly raised the problem of extending their dimension-independent sumset-estimation algorithm to other finite Abelian groups. In this work, we resolve this question for finite Abelian groups of constant torsion. We develop the first constructive version of Green's {\em Arithmetic Regularity Lemma} in this general setting. Given oracle access to a subset of the group, our algorithm computes an implicit description of a regular decomposition together with an oracle representation of a structured subset satisfying the guarantees of Green's lemma. The algorithm runs in time and query complexity polynomial in the regularity parameters and the tower bound, while remaining independent of the size of the ambient group. As applications, we obtain efficient algorithms for removing linear configurations and approximately counting linear images, including weighted sumsets and suitable matrix systems of Cauchy--Schwarz complexity one, over finite Abelian groups of constant torsion. Our results provide a unified algorithmic framework extending dimension-independent constructive arithmetic regularity and its applications beyond $\mathbb{F}_2^n$.

0.27

Word Length and Diameter in Permutation Groups

cs.CC math.GR ·2026-09-22 ·Markus Lohrey, Alexander Thumm
similarity 0.57
Abstract

In the binary diameter problem, the input consists of explicitly given permutations generating a finite group $G$ and a binary-encoded number $k$, and the question is whether every element of $G$ is a product of at most $k$ of the given generators. In the binary length problem, the input additionally contains a permutation $g \in G$, and the question is whether $g$ is such a product. We show that the binary diameter problem is PSPACE-complete, thereby confirming a conjecture of Lohrey and Rosowski (2023). Moreover, we show that PSPACE-hardness already holds for solvable groups of derived length at most 3, whereas the problem is $Π_2^{\mathrm{P}}$-complete for 2-step nilpotent groups. For the binary length problem, we establish a sharp complexity threshold: the problem is NP-complete for 2-step nilpotent groups, which extends a result of Lohrey and Rosowski for abelian groups, and PSPACE-complete for groups that are simultaneously 3-step nilpotent and metabelian, which strengthens the main result of Jerrum (1985). Finally, we show that the unary diameter problem, where $k$ is encoded in unary, is $Π_2^{\mathrm{P}}$-complete for generating sets of the full symmetric group, confirming another conjecture of Lohrey and Rosowski.

0.28

Quasi-Cyclic Qudit Lifted Product Codes with Almost Linear Minimum Distance

cs.IT quant-ph ·2026-11-11 ·Shantom K. Borah, Abhinav Vaishya, V. Lalitha, Asit Kumar Pradhan, Bane Vasic +1 more
similarity 0.56
Abstract · 43 pages, 6 figures

Quantum low-density parity-check (QLDPC) codes are a promising route to fault-tolerant quantum computation with low overhead, and qudits offer advantages over qubits including more efficient information representation, improved magic state distillation, and richer algebraic structure for code design. Asymptotically good QLDPC codes arise from the lifted product (LP) construction with non-abelian lifts, but cyclic lifts remain attractive in practice because the resulting quasi-cyclic codes have circulant structure that hardware decoders exploit, which matters especially for non-binary decoders with costly check node operations. We introduce a qudit generalization of the LP construction over cyclic group algebras, which extends hypergraph product and LP codes to arbitrary prime-power dimensions and yields quasi-cyclic qudit CSS codes for every stacking order. We bound encoding rates via a connection to additive codes, and show that in the fully stacked case, qudit LP codes built from lifted Tanner codes on expander graphs form families with $Θ(\log N)$ logical qudits and almost linear minimum distance $Θ(N/\log N)$, via a distance bound that holds for a general class of LP factors. We also study an additive decoder for general qudit codes and a linear merged-syndrome decoder for fully stacked codes. Monte Carlo simulations under a depolarizing channel with equal symbol error probability show that qudit codes achieve lower frame error rates than comparable qubit codes, and that the linear decoder gives further gains for fully stacked codes.

0.24

Quantum Bicycle LDPC Codes with High $kd^2/n$ from Divisor-Driven Search

cs.IT quant-ph ·2026-08-10 ·Liangdong Lu, Guanmin Guo, Yang Liu, Ruipan Yang
similarity 0.56
Abstract · v2: Added references on decoding comparison

Bicycle (two-block circulant) quantum low-density parity-check (LDPC) codes include some of the best known small quantum codes, yet their design has relied on group-algebra formulations in which the dimension and distance are accessible only through matrix computation. We show that in the cyclic case the construction collapses into the polynomial ring $\F_2[x]/(x^{l}-1)$: self-orthogonality is automatic, the quantum dimension is read off from a polynomial gcd, and the minimum distance is certified exactly through the Calderbank correspondence to additive codes over $\F_4$, turning code search into an algebraically pre-filtered enumeration that reaches parameter regimes poorly covered by existing tables. A computer search based on this framework recovers the short codes $[[42,12,4]]_2$ and $[[62,12,4]]_2$ and produces a family of codes with competitive figure of merit $kd^2/n$, including $[[66,20,7]]_2$ with $kd^2/n=14.85$, above the bivariate bicycle code $[[144,12,12]]_2$ ($kd^2/n=12$) at less than half the block length, together with $[[46,2,8]]_2$, $[[66,2,9]]_2$, $[[66,4,8]]_2$, $[[66,6,8]]_2$ and, at $n=90$, $[[90,16,6]]_2$, $[[90,18,6]]_2$, $[[90,20,6]]_2$. An exhaustive census at $n=48$ delineates the boundary of this picture: we exhibit a $[[48,10,6]]_2$ code from a minimal $48$-element group (the Aydin--Tamo--Barg realization uses $72$ elements), and prove that distance $5$ forces a stabilizer-rank loss, which excludes $[[48,10,5]]_2$ from the weight-$8$ symmetric coset family. The framework thus opens a systematic route to bicycle-type quantum LDPC codes beyond the reach of group-theoretic searches, and identifies exactly where genuinely coset-theoretic phenomena begin.

0.32

Hidden parabolic subgroups of $\mathrm{GL}_n$ over finite chain rings

cs.CC quant-ph ·2026-10-20 ·Muhammad Imran
similarity 0.56
Abstract · Added author details

We give a bounded-error quantum polynomial-time algorithm for finding hidden parabolic subgroups of $\mathrm{GL}_n(R)$ over any effectively presented finite chain ring $R$. We call auxiliary group elements or subgroups used to extract information through oracle queries \emph{probes}. For chain length at least two, elementary abelian socle probes first recover the complete flag modulo the maximal ideal. When the residue field has size $q\ge3$, we reconstruct the flag recursively, lifting rank-one terminal members one digit at a time. The intermediate digits reduce to abelian hidden subgroup problems, while the final digit is a finite-field multiple-shift problem solved using learning from subset and Fourier sampling. For $q=2$, where distinct flags can have the same stabilizer, we instead lift the conjugate parabolic subgroup through the congruence filtration. A final linear system determines it modulo normalizer directions. The algorithm outputs generators with probability at least $1-ε$ in time $\mathrm{poly}(n,\log|R|,\log(1/ε))$. Consequences include $\mathrm{GL}_n(\mathbb{Z}/N\mathbb{Z})$ for every $N\ge2$ and, with an explicit maximal-order presentation, $\mathrm{GL}_n(\mathcal{O}_K/N\mathcal{O}_K)$ for number fields $K$.

0.19

Quantum Approximation Complexity of Classical Optimization Problems

cs.CC quant-ph ·2026-10-07 ·Stuart Hadfield
benchmark similarity 0.55
Abstract

Classical approximation complexity asks what solution quality can be guaranteed with polynomial-time computation. The classes APX, PTAS, and FPTAS distinguish a fixed approximation ratio, approximation to any fixed accuracy, and approximation schemes whose running time is also polynomial in inverse accuracy. Their randomized counterparts are R-APX, R-PTAS, and R-FPTAS. We define bounded-error quantum counterparts BQ-APX, BQ-PTAS, and BQ-FPTAS. Membership requires a uniform quantum algorithm that, on every input, returns a feasible classical solution achieving at least the claimed approximation ratio with probability at least 2/3. Scores (objective values) must be efficiently classically computable. Running time includes parameter selection, preparation, measurement, decoding, and repetition. Many quantum optimization methods are used heuristically, and high benchmark scores alone do not establish these guarantees. We further establish a conditional hierarchy for logarithmic, polynomial, and exponential approximation factors. Assuming NP $\nsubseteq$ BQP, the quantum classes form a strict hierarchy. Problems based on prime factorization and discrete logarithms give conditional quantum-classical separations. Certified Maximum Order has an exact quantum algorithm, while any randomized polynomial-time algorithm guaranteeing at least an inverse-polynomial approximation ratio on every input would yield efficient factoring. Discrete-Logarithm Fitting has an exact quantum algorithm and a deterministic one-half approximation, but any fixed improvement over one half would give a randomized polynomial-time algorithm for the safe-prime discrete logarithm problem. Our results show, under explicit complexity assumptions, that quantum computation can improve worst-case approximation guarantees. A quantum-classical gap for common problems such as MaxCut or MaxSAT remains open.

0.05