Learning T-conjugated stabilizers: The multiple-squares dihedral StateHSP

• URL: http://arxiv.org/abs/2510.07872v1
• Date: Thu, 09 Oct 2025 07:23:53 GMT
• Title: Learning T-conjugated stabilizers: The multiple-squares dihedral StateHSP
• Authors: Gideon Lee, Jonathan A. Gross, Masaya Fukami, Zhang Jiang,
• Abstract summary: We present an algorithm that solves the non-abelian StateHSP over $N$ copies of the dihedral group of order $8$ (the symmetries of a square)<n>This algorithm is of interest for learning non-Pauli stabilizers, as well as related symmetries relevant for the problem of Hamiltonian spectroscopy.
• Score: 0.25956507689419356
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The state hidden subgroup problem (StateHSP) is a recent generalization of the hidden subgroup problem. We present an algorithm that solves the non-abelian StateHSP over $N$ copies of the dihedral group of order $8$ (the symmetries of a square). This algorithm is of interest for learning non-Pauli stabilizers, as well as related symmetries relevant for the problem of Hamiltonian spectroscopy. Our algorithm is polynomial in the number of samples and computational time, and requires only constant depth circuits. This result extends previous work on the abelian StateHSP and, as a special case, provides a solution for the ordinary hidden subgroup problem on this specific non-abelian group.

Related papers

• Low-degree Lower bounds for clustering in moderate dimension [53.03724383992195]
  We study the fundamental problem of clustering $n$ points into $K$ groups drawn from a mixture of isotropic Gaussians in $mathbbRd$.<n>We show that while the difficulty of clustering for $n leq dK$ is driven by dimension reduction and spectral methods, the moderate-dimensional regime involves more delicate phenomena leading to a "non-optimal rate"<n>We provide a novel non-spectral algorithm matching this rate, shedding new light on the computational limits of the clustering problem in moderate dimension.
  arXiv  Detail & Related papers  (2026-02-26T14:03:55Z)
• Revisiting finite Abelian hidden subgroup problem and its distributed exact quantum algorithm [4.250782756734906]
  We revisit the finite Abelian hidden subgroup problem (AHSP) from a mathematical perspective.<n>We present an exact quantum algorithm for the finite AHSP, which is more concise than the previous exact algorithm.<n>We propose a distributed exact quantum algorithm for finite AHSP, which requires fewer qudits, lower quantum query complexity, and no quantum communication.
  arXiv  Detail & Related papers  (2025-12-28T15:00:50Z)
• A survey about Hidden Subgroup Problem from a mathematical and cryptographic perspective [0.0]
  The Hidden Subgroup Problem (HSP) plays an important role in studying the security of public-key cryptosystems.<n>We first review the abelian case, where Kitaev's algorithm yields an efficient quantum solution to the HSP.<n>We then examine the current state of the art for non-abelian HSP, where no general efficient quantum solution is known.
  arXiv  Detail & Related papers  (2025-12-01T12:48:34Z)
• The hidden subgroup problem for infinite groups [0.0]
  We show that HSP is NP-hard for the additive group of rational numbers, and for normal subgroups of non-abelian free groups.<n>We generalize the ShorKitev algorithm for HSP in $mathbbZk$ with standard query cost.<n>It follows that HSP in any finitely generated, virtually abelian group also has a stretched exponential time algorithm.
  arXiv  Detail & Related papers  (2025-07-24T15:16:20Z)
• An Initialization-free Quantum Algorithm for General Abelian Hidden Subgroup Problem [0.0]
  Our algorithm can adopt an arbitrary unknown mixed state as the auxiliary register.<n>Our algorithm also restores the state of the auxiliary register to its original form after completing the computations.
  arXiv  Detail & Related papers  (2025-07-24T04:50:28Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• 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)
• Polynomial-time quantum algorithm for solving the hidden subgroup problem [0.0]
  The hidden subgroup problem(HSP) is one of the most important problems in quantum computation. We find that the HSP can be reduced to a nested structured search problem that is solved efficiently by using a quantum algorithm via multistep quantum algorithm.
  arXiv  Detail & Related papers  (2022-04-07T08:50:50Z)
• 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)
• 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)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise. Our algorithm learns the true halfspace within any accuracy $epsilon$.
  arXiv  Detail & Related papers  (2020-10-04T22:19:06Z)
• 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.