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

Quantum Information and Computation

Reduction from non-injective hidden shift problem to injective hidden shift problem

GharibiMirmojtaba

Published Mar 1, 2013• 0 citations
Publisher

Abstract

We introduce a simple tool that can be used to reduce non-injective instances of the hidden shift problem over arbitrary group to injective instances over the same group. In particular, we show tha...
DOI
10.5555/2481602.2481606

Related papers

On the sample complexity of the generalized hidden shift problem over arbitrary finite groups

Juntai Zhou

We formulate the generalized hidden shift problem over arbitrary finite groups and obtain upper and lower bounds for the sample complexity in terms of group theoretic data.

quant-pharXiv:2609.05828•Sep 8, 2026•0 citations

Reduction from non-injective hidden shift problem to injective hidden shift problem

Mirmojtaba Gharibi

We introduce a simple tool that can be used to reduce non-injective instances of the hidden shift problem over arbitrary group to injective instances over the same group. In particular, we show that the average-case non-injective hidden shift problem admit this reduction. We show similar results for (non-injective) hidden shift problem for bent functions. We generalize the notion of influence and show how it relates to applicability of this tool for doing reductions. In particular, these results can be used to simplify the main results by Gavinsky, Roetteler, and Roland about the hidden shift problem for the Boolean-valued functions and bent functions, and also to generalize their results to non-Boolean domains (thereby answering an open question that they pose).

arXiv:1207.4537•Quantum Information and Computation•Mar 1, 2013•3 citations

The non-injective hidden shift problem

Mirmojtaba Gharibi

In this work, we mostly concentrate on the hidden shift problem for non-injective functions. It is worthwhile to know that the query complexity of the non-injective hidden shift problem is exponential in the worst case by the well known bounds on the unstructured search problem. Hence, we can make this problem more tractable by imposing additional constraints on the problem. Perhaps the first constraint that comes to mind is to address the average case problem. In this work, we show that the average case non-injective hidden shift problem can be reduced to the injective hidden shift problem by giving one such reduction. The reduction is based on a tool we developed called injectivization. The result is strong in the sense that the underlying group can be any finite group and that the non-injective functions for which we have defined the hidden shift problem can have range in an arbitrary finite set. Using this tool, we simplify the main result of a recent paper by about the hidden shift problem for Boolean-valued functions by reducing that problem to Simon's problem. They also posed an open question which is subject to personal interpretation. We answer the seemingly most general interpretation of the question. However, we use our own techniques in doing so (the authors ask if their techniques can be used for addressing that problem). Another constraint that one can consider is to have a promise on the structure of the functions. In this work we consider the hidden shift problem for c-almost generalized bent functions. A class of functions which we defined that includes the generalized bent functions. Then we turn our attention toward the generalized hidden shift problem which is easier than injective hidden shift problem and hence more tractable. We state some of our observations about this problem. Finally we show that the average classical query complexity of the non-injective hidden shift problem over groups of form (Z/mZ)^n when m is a constant is exponential, which also immediately implies that the classical average query complexity of the non-injective hidden shift problem is exponential. We also show that the worst-case classical query complexity of the generalized injective hidden shift problem over the same group is high, which implies that the classical query complexity of the hidden shift problem is high.

•Jan 19, 2012•1 citation

A Fusion Algorithm for Solving the Hidden Shift Problem in Finite Abelian Groups

Wouter Castryck, Ann Dooms, Carlo Emerencia +1 more

Lecture notes in computer science•Jan 1, 2021•7 citations

Quantum algorithms for the hidden subgroup problem on some semi-direct product groups by reduction to Abelian cases

Dong Pyo Chi, Jeong San Kim, Soojoon Lee

Physics Letters A•Jun 14, 2006•7 citations

Learning quantum symmetries

Isaac Holt, Sathyawageeswar Subramanian

Quantum algorithms are powerful tools for finding symmetries of classical objects, most famously through Shor's algorithm and the Hidden Subgroup Problem (HSP). In this work, we study quantum algorithms for learning symmetries of \emph{quantum} objects. Existing work in this area centres on the recently introduced State Hidden Subgroup Problem (StateHSP), a quantum generalisation of HSP in which the task is to learn the symmetry subgroup of a quantum state. We develop efficient quantum algorithms for non-abelian StateHSP when the hidden subgroup is normal and the ambient group belongs to a broad class of non-abelian groups, extending the previous general theory beyond the abelian setting. StateHSP learns \emph{Bose} symmetries, under which a state must be invariant exactly under the action of the symmetry group. In quantum mechanics, however, physically equivalent pure states are defined only up to global phase. Motivated by this, we introduce a natural notion of \emph{Anyonic} state symmetry learning, based on invariance up to global phase. We give an efficient quantum algorithm by reducing the problem to StateHSP, where the reduction rests on a new correspondence between linearisations of projective representations and linear error-correcting codes. As an application, we obtain an improved algorithm for learning stabiliser groups of mixed qudit states of arbitrary local dimension. Finally, we introduce symmetry learning problems for other quantum objects, including unitaries, Hamiltonians, and finite collections of states, and give efficient algorithms for them by reduction to state symmetry learning. Together, these results broaden the scope of state symmetry learning as a common algorithmic primitive for learning quantum symmetries.

quant-pharXiv:2609.38085•Sep 30, 2026•0 citations
We introduce a simple tool that can be used to reduce non-injective instances of the hidden shift problem over arbitrary group to injective instances over the same group. In particular, we show that the average-case non-injective hidden shift problem admit this reduction. We show similar results for (non-injective) hidden shift problem for bent functions. We generalize the notion of influence and show how it relates to applicability of this tool for doing reductions. In particular, these results can be used to simplify the main results by Gavinsky, Roetteler, and Roland about the hidden shift problem for the Boolean-valued functions and bent functions, and also to generalize their results to non-Boolean domains (thereby answering an open question that they pose).
In this work, we mostly concentrate on the hidden shift problem for non-injective functions. It is worthwhile to know that the query complexity of the non-injective hidden shift problem is exponential in the worst case by the well known bounds on the unstructured search problem. Hence, we can make this problem more tractable by imposing additional constraints on the problem. Perhaps the first constraint that comes to mind is to address the average case problem. In this work, we show that the average case non-injective hidden shift problem can be reduced to the injective hidden shift problem by giving one such reduction. The reduction is based on a tool we developed called injectivization. The result is strong in the sense that the underlying group can be any finite group and that the non-injective functions for which we have defined the hidden shift problem can have range in an arbitrary finite set. Using this tool, we simplify the main result of a recent paper by about the hidden shift problem for Boolean-valued functions by reducing that problem to Simon's problem. They also posed an open question which is subject to personal interpretation. We answer the seemingly most general interpretation of the question. However, we use our own techniques in doing so (the authors ask if their techniques can be used for addressing that problem). Another constraint that one can consider is to have a promise on the structure of the functions. In this work we consider the hidden shift problem for c-almost generalized bent functions. A class of functions which we defined that includes the generalized bent functions. Then we turn our attention toward the generalized hidden shift problem which is easier than injective hidden shift problem and hence more tractable. We state some of our observations about this problem. Finally we show that the average classical query complexity of the non-injective hidden shift problem over groups of form (Z/mZ)^n when m is a constant is exponential, which also immediately implies that the classical average query complexity of the non-injective hidden shift problem is exponential. We also show that the worst-case classical query complexity of the generalized injective hidden shift problem over the same group is high, which implies that the classical query complexity of the hidden shift problem is high.
Quantum algorithms are powerful tools for finding symmetries of classical objects, most famously through Shor's algorithm and the Hidden Subgroup Problem (HSP). In this work, we study quantum algorithms for learning symmetries of \emph{quantum} objects. Existing work in this area centres on the recently introduced State Hidden Subgroup Problem (StateHSP), a quantum generalisation of HSP in which the task is to learn the symmetry subgroup of a quantum state. We develop efficient quantum algorithms for non-abelian StateHSP when the hidden subgroup is normal and the ambient group belongs to a broad class of non-abelian groups, extending the previous general theory beyond the abelian setting. StateHSP learns \emph{Bose} symmetries, under which a state must be invariant exactly under the action of the symmetry group. In quantum mechanics, however, physically equivalent pure states are defined only up to global phase. Motivated by this, we introduce a natural notion of \emph{Anyonic} state symmetry learning, based on invariance up to global phase. We give an efficient quantum algorithm by reducing the problem to StateHSP, where the reduction rests on a new correspondence between linearisations of projective representations and linear error-correcting codes. As an application, we obtain an improved algorithm for learning stabiliser groups of mixed qudit states of arbitrary local dimension. Finally, we introduce symmetry learning problems for other quantum objects, including unitaries, Hamiltonians, and finite collections of states, and give efficient algorithms for them by reduction to state symmetry learning. Together, these results broaden the scope of state symmetry learning as a common algorithmic primitive for learning quantum symmetries.