An Initialization-free Quantum Algorithm for General Abelian Hidden Subgroup Problem

• URL: http://arxiv.org/abs/2507.18088v1
• Date: Thu, 24 Jul 2025 04:50:28 GMT
• Title: An Initialization-free Quantum Algorithm for General Abelian Hidden Subgroup Problem
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Hidden Subgroup Problem(HSP) seeks to identify an unknown subgroup H of a group G for a given injective function f defined on cosets of H. Here we present an initialization-free quantum algorithm for solving HSP in the case where G is a finite abelian group. Our algorithm can adopt an arbitrary unknown mixed state as the auxiliary register and removes the need for initialization while preserving computational cost comparable to existing methods. Our algorithm also restores the state of the auxiliary register to its original form after completing the computations. Since the recovered state can be utilized for other operations, a single preparation of the auxiliary register in an arbitrarily unknown mixed state is sufficient to execute the iterative procedure in solving hidden subgroup problems. This approach provides a promising direction for improving quantum algorithm efficiency by reducing operational time of initialization.

Related papers

• Reducing Circuit Resources in Grover's Algorithm via Constraint-Aware Initialization [3.7738353997936973]
  Grover's search algorithm provides a quadratic speedup over classical brute-force search in terms of query complexity.<n>We present a systematic framework with a simple preprocessing procedure for constraint-aware initializes in Grover's algorithm.<n>Our results indicate that this approach serves as a practical baseline for achieving more resource-efficient implementations of Grover's algorithm.
  arXiv  Detail & Related papers  (2026-01-25T07:31:06Z)
• 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)
• Learning T-conjugated stabilizers: The multiple-squares dihedral StateHSP [0.25956507689419356]
  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.
  arXiv  Detail & Related papers  (2025-10-09T07:23:53Z)
• 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)
• Arbitrary state creation via controlled measurement [49.494595696663524]
  This algorithm creates an arbitrary $n$-qubit pure quantum superposition state with precision of $m$-decimals.<n>The algorithm uses one-qubit rotations, Hadamard transformations and C-NOT operations with multi-qubit controls.
  arXiv  Detail & Related papers  (2025-04-13T07:23:50Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Modified Multiple Sequence Alignment Algorithm on Quantum Annealers (MAQ) [0.0]
  We propose a modified MSA algorithm on quantum annealers with applications in areas of bioinformatics and genetic sequencing. We apply progressive alignment techniques to modify algorithms, achieving a linear reduction in spin usage whilst introducing more quantum complexs to the algorithm.
  arXiv  Detail & Related papers  (2024-03-24T01:57:38Z)
• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input. For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer. For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
  arXiv  Detail & Related papers  (2023-12-18T18:29:01Z)
• Quantum algorithms for generator coordinate methods [12.744157326232749]
  This paper discusses quantum algorithms for the generator coordinate method (GCM) that can be used to benchmark molecular systems. We illustrate the performance of the quantum algorithm for constructing a discretized form of the Hill-Wheeler equation for ground and excited state energies.
  arXiv  Detail & Related papers  (2022-12-19T01:22:19Z)
• Alternatives to a nonhomogeneous partial differential equation quantum algorithm [52.77024349608834]
  We propose a quantum algorithm for solving nonhomogeneous linear partial differential equations of the form $Apsi(textbfr)=f(textbfr)$. These achievements enable easier experimental implementation of the quantum algorithm based on nowadays technology.
  arXiv  Detail & Related papers  (2022-05-11T14:29:39Z)
• 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)
• An efficient quantum algorithm for lattice problems achieving subexponential approximation factor [2.3351527694849574]
  We give a quantum algorithm for solving the Bounded Distance Decoding (BDD) problem with a subexponential approximation factor on a class of integer lattices. The running time of the quantum algorithm is for one range of approximation factors and subexponential time for a second range of approximation factors. This view makes for a clean quantum algorithm in terms of finite abelian groups, uses relatively little from lattice theory, and suggests exploring approximation algorithms for lattice problems in parameters other than dimension alone.
  arXiv  Detail & Related papers  (2022-01-31T18:58:33Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  We propose a new Hessian inverse free Fully Single Loop Algorithm for bilevel optimization problems. We show that our algorithm converges with the rate of $O(epsilon-2)$.
  arXiv  Detail & Related papers  (2021-12-09T02:27:52Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)

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.