An exact quantum hidden subgroup algorithm and applications to solvable groups

• URL: http://arxiv.org/abs/2202.04047v3
• Date: Mon, 2 May 2022 12:21:41 GMT
• Title: An exact quantum hidden subgroup algorithm and applications to solvable groups
• Authors: Muhammad Imran and Gabor Ivanyos
• Abstract summary: We present a time exact quantum algorithm for the hidden subgroup problem in $Z_mkn$. We also present applications to compute the structure of abelian and solvable groups whose order has the same (but possibly unknown) prime factors solvable as m.
• Score: 2.5204420653245245
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a polynomial time exact quantum algorithm for the hidden subgroup problem in $Z_{m^k}^n$. The algorithm uses the quantum Fourier transform modulo m and does not require factorization of m. For smooth m, i.e., when the prime factors of m are of size poly(log m), the quantum Fourier transform can be exactly computed using the method discovered independently by Cleve and Coppersmith, while for general m, the algorithm of Mosca and Zalka is available. Even for m=3 and k=1 our result appears to be new. We also present applications to compute the structure of abelian and solvable groups whose order has the same (but possibly unknown) prime factors as m. The applications for solvable groups also rely on an exact version of a technique proposed by Watrous for computing the uniform superposition of elements of subgroups.

Related papers

• Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
  Quantum signal processing (QSP) provides a systematic framework for implementing a transformation of a linear operator. Recent works have developed randomized compiling, a technique that promotes a unitary gate to a quantum channel. Our algorithm implements a probabilistic mixture of randomizeds, strategically chosen so that the average evolution converges to that of a target function, with an error quadratically smaller than that of an equivalent individual.
  arXiv  Detail & Related papers  (2024-09-05T17:56:51Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• The Power of Adaptivity in Quantum Query Algorithms [0.5702169790677977]
  We study the depth-computation trade-off in the query model, where the depth corresponds to the number of adaptive query rounds and the number of parallel queries per round. We achieve the strongest known separation between quantum algorithms with $r$ versus $r-1$ rounds of adaptivity.
  arXiv  Detail & Related papers  (2023-11-27T18:21:32Z)
• Generalised Coupling and An Elementary Algorithm for the Quantum Schur Transform [0.0]
  We present a transparent algorithm for implementing the qubit quantum Schur transform. We study the associated Schur states, which consist of qubits coupled via Clebsch-Gordan coefficients. It is shown that Wigner 6-j symbols and SU(N) Clebsch-Gordan coefficients naturally fit our framework.
  arXiv  Detail & Related papers  (2023-05-06T15:19:52Z)
• 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 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)
• Near-term quantum algorithm for computing molecular and materials properties based on recursive variational series methods [44.99833362998488]
  We propose a quantum algorithm to estimate the properties of molecules using near-term quantum devices. We test our method by computing the one-particle Green's function in the energy domain and the autocorrelation function in the time domain.
  arXiv  Detail & Related papers  (2022-06-20T16:33:23Z)
• An exact quantum order finding algorithm and its applications [2.5204420653245245]
  We present an efficient exact quantum algorithm for order finding problem when a multiple $m$ of the order $r$ is known. As applications, we show how the algorithm derandomizes the quantum algorithm for primality testing.
  arXiv  Detail & Related papers  (2022-05-06T07:15:54Z)
• 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)
• How to Decompose a Tensor with Group Structure [25.313563663123354]
  We study the orbit recovery problem, which is a natural abstraction for the problem of recovering a planted signal from noisy measurements under unknown group actions. Our main result is a quasi-polynomial time algorithm to solve orbit recovery over $SO(3)$ - i.e. the cryo-electron tomography problem.
  arXiv  Detail & Related papers  (2021-06-04T19:27:24Z)
• 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)

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.