The dihedral hidden subgroup problem

• URL: http://arxiv.org/abs/2106.09907v2
• Date: Tue, 4 Oct 2022 23:11:42 GMT
• Title: The dihedral hidden subgroup problem
• Authors: Imin Chen and David Sun
• Abstract summary: We give an exposition of the hidden problem for dihedral groups from the point of view of the standard subgroup quantum algorithm for finite groups. We explain a new connection between the dihedral coset problem and cloning of quantum states.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give an exposition of the hidden subgroup problem for dihedral groups from the point of view of the standard hidden subgroup quantum algorithm for finite groups. In particular, we recall the obstructions for strong Fourier sampling to succeed, but at the same time, show how the standard algorithm can be modified to establish polynomial quantum query complexity. Finally, we explain a new connection between the dihedral coset problem and cloning of quantum states.

Related papers

• Quantum channels, complex Stiefel manifolds, and optimization [45.9982965995401]
  We establish a continuity relation between the topological space of quantum channels and the quotient of the complex Stiefel manifold. The established relation can be applied to various quantum optimization problems.
  arXiv  Detail & Related papers  (2024-08-19T09:15:54Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
  arXiv  Detail & Related papers  (2023-01-05T11:05:22Z)
• 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)
• A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem [1.189332466445755]
  We present a-time quantum algorithm for the Hidden Subgroup Problem over $mathbbD_2n$. By focusing on structure encoded in the codomain of the problem, we develop an algorithm which uses this structure to direct a "walk" down the subgroup lattice of $mathbbD_2n$ terminating at the hidden subgroup.
  arXiv  Detail & Related papers  (2022-02-19T23:51:15Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• On the Universality and Membership problems for quantum gates [0.0]
  We study the Universality and Membership Problems for gate sets consisting of a finite number of quantum gates. Our approach relies on the techniques from compact Lie groups theory.
  arXiv  Detail & Related papers  (2021-10-08T15:53:09Z)
• Quantum Error Mitigation Relying on Permutation Filtering [84.66087478797475]
  We propose a general framework termed as permutation filters, which includes the existing permutation-based methods as special cases. We show that the proposed filter design algorithm always converges to the global optimum, and that the optimal filters can provide substantial improvements over the existing permutation-based methods.
  arXiv  Detail & Related papers  (2021-07-03T16:07:30Z)
• Quantum Hypothesis Testing with Group Structure [0.0]
  Recently-developed techniques of quantum signal processing can be modified to constitute subroutines for quantum hypothesis testing. Performance is completely defined by explicit group homomorphisms. Extensions to larger groups and noisy settings are discussed.
  arXiv  Detail & Related papers  (2021-02-03T18:46:51Z)
• 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)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

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.