Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

journal of Groups complexity cryptology

Quantum algorithms for fixed points and invariant subgroups

Marianna C. Bonanome, Stephen Majewicz

Published Jan 1, 2011• 0 citations
Publisher

Abstract

In this paper, we apply quantum algorithms to solve problems concerning fixed points and invariant subgroups of automorphisms. These efficient algorithms invoke a quantum algorithm which computes the intersection of multiple unsorted multisets whose elements originate from the same set. This intersection algorithm is an application of the Grover search procedure.

DOI
10.1515/gcc.2011.013

Related papers

Application of quantum algorithms to the study of permutations and group automorphisms

Marianna C. Bonanome, Mark S. Hillery, Vladimír Bužek

We discuss three applications of efficient quantum algorithms to determining properties of permutations and group automorphisms. The first uses the Bernstein-Vazirani algorithm to determine an unknown homomorphism from ${Z}_{p\ensuremath{-}1}^{m}$ to $\mathit{Aut}({Z}_{p})$ where $p$ is prime. The remaining two make use of modifications of the Grover search algorithm. The first finds the fixed point of a permutation or an automorphism (assuming it has only one besides the identity). It can be generalized to find cycles of a specified size for permutations or orbits of a specified size for automorphisms. The second finds which of a set of permutations or automorphisms maps one particular element of a set or group onto another. This has relevance to the conjugacy problem for groups. We show how two of these algorithms can be implemented via programmable quantum processors. This approach opens new perspectives in quantum information processing when both the data and the programs are represented by states of quantum registers. In particular, quantum programs that specify control over data can be treated using methods of quantum information theory.

arXiv:0708.2560•Physical Review A•Jul 24, 2007•3 citations

Quantum Algorithm for Searching of Two Sets Intersection

Kamil Ravilevich Khadiev, Elizaveta Krendeleva

Abstract In the paper we investigate Two Sets Intersection problem. Assume that we have two sets that are subsets of n objects. Sets are presented by two predicates that show which of n objects belong to these sets. We present a quantum algorithm that finds an element from the two sets intersection. It is a modification of the well-known Grover’s search algorithm that uses two Oracles with access to the predicates. The algorithm is faster than the naive application of Grover’s search.

arXiv:2312.16897•Russian Microelectronics•Dec 1, 2023•2 citations

Quantum Algorithm for Solving the Continuous Hidden Symmetry Subgroup Problem

Eunok Bae, Soojoon Lee

Quantum computers are expected to be able to outperform classical computers. In fact, some computational problems such as integer factorization can be solved on quantum computers substantially faster than classical computers. Interestingly, these problems can be cast in a framework of the hidden symmetry subgroup problem. However, only a few of quantum algorithms for efficiently solving this problem have been known, and the approaches used in all previous results can be applied to particular groups with specific group actions. In this paper, we introduce new technique for solving the hidden symmetry subgroup problem which can be applicable for any groups and any group actions with a certain condition. In addition, we define the continuous hidden symmetry subgroup problem on a group by employing a continuous oracle function, and prove that if the group is a metric space and the group action satisfies some condition, then the continuous hidden symmetry subgroup problem can be efficiently reduced to the continuous hidden subgroup problem. In particular, we show that there exists an efficient quantum algorithm to solve the continuous hidden symmetry subgroup problem on$\mathbb {R}^{n}$, while it has not yet been shown that the original hidden symmetry subgroup problem on$\mathbb {R}^{n}$can be efficiently solved by a quantum computer.

IEEE Access•Jan 1, 2021•0 citations

Exact quantum algorithm for searching of multiple sets intersection

Sheng-Ao Mao, Lin Zhang, Bo Li

Grover's algorithm achieves a quadratic speedup for unstructured search when a global oracle for the target set is available. However, its success probability is generally below $100\%$. To overcome this issue, Long presented a modified version of Grover's search algorithm by introducing a phase-matching condition, which can search for the target set with zero theoretical failure rate. Nevertheless, in many applications, the target set is determined by the intersection of multiple constrained sets. Most existing Grover-based methods are limited to the intersection of only two sets and are not always successful in searching for the target set. In this work, based on Long's method, we propose an algorithm for exactly searching the intersection of multiple sets. We derive and prove a phase-matching condition for searching the intersection exactly. Furthermore, we present a quantum circuit that implements exact intersection search. Finally, we support our theoretical results with numerical simulations.

quant-pharXiv:2609.36908•Sep 30, 2026•0 citations

Hidden subgroup problem in quantum computing

Shuhong Gao, Prasit Limbupasiriporn

We study quantum algorithms for the hidden subgroup problem (HSP). The HSP provides a unified framework for many important problems, including factoring integers, graph isomorphism problem, etc. It has been known that the problem for abelian groups can be efficiently solved. However, for non-abelian groups, it remains widely open. In this dissertation we study the problem for some specific non-abelian groups, called q-hedral groups. We start with a quantum algorithm, proposed by Moore et al. (2003), for finding some hidden conjugate subgroups of affine groups, a special case of q-hedral groups for large q. We then adapt their algorithm to construct an algorithm for solving the hidden conjugate problem for q-hedral groups for large q and point out a difficulty in complexity analysis that involves certain exponential sums. We discuss certain bounds on these sums and present some computational data on their values to make a conjecture. For small q, Regev (2003) gave an efficient algorithm for solving the HSP for dihedral groups (q = 2) using an oracle that solves a certain subset sum problem (SSP). A crucial step of his algorithm relies on the probability that elements in a cyclic group ZN can be expressed as sums of random elements in the group. We generalize this problem to any finite group and prove the following theorem: for any finite group G and r ≥ 32 log2 |G| + 5, if r elements from G are chosen randomly, then the 2r possible sums (or products) of the r elements will cover all the elements in G with high probability. Also, by making a further generalization of the SSP, we show that Regev's algorithm can be generalized for q-hedral groups for any fixed q. We also study this generalized subset sum problem. In addition to the algorithm developing for small q, we give an efficient quantum algorithm for solving the coset problem and an efficient quantum algorithm for solving the hidden conjugate problem. Furthermore, we also give a survey of an algorithm for finding the largest normal subgroup in a hidden subgroup of any finite group, introduced by Hallgren et al. (2000) and provide a simplified and unified proof.

•Jan 1, 2005•0 citations

Many Known Quantum Algorithms Are Optimal: Symmetry-Based Proofs

Владик Крейнович, Oscar Galindo, Olga M. Kosheleva

Many quantum algorithms have been proposed which are drastically more efficient that the best of the non-quantum algorithms for solving the same problems. A natural question is: are these quantum algorithms already optimal – in some reasonable sense – or they can be further improved? In this paper, we review recent results showing that many known quantum algorithms are actually optimal. Several of these results are based on appropriate invariances (symmetries). Specifically, we show that the following algorithms are optimal: Grover’s algorithm for fast search in an unsorted array, teleportation algorithm – which is important for parallel quantum computations, and quantum annealing optimization algorithm. This covers many algorithms related to quantum computing. We also mention that algorithms for quantum communication and Deutsch-Josza algorithm – for fast checking whether a bit affect computation results – are optimal. In all these cases, optimality is shown not just for one specific optimality criterion, but for all possible optimality criteria that satisfy the natural invariance requirement.

International Journal of Computing•Dec 31, 2022•1 citation
In this paper, we apply quantum algorithms to solve problems concerning fixed points and invariant subgroups of automorphisms. These efficient algorithms invoke a quantum algorithm which computes the intersection of multiple unsorted multisets whose elements originate from the same set. This intersection algorithm is an application of the Grover search procedure.
We discuss three applications of efficient quantum algorithms to determining properties of permutations and group automorphisms. The first uses the Bernstein-Vazirani algorithm to determine an unknown homomorphism from ${Z}_{p\ensuremath{-}1}^{m}$ to Aut(Zp)\mathit{Aut}({Z}_{p})Aut(Zp​) where ppp is prime. The remaining two make use of modifications of the Grover search algorithm. The first finds the fixed point of a permutation or an automorphism (assuming it has only one besides the identity). It can be generalized to find cycles of a specified size for permutations or orbits of a specified size for automorphisms. The second finds which of a set of permutations or automorphisms maps one particular element of a set or group onto another. This has relevance to the conjugacy problem for groups. We show how two of these algorithms can be implemented via programmable quantum processors. This approach opens new perspectives in quantum information processing when both the data and the programs are represented by states of quantum registers. In particular, quantum programs that specify control over data can be treated using methods of quantum information theory.
Quantum computers are expected to be able to outperform classical computers. In fact, some computational problems such as integer factorization can be solved on quantum computers substantially faster than classical computers. Interestingly, these problems can be cast in a framework of the hidden symmetry subgroup problem. However, only a few of quantum algorithms for efficiently solving this problem have been known, and the approaches used in all previous results can be applied to particular groups with specific group actions. In this paper, we introduce new technique for solving the hidden symmetry subgroup problem which can be applicable for any groups and any group actions with a certain condition. In addition, we define the continuous hidden symmetry subgroup problem on a group by employing a continuous oracle function, and prove that if the group is a metric space and the group action satisfies some condition, then the continuous hidden symmetry subgroup problem can be efficiently reduced to the continuous hidden subgroup problem. In particular, we show that there exists an efficient quantum algorithm to solve the continuous hidden symmetry subgroup problem onRn\mathbb {R}^{n}Rn, while it has not yet been shown that the original hidden symmetry subgroup problem onRn\mathbb {R}^{n}Rncan be efficiently solved by a quantum computer.
Grover's algorithm achieves a quadratic speedup for unstructured search when a global oracle for the target set is available. However, its success probability is generally below 100%100\%100%. To overcome this issue, Long presented a modified version of Grover's search algorithm by introducing a phase-matching condition, which can search for the target set with zero theoretical failure rate. Nevertheless, in many applications, the target set is determined by the intersection of multiple constrained sets. Most existing Grover-based methods are limited to the intersection of only two sets and are not always successful in searching for the target set. In this work, based on Long's method, we propose an algorithm for exactly searching the intersection of multiple sets. We derive and prove a phase-matching condition for searching the intersection exactly. Furthermore, we present a quantum circuit that implements exact intersection search. Finally, we support our theoretical results with numerical simulations.
We study quantum algorithms for the hidden subgroup problem (HSP). The HSP provides a unified framework for many important problems, including factoring integers, graph isomorphism problem, etc. It has been known that the problem for abelian groups can be efficiently solved. However, for non-abelian groups, it remains widely open. In this dissertation we study the problem for some specific non-abelian groups, called q-hedral groups. We start with a quantum algorithm, proposed by Moore et al. (2003), for finding some hidden conjugate subgroups of affine groups, a special case of q-hedral groups for large q. We then adapt their algorithm to construct an algorithm for solving the hidden conjugate problem for q-hedral groups for large q and point out a difficulty in complexity analysis that involves certain exponential sums. We discuss certain bounds on these sums and present some computational data on their values to make a conjecture. For small q, Regev (2003) gave an efficient algorithm for solving the HSP for dihedral groups (q = 2) using an oracle that solves a certain subset sum problem (SSP). A crucial step of his algorithm relies on the probability that elements in a cyclic group ZN can be expressed as sums of random elements in the group. We generalize this problem to any finite group and prove the following theorem: for any finite group G and r ≥ 32 log2 |G| + 5, if r elements from G are chosen randomly, then the 2r possible sums (or products) of the r elements will cover all the elements in G with high probability. Also, by making a further generalization of the SSP, we show that Regev's algorithm can be generalized for q-hedral groups for any fixed q. We also study this generalized subset sum problem. In addition to the algorithm developing for small q, we give an efficient quantum algorithm for solving the coset problem and an efficient quantum algorithm for solving the hidden conjugate problem. Furthermore, we also give a survey of an algorithm for finding the largest normal subgroup in a hidden subgroup of any finite group, introduced by Hallgren et al. (2000) and provide a simplified and unified proof.
Many quantum algorithms have been proposed which are drastically more efficient that the best of the non-quantum algorithms for solving the same problems. A natural question is: are these quantum algorithms already optimal – in some reasonable sense – or they can be further improved? In this paper, we review recent results showing that many known quantum algorithms are actually optimal. Several of these results are based on appropriate invariances (symmetries). Specifically, we show that the following algorithms are optimal: Grover’s algorithm for fast search in an unsorted array, teleportation algorithm – which is important for parallel quantum computations, and quantum annealing optimization algorithm. This covers many algorithms related to quantum computing. We also mention that algorithms for quantum communication and Deutsch-Josza algorithm – for fast checking whether a bit affect computation results – are optimal. In all these cases, optimality is shown not just for one specific optimality criterion, but for all possible optimality criteria that satisfy the natural invariance requirement.