Group Order is in QCMA

• URL: http://arxiv.org/abs/2504.05547v1
• Date: Mon, 07 Apr 2025 22:54:09 GMT
• Title: Group Order is in QCMA
• Authors: François Le Gall, Harumichi Nishimura, Dhara Thakkar,
• Abstract summary: We show that verifying the order of a finite group given as a black-box is in the complexity class QCMA.<n>Our techniques also give improved quantum upper bounds on the complexity of many other group-theoretical problems, such as group isomorphism in black-box groups.
• Score: 0.5188841610098435
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we show that verifying the order of a finite group given as a black-box is in the complexity class QCMA. This solves an open problem asked by Watrous in 2000 in his seminal paper on quantum proofs and directly implies that the Group Non-Membership problem is also in the class QCMA, which further proves a conjecture proposed by Aaronson and Kuperberg in 2006. Our techniques also give improved quantum upper bounds on the complexity of many other group-theoretical problems, such as group isomorphism in black-box groups.

Related papers

• A quantum algorithm for Khovanov homology [42.6618666851542]
  Khovanov homology is a knot that categorifies the Jones topological invariant, recognizes the unknot, and is conjectured to appear as an observable in $4D$ supersymmetric Yang-Mills theory. Despite its rich mathematical and physical significance, the computational complexity of Khovanov homology remains largely unknown.
  arXiv  Detail & Related papers  (2025-01-21T18:54:59Z)
• 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)
• Constructive quantum mechanics based on finite groups [0.0]
  A formulation of quantum mechanics based on replacing the general unitary group by finite groups is considered. To solve problems arising in the context of this formulation, we use computer algebra and computational group theory methods.
  arXiv  Detail & Related papers  (2024-09-26T14:04:37Z)
• Contracting Self-similar Groups in Group-Based Cryptography [0.0]
  We propose self-similar contracting groups as a platform for cryptographic schemes based on simultaneous conjugacy search problem (SCSP) The class of these groups contains extraordinary examples like Grigorchuk group, which is known to be non-linear. We discuss benefits and drawbacks of using these groups in group-based cryptography and provide computational analysis of variants of the length-based attack on SCSP.
  arXiv  Detail & Related papers  (2024-08-26T15:30:11Z)
• 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)
• A perturbative approach to the solution of the Thirring quantum cellular automaton [42.205102271729665]
  The Thirring Quantum Cellular Automaton (QCA) describes the discrete time dynamics of local fermionic modes that evolve according to one step of the Dirac cellular automaton followed by the most general on-site number-preserving interaction, and serves as the QCA counterpart of the Thirring model in quantum field theory.
  arXiv  Detail & Related papers  (2024-06-28T13:44:10Z)
• Clique Homology is QMA1-hard [0.0]
  We show that the decision problem of determining homology groups of simplicial complexes is QMA1-hard. This suggests that the seemingly classical problem may in fact be quantum mechanical. We discuss potential implications for the problem of quantum advantage in topological data analysis.
  arXiv  Detail & Related papers  (2022-09-23T18:14:16Z)
• Max-Min Grouped Bandits [48.62520520818357]
  We introduce a multi-armed bandit problem termed max-min grouped bandits. The goal is to find a group whose worst arm has the highest mean reward. This problem is of interest to applications such as recommendation systems.
  arXiv  Detail & Related papers  (2021-11-17T01:59:15Z)
• 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)
• The dihedral hidden subgroup problem [0.0]
  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.
  arXiv  Detail & Related papers  (2021-06-18T04:19:10Z)
• Constraints on Maximal Entanglement Under Groups of Permutations [73.21730086814223]
  Sets of entanglements are inherently equal, lying in the same orbit under the group action. We introduce new, generalized relationships for the maxima of those entanglement by exploiting the normalizer and normal subgroups of the physical symmetry group.
  arXiv  Detail & Related papers  (2020-11-30T02:21:22Z)
• A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group [29.714239628405515]
  We consider the class of synchronization problems which the group is a closed subgroup. We propose a unified approach for solving this class of problems. We show that our approach outperforms existing approaches.
  arXiv  Detail & Related papers  (2020-09-16T07:25:50Z)
• Continuous LWE [32.345218864470446]
  We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We give a quantum reduction from worst-case lattice problems to CLWE, showing that CLWE enjoys similar hardness guarantees to those of LWE.
  arXiv  Detail & Related papers  (2020-05-19T17:16:12Z)

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.