Zero sum subsequences and hidden subgroups
- URL: http://arxiv.org/abs/2304.08376v1
- Date: Mon, 17 Apr 2023 15:40:30 GMT
- Title: Zero sum subsequences and hidden subgroups
- Authors: Muhammad Imran and Gabor Ivanyos
- Abstract summary: We solve the hidden subgroup problem in nilpotent groups by transforming a subgroup to its images in the quotient groups by the members of a central series.
Knowing this image allows one to descend to a proper subgroup unless the hidden subgroup is the full group.
We present a new deterministic time algorithm for the latter problem in the case of the size of the field is constant.
- Score: 2.5204420653245245
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose a method for solving the hidden subgroup problem in nilpotent
groups. The main idea is iteratively transforming the hidden subgroup to its
images in the quotient groups by the members of a central series, eventually to
its image in the commutative quotient of the original group; and then using an
abelian hidden subgroup algorithm to determine this image. Knowing this image
allows one to descend to a proper subgroup unless the hidden subgroup is the
full group. The transformation relies on finding zero sum subsequences of
sufficiently large sequences of vectors over finite prime fields. We present a
new deterministic polynomial time algorithm for the latter problem in the case
when the size of the field is constant. The consequence is a polynomial time
exact quantum algorithm for the hidden subgroup problem in nilpotent groups
having constant nilpotency class and whose order only have prime factors also
bounded by a constant.
Related papers
- Discover and Mitigate Multiple Biased Subgroups in Image Classifiers [45.96784278814168]
Machine learning models can perform well on in-distribution data but often fail on biased subgroups that are underrepresented in the training data.
We propose Decomposition, Interpretation, and Mitigation (DIM) to address this problem.
Our approach decomposes the image features into multiple components that represent multiple subgroups.
arXiv Detail & Related papers (2024-03-19T14:44:54Z) - Clustered Orienteering Problem with Subgroups [6.961946145048321]
Clustered Orienteering Problem with Subgroups (COPS)
We show that our new formulation has the ability to model and solve two previous well-known variants.
arXiv Detail & Related papers (2023-12-26T18:28:25Z) - Concomitant Group Testing [49.50984893039441]
We introduce a variation of the group testing problem capturing the idea that a positive test requires a combination of multiple types'' of item.
The goal is to reliably identify all of the semi-defective sets using as few tests as possible.
Our algorithms are distinguished by (i) whether they are deterministic (zero-error) or randomized (small-error), and (ii) whether they are non-adaptive, fully adaptive, or have limited adaptivity.
arXiv Detail & Related papers (2023-09-08T09:11:12Z) - Discovering Sparse Representations of Lie Groups with Machine Learning [55.41644538483948]
We show that our method reproduces the canonical representations of the generators of the Lorentz group.
This approach is completely general and can be used to find the infinitesimal generators for any Lie group.
arXiv Detail & Related papers (2023-02-10T17:12:05Z) - A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup
Problem [1.189332466445755]
We present a-time quantum algorithm for the Hidden Subgroup Problem over $mathbbD_2n$.
By focusing on structure encoded in the codomain of the problem, we develop an algorithm which uses this structure to direct a "walk" down the subgroup lattice of $mathbbD_2n$ terminating at the hidden subgroup.
arXiv Detail & Related papers (2022-02-19T23:51:15Z) - An exact quantum hidden subgroup algorithm and applications to solvable
groups [2.5204420653245245]
We present a time exact quantum algorithm for the hidden subgroup problem in $Z_mkn$.
We also present applications to compute the structure of abelian and solvable groups whose order has the same (but possibly unknown) prime factors solvable as m.
arXiv Detail & Related papers (2022-02-08T18:22:35Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
Clustering is a fundamental primitive in unsupervised learning.
Recent work has established lower bounds against the class of low-degree methods.
We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
arXiv Detail & Related papers (2021-12-07T18:50:17Z) - The dihedral hidden subgroup problem [0.0]
We give an exposition of the hidden problem for dihedral groups from the point of view of the standard subgroup quantum algorithm for finite groups.
We explain a new connection between the dihedral coset problem and cloning of quantum states.
arXiv Detail & Related papers (2021-06-18T04:19:10Z) - A Practical Method for Constructing Equivariant Multilayer Perceptrons
for Arbitrary Matrix Groups [115.58550697886987]
We provide a completely general algorithm for solving for the equivariant layers of matrix groups.
In addition to recovering solutions from other works as special cases, we construct multilayer perceptrons equivariant to multiple groups that have never been tackled before.
Our approach outperforms non-equivariant baselines, with applications to particle physics and dynamical systems.
arXiv Detail & Related papers (2021-04-19T17:21:54Z) - On construction of finite averaging sets for $SL(2, \mathbb{C})$ via its
Cartan decomposition [0.0]
Averaging physical quantities over Lie groups appears in many contexts like quantum information science or quantum optics.
In this work we investigate the problem of constructing finite averaging sets for averaging over general non-compact matrix Lie groups.
We provide an explicit calculation of such sets for the group $SL(2, mathbbC)$, although our construction can be applied to other cases.
arXiv Detail & Related papers (2020-10-29T17:26:33Z) - Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU
Networks [48.32532049640782]
We study the problem of learning one-hidden-layer ReLU networks with $k$ hidden units on $mathbbRd$ under Gaussian marginals.
For the case of positive coefficients, we give the first-time algorithm for this learning problem for $k$ up to $tildeOOmega(sqrtlog d)$.
arXiv Detail & Related papers (2020-06-22T17:53:54Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.