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
• Authors: Sekang Kwon, Jeong San Kim,
• 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

• 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.