Two Problems on Quantum Computing in Finite Abelian Groups

• URL: http://arxiv.org/abs/2604.00929v1
• Date: Wed, 01 Apr 2026 14:07:38 GMT
• Title: Two Problems on Quantum Computing in Finite Abelian Groups
• Abstract summary: In the context of finite Abelian groups two problems are presented and solved using quantum computing techniques.<n>The first is the well--known Hidden Subgroup Problem, originally solved by Simon.<n>The second is the Fully Balanced Image Problem, originally introduced by the authors.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In the context of finite Abelian groups two problems are presented and solved using quantum computing techniques. The first is the well--known Hidden Subgroup Problem, originally solved by Simon in a landmark work. The second is the Fully Balanced Image Problem, originally introduced by the authors (joint with J. Ossorio--Castillo), which is related to a certain class of mappings (which contains strictly, for instance, the family of group morphisms). Both problems are tackled using a combination of two techniques: first, a conversion into Boolean objects, better suited for quantum computing arguments, and subsequently a custom--tailored algorithm which takes advantage of the Generalised Phase--Kick Back technique.

Related papers

• Quantum state isomorphism problems for groups [41.49556721904551]
  We study the computational complexity of quantum state isomorphism problems under group actions.<n>For pure-state version, we show that the problem is BQP-hard for all nontrivial groups.<n>For the mixed-state version, for nontrivial, finite and efficiently representable groups, the problem is QSZK-complete.
  arXiv  Detail & Related papers  (2026-05-12T18:05:27Z)
• Tight Quantum Lower Bound for k-Distinctness [52.10197476419622]
  We introduce a new quantum query lower bound framework.<n>We show how this framework behaves on the problem of finding equal elements in the input string.<n>In particular, we demonstrate its power by proving a first tight quantum query lower bound for the k-Distinctness problem.
  arXiv  Detail & Related papers  (2026-04-06T19:52:58Z)
• 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)
• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  The tutorial begins by outlining variational quantum circuits and QUBO problems.<n>Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications.<n>The tutorial extends these concepts to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
  arXiv  Detail & Related papers  (2025-11-23T09:54:20Z)
• Lie groups for quantum complexity and barren plateau theory [0.0]
  We introduce the theory of Lie groups and their algebras to analyze two fundamental problems in quantum computing.<n> Firstly, we describe the geometric formulation of quantum computational complexity.<n> Secondly, we deal with the barren plateau phenomenon in Variational Quantum Algorithms.
  arXiv  Detail & Related papers  (2025-07-30T11:46:09Z)
• Quantum Algorithm for Vector Set Orthogonal Normalization and Matrix QR Decomposition with Polynomial Speedup [4.913177281640608]
  Gram-Schmidt process is widely used to solve Vector set normalization and matrix QR decomposition.<n>Existing methods have problems of high complexity, scaling $O(N3)$ in the system dimension $N$.<n>We propose quantum algorithms to solve these two problems based on the idea of Gram-Schmidt process and quantum phase estimation.
  arXiv  Detail & Related papers  (2024-12-26T07:04:34Z)
• A QUBO Formulation for the Generalized LinkedIn Queens and Takuzu/Tango Game [49.1574468325115]
  We present a QUBO formulation designed to solve a series of generalisations of the LinkedIn queens game.<n>We adapt this formulation for several particular cases of the problem, as Tents & Trees.<n>We also present two new types of problems, the Coloured Chess Piece Problem and the Max Chess Pieces Problem, with their corresponding QUBO formulations.
  arXiv  Detail & Related papers  (2024-10-08T23:54:54Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Quantum representation of finite groups [0.0]
  The concept of quantum representation of finite groups (QRFG) has been a fundamental aspect of quantum computing for quite some time. We provide a formal definition of this concept using both group theory and differential geometry. Our work proves the existence of a quantum representation for any finite group and outlines two methods for translating each generator of the group into a quantum circuit.
  arXiv  Detail & Related papers  (2022-09-29T18:01:03Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• 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)
• Verification of Group Non-membership by Shallow Quantum Circuits [6.611344035597144]
  The problem of deciding the group non-membership (GNM) of a group element is known to be in $mathsfQMA$. We propose an efficient way to verify GNM problems, reducing the circuit depth to $O(1)$ and the number of qubits by half.
  arXiv  Detail & Related papers  (2020-10-07T14:53:15Z)

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.