Polynomial-time quantum algorithm for solving the hidden subgroup problem

• URL: http://arxiv.org/abs/2204.03295v5
• Date: Thu, 4 May 2023 02:25:20 GMT
• Title: Polynomial-time quantum algorithm for solving the hidden subgroup problem
• Authors: Hefeng Wang
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The hidden subgroup problem~(HSP) is one of the most important problems in quantum computation. Many problems for which quantum algorithm achieves exponential speedup over its classical counterparts can be reduced to the Abelian HSP. However, there is no efficient quantum algorithm for solving the non-Abelian HSP. 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 computation. Then we solve the HSP and problems that can be reduced to both the Abelian and the non-Abelian HSP in polynomial time by using this algorithm.

Related papers

• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• 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)
• The NISQ Complexity of Collision Finding [2.9405711598281536]
  A fundamental primitive in modern cryptography, collision-resistant hashing ensures there is no efficient way to find inputs that produce the same hash value. Quantum adversaries now require full-scale computers equipped with the power of NISQ. In this paper, we investigate three different models for NISQ algorithms achieve tight bounds for all of them.
  arXiv  Detail & Related papers  (2022-11-23T13:55:28Z)
• 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)
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
  We present a complete analysis of the quantum solvability of the noisy binary linear problem (NBLP) We show that the cost of solving the NBLP can be in the problem size, at the expense of an exponentially increasing logical qubits.
  arXiv  Detail & Related papers  (2021-09-23T07:46:20Z)
• Finding high-order Hadamard matrices by using quantum computers [0.0]
  We show that by adopting classical construction/search techniques of the H-matrix, we can develop new quantum computing methods to find higher order H-matrices. Especially, the Turyn-based quantum computing method can be further developed to find an arbitrarily high order H-matrix.
  arXiv  Detail & Related papers  (2020-09-23T03:19:39Z)
• An HHL-Based Algorithm for Computing Hitting Probabilities of Quantum Random Walks [3.068108039722565]
  We present a novel application of the HHL (Harrow-Hassidim-Lloyd) algorithm -- a quantum algorithm solving systems of linear equations -- in solving an open problem about quantum random walks. A quantum algorithm with the HHL algorithm as a subroutine is developed for solving the problem, which is faster than the known classical algorithms by numerical experiments.
  arXiv  Detail & Related papers  (2020-09-08T09:47:43Z)
• The Hidden Subgroup Problem for Universal Algebras [0.7832189413179361]
  The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete discrete problem, graph isomorphism, and the shortest vector problem.
  arXiv  Detail & Related papers  (2020-01-30T13:09:35Z)

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.