A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem

• URL: http://arxiv.org/abs/2202.09697v2
• Date: Wed, 23 Feb 2022 14:39:27 GMT
• Title: A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem
• Authors: Matthew Moore and Grace Young
• Abstract summary: 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.
• Score: 1.189332466445755
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a polynomial-time quantum algorithm for the Hidden Subgroup Problem over $\mathbb{D}_{2^n}$. The usual approach to the Hidden Subgroup Problem relies on harmonic analysis in the domain of the problem, and the best known algorithm using this approach has time complexity in $2^{\mathcal{O}(\sqrt{n})}$. By focusing on structure encoded in the codomain of the problem, we develop a polynomial-time algorithm which uses this structure to direct a "walk" down the subgroup lattice of $\mathbb{D}_{2^n}$ terminating at the hidden subgroup.

Related papers

• Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Cyclotomic Subextensions [6.487242614495099]
  We prove the equivalence between the Ring Learning With Errors (RLWE) and the Polynomial Learning With Errors (PLWE) problems. We also describe a fast integers for computing the product of two elements in the ring of the maximal real subfield.
  arXiv  Detail & Related papers  (2024-10-01T15:32:02Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Zero sum subsequences and hidden subgroups [2.5204420653245245]
  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.
  arXiv  Detail & Related papers  (2023-04-17T15:40:30Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$. We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
  arXiv  Detail & Related papers  (2023-01-04T04:15:40Z)
• Computing a Group Action from the Class Field Theory of Imaginary Hyperelliptic Function Fields [0.0]
  The Jacobian of an imaginary hyperelliptic curve defined over $mathbb F_q$ acts on a subset of isomorphism classes of Drinfeld modules. This is a function field analog of the Couveignes-Rostovtsev-Stolbunov group action. We prove that the problem of inverting the group action reduces the problem of finding isogenies of fixed $tau$-degree between Drinfeld $mathbb F_q[X]$-modules.
  arXiv  Detail & Related papers  (2022-03-14T10:11:35Z)
• 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)
• Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
  We propose to accelerate existing linear bandit algorithms to achieve per-step time complexity sublinear in the number of arms $K$. We show that our proposed algorithms can achieve $O(K1-alpha(T))$ per-step complexity for some $alpha(T) > 0$ and $widetilde O(stT)$ regret, where $T$ is the time horizon.
  arXiv  Detail & Related papers  (2021-03-03T22:42:15Z)
• A new quantum algorithm for the hidden shift problem in $\mathbb{Z}_{2^t}^n$ [0.0]
  We give a solution to the case when $k$ is a power of 2, which has running time in $nlog (k) It can be a useful tool in the general case of the hidden shift and hidden problems too.
  arXiv  Detail & Related papers  (2021-02-08T13:01:33Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• 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.