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

Восточно-Европейский журнал передовых технологий

Complexity of hidden abelian group action problem in quantum computing

Andrii Fesenko

Published Jan 1, 2013• 0 citations
Publisher

Abstract

The paper first examines the Hidden Abelian Group Action problem’s complexity in quantum computing model. This algebraic problem is fundamental in determining the hardness of a one-way function constructed on the basis of commutative and locally commutative maps and ciphers. In fact, finding new one-way functions that will be resistant in quantum computing model is very important for modern cryptography.The main objective of the study is to assess the complexity of the Hidden Abelian Group Action problem by using a reduction to already known problems, such as the Hidden Subgroup problem and the Hidden Shift problem. In this paper, reduction of the Hidden Abelian Group Action problem to the Hidden Shift problem was first shown, and limitations that distinguish them were first demonstrated. As a result, on the one hand, the existing partial solutions to the Hidden Shift problem, and general Kuperberg’s subexponential algorithm can be extended to the case of the Hidden Abelian Group Action problem. Moreover, more limitations give more chances to effective general solution to this problem. On the other hand, the reduction and similarity to a known challenge in quantum computing model also indicate the complexity of the Hidden Abelian Group Action problem, which leaves a chance for making a real stand one-way function in quantum computing model based on a locally commutative mapping

DOI
10.15587/1729-4061.2013.18345

Related papers

Quantum state isomorphism problems for groups

Alexandru Gheorghiu, Dale Jacobs, Saeed Mehraban +1 more

We study the computational complexity of quantum state isomorphism problems under group actions: given two quantum circuits that prepare pure or mixed states, decide whether the two states are related by a group action. This can be seen as a quantum state version of the Hidden Shift Problem, in much the same way that the State Hidden Subgroup Problem is a quantum version of the ordinary Hidden Subgroup Problem. We prove several results for this computational problem: - For the pure-state version, we show that the problem is BQP-hard for all nontrivial groups, and contained in QCMA $\cap$ QCSZK. We further obtain refined results for specific groups of interest: for abelian groups we show that the problem reduces to the state hidden subgroup problem over the generalized dihedral group; for the Clifford group, the problem is at least as hard as Graph Isomorphism under polynomial-time reductions; for the Pauli group it is BQP-complete. - For the mixed-state version, for nontrivial, finite and efficiently representable groups, the problem is QSZK-complete. - We also study a variant of this problem over an infinite group, in particular, the bosonic linear optical unitaries. We show that in the setting where the classical description of the quantum state is given in a suitable wave function representation known as the stellar representation, the problem is at least as hard as Graph Isomorphism, and is contained in NP $\cap$ SZK. Prior to our work, state isomorphism problems had only been studied for the symmetric group [LG17]. As a consequence of our results, we resolve an open question posed in [HEC25] about the existence of a quantum algorithm for the abelian state hidden subgroup problem on mixed states. We show that this problem is QSZK-hard in the worst case, thereby ruling out an efficient quantum algorithm unless QSZK = BQP.

quant-pharXiv:2605.12615•May 14, 2026•3 citations

Quantum algorithms and the fourier transform

Lawrence Ip, Umesh V. Vazirani

The search for practical problems that can be solved exponentially faster on a quantum computer is one of the primary goals in research into algorithms for quantum computers. It has long been known that such speedups are only possible for highly structured problems. We consider two problems with algebraic structure: (1) the hidden subgroup problem, where we have an unknown subgroup, a function that is constant on cosets of the subgroup, and the task is to find the unknown subgroup; (2) the hidden shift problem, where we have an unknown element of a group, a function that has been shifted by that group element, and the task is to find the unknown group element. We show that the Fourier transform is intimately connected to both these problems. This is because the Fourier transform respects group symmetries. For the hidden subgroup problem, we introduce the idea of using information theoretic techniques to design quantum algorithms. This consists of first finding an optimal set of measurements for distinguishing between different subgroups, followed by attempts to implement this set of measurements. We show that the standard algorithm for the abelian hidden subgroup problem is optimal. For the nonabelian hidden subgroup problem, the optimal measurements respect the Fourier transform in that they can be implemented by first performing a Fourier transform on each coset state, measuring the name of the irreducible representation for each state, followed by a joint measurement over the resulting lower dimensional space. This shows that the “strong standard method” cannot be used to implement the optimal set of measurements. For some instances of the hidden shift problem, we give a quantum algorithms that are exponentially faster than the best known classical algorithm. The algorithms make use of the Fourier transform in a way that may be interpreted as solving a deconvolution problem. As evidence of hardness, we give a reduction from algebraically homomorphic cryptosystems to the shifted Legendre symbol problem. This is an example of a problem which admits an exponential quantum speedup yet is not an instance of the abelian hidden subgroup problem.

•Jan 1, 2004•0 citations

The Hidden Subgroup Problem and Quantum Computation Using Group Representations

Sean Hallgren, Alexander C. Russell, Amnon Ta‐Shma

The hidden subgroup problem is the foundation of many quantum algorithms. An efficient solution is known for the problem over abelian groups, employed by both Simon's algorithm and Shor's factoring and discrete log algorithms. The nonabelian case, however, remains open; an efficient solution would give rise to an efficient quantum algorithm for graph isomorphism. We fully analyze a natural generalization of the algorithm for the abelian case to the nonabelian case and show that the algorithm determines the normal core of a hidden subgroup: in particular, normal subgroups can be determined. We show, however, that this immediate generalization of the abelian algorithm does not efficiently solve graph isomorphism.

SIAM Journal on Computing•Jan 1, 2003•107 citations

Hidden Translation and Translating Coset in Quantum Computing

Katalin Friedl, Gábor Ivanyos, Frédéric Magniez +2 more

We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of nonabelian solvable groups, including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in $\mathbb{Z}_p^n$, whenever $p$ is a fixed prime. For the induction step, we introduce the problem Translating Coset generalizing both Hidden Translation and Hidden Subgroup and prove a powerful self-reducibility result: Translating Coset in a finite solvable group $G$ is reducible to instances of Translating Coset in $G/N$ and $N$, for appropriate normal subgroups $N$ of $G$. Our self-reducibility framework, combined with Kuperberg's subexponential quantum algorithm for solving Hidden Translation in any abelian group, leads to subexponential quantum algorithms for Hidden Translation and Hidden Subgroup in any solvable group.

arXiv:quant-ph/0211091•SIAM Journal on Computing•Jan 1, 2014•40 citations

The Hidden Subgroup Problem for Generalized Quaternions

Julia Tumasova Upton

The hidden subgroup problem is a pivotal problem in quantum computation since it reflects the structure of tasks for which quantum algorithms significantly outperform classical algorithms. In this paper, a quantum algorithm that solves the hidden subgroup problem over the generalized quaternion group is developed. The algorithm employs the abelian quantum Fourier transform and Kuperberg sieve to reveal the hidden subgroup.

International Conference on Quantum, Nano and Micro Technologies (ICQNM)•Feb 1, 2010•1 citation

The hidden subgroup problem for generalized quaternions

Julia Tumasova Upton

The hidden subgroup problem is a pivotal problem in quantum computation since it reflects the structure of tasks for which quantum algorithms significantly outperform classical algorithms. In this paper, a quantum algorithm that solves the hidden subgroup problem over the generalized quaternion group is developed. The algorithm employs the abelian quantum Fourier transform and Kuperberg sieve to reveal the hidden subgroup.

•Jan 1, 2009•0 citations
The paper first examines the Hidden Abelian Group Action problem’s complexity in quantum computing model. This algebraic problem is fundamental in determining the hardness of a one-way function constructed on the basis of commutative and locally commutative maps and ciphers. In fact, finding new one-way functions that will be resistant in quantum computing model is very important for modern cryptography.The main objective of the study is to assess the complexity of the Hidden Abelian Group Action problem by using a reduction to already known problems, such as the Hidden Subgroup problem and the Hidden Shift problem. In this paper, reduction of the Hidden Abelian Group Action problem to the Hidden Shift problem was first shown, and limitations that distinguish them were first demonstrated. As a result, on the one hand, the existing partial solutions to the Hidden Shift problem, and general Kuperberg’s subexponential algorithm can be extended to the case of the Hidden Abelian Group Action problem. Moreover, more limitations give more chances to effective general solution to this problem. On the other hand, the reduction and similarity to a known challenge in quantum computing model also indicate the complexity of the Hidden Abelian Group Action problem, which leaves a chance for making a real stand one-way function in quantum computing model based on a locally commutative mapping
We study the computational complexity of quantum state isomorphism problems under group actions: given two quantum circuits that prepare pure or mixed states, decide whether the two states are related by a group action. This can be seen as a quantum state version of the Hidden Shift Problem, in much the same way that the State Hidden Subgroup Problem is a quantum version of the ordinary Hidden Subgroup Problem. We prove several results for this computational problem: - For the pure-state version, we show that the problem is BQP-hard for all nontrivial groups, and contained in QCMA ∩\cap∩ QCSZK. We further obtain refined results for specific groups of interest: for abelian groups we show that the problem reduces to the state hidden subgroup problem over the generalized dihedral group; for the Clifford group, the problem is at least as hard as Graph Isomorphism under polynomial-time reductions; for the Pauli group it is BQP-complete. - For the mixed-state version, for nontrivial, finite and efficiently representable groups, the problem is QSZK-complete. - We also study a variant of this problem over an infinite group, in particular, the bosonic linear optical unitaries. We show that in the setting where the classical description of the quantum state is given in a suitable wave function representation known as the stellar representation, the problem is at least as hard as Graph Isomorphism, and is contained in NP ∩\cap∩ SZK. Prior to our work, state isomorphism problems had only been studied for the symmetric group [LG17]. As a consequence of our results, we resolve an open question posed in [HEC25] about the existence of a quantum algorithm for the abelian state hidden subgroup problem on mixed states. We show that this problem is QSZK-hard in the worst case, thereby ruling out an efficient quantum algorithm unless QSZK = BQP.
The search for practical problems that can be solved exponentially faster on a quantum computer is one of the primary goals in research into algorithms for quantum computers. It has long been known that such speedups are only possible for highly structured problems. We consider two problems with algebraic structure: (1) the hidden subgroup problem, where we have an unknown subgroup, a function that is constant on cosets of the subgroup, and the task is to find the unknown subgroup; (2) the hidden shift problem, where we have an unknown element of a group, a function that has been shifted by that group element, and the task is to find the unknown group element. We show that the Fourier transform is intimately connected to both these problems. This is because the Fourier transform respects group symmetries. For the hidden subgroup problem, we introduce the idea of using information theoretic techniques to design quantum algorithms. This consists of first finding an optimal set of measurements for distinguishing between different subgroups, followed by attempts to implement this set of measurements. We show that the standard algorithm for the abelian hidden subgroup problem is optimal. For the nonabelian hidden subgroup problem, the optimal measurements respect the Fourier transform in that they can be implemented by first performing a Fourier transform on each coset state, measuring the name of the irreducible representation for each state, followed by a joint measurement over the resulting lower dimensional space. This shows that the “strong standard method” cannot be used to implement the optimal set of measurements. For some instances of the hidden shift problem, we give a quantum algorithms that are exponentially faster than the best known classical algorithm. The algorithms make use of the Fourier transform in a way that may be interpreted as solving a deconvolution problem. As evidence of hardness, we give a reduction from algebraically homomorphic cryptosystems to the shifted Legendre symbol problem. This is an example of a problem which admits an exponential quantum speedup yet is not an instance of the abelian hidden subgroup problem.
The hidden subgroup problem is the foundation of many quantum algorithms. An efficient solution is known for the problem over abelian groups, employed by both Simon's algorithm and Shor's factoring and discrete log algorithms. The nonabelian case, however, remains open; an efficient solution would give rise to an efficient quantum algorithm for graph isomorphism. We fully analyze a natural generalization of the algorithm for the abelian case to the nonabelian case and show that the algorithm determines the normal core of a hidden subgroup: in particular, normal subgroups can be determined. We show, however, that this immediate generalization of the abelian algorithm does not efficiently solve graph isomorphism.
We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of nonabelian solvable groups, including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in Zpn\mathbb{Z}_p^nZpn​, whenever ppp is a fixed prime. For the induction step, we introduce the problem Translating Coset generalizing both Hidden Translation and Hidden Subgroup and prove a powerful self-reducibility result: Translating Coset in a finite solvable group GGG is reducible to instances of Translating Coset in G/NG/NG/N and NNN, for appropriate normal subgroups NNN of GGG. Our self-reducibility framework, combined with Kuperberg's subexponential quantum algorithm for solving Hidden Translation in any abelian group, leads to subexponential quantum algorithms for Hidden Translation and Hidden Subgroup in any solvable group.