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

arXiv:quant-ph/0612107 · Quantum Information and Computation

How a Clebsch-Gordan transform helps to solve the Heisenberg hidden subgroup problem

Dave Bacon

Published May 1, 2008• 15 citations
arXivHTMLPDF

Abstract

It has recently been shown that quantum computers can efficiently solve the Heisenberg hidden subgroup problem, a problem whose classical query complexity is exponential. This quantum algorithm was discovered within the framework of using pretty good measurements for obtaining optimal measurements in the hidden subgroup problem. Here we show how to solve the Heisenberg hidden subgroup problem using arguments based instead on the symmetry of certain hidden subgroup states. The symmetry we consider leads naturally to a unitary transform known as the Clebsch-Gordan transform over the Heisenberg group. This gives a new representation theoretic explanation for the pretty good measurement derived algorithm for efficiently solving the Heisenberg hidden subgroup problem and provides evidence that Clebsch-Gordan transforms over finite groups are a new primitive in quantum algorithm design.

DOI
10.26421/qic8.5-6

Related papers

How a Clebsch-Gordan transform helps to solve the Heisenberg hidden subgroup problem

BaconD.

It has recently been shown that quantum computers can efficiently solve the Heisenberg hidden subgroup problem, a problem whose classical query complexity is exponential. This quantum algorithm was...

Quantum Information and Computation•May 1, 2008•0 citations

From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups

Dave Bacon, Andrew M. Childs, Wim van Dam

We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form /spl Zopf//sub p/ /sup r/ /spl times/ /spl Zopf//sub p/ fixed r (including the Heisenberg group, r = 2). In particular our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP.

arXiv:quant-ph/0504083•Annual Symposium on Foundations of Computer Science•Nov 15, 2005•124 citations

An Efficient Quantum Algorithm for the Hidden Subgroup Problem over Weyl-Heisenberg Groups

Hari Krovi, Martin Roetteler

Many exponential speedups that have been achieved in quantum computing are obtained via hidden subgroup problems (HSPs). We show that the HSP over Weyl-Heisenberg groups can be solved efficiently on a quantum computer. These groups are well-known in physics and play an important role in the theory of quantum error-correcting codes. Our algorithm is based on non-commutative Fourier analysis of coset states which are quantum states that arise from a given black-box function. We use Clebsch-Gordan decompositions to combine and reduce tensor products of irreducible representations. Furthermore, we use a new technique of changing labels of irreducible representations to obtain low-dimensional irreducible representations in the decomposition process. A feature of the presented algorithm is that in each iteration of the algorithm the quantum computer operates on two coset states simultaneously. This is an improvement over the previously best known quantum algorithm for these groups which required four coset states.

arXiv:0810.3695•Oct 20, 2008•0 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

Simon's Algorithm, Clebsch-Gordan Sieves, and Hidden Symmetries of Multiple Squares

Dave Bacon

The first quantum algorithm to offer an exponential speedup (in the query complexity setting) over classical algorithms was Simon's algorithm for identifying a hidden exclusive-or mask. Here we observe how part of Simon's algorithm can be interpreted as a Clebsch-Gordan transform. Inspired by this we show how Clebsch-Gordan transforms can be used to efficiently find a hidden involution on the group G^n where G is the dihedral group of order eight (the group of symmetries of a square.) This problem previously admitted an efficient quantum algorithm but a connection to Clebsch-Gordan transforms had not been made. Our results provide further evidence for the usefulness of Clebsch-Gordan transform in quantum algorithm design.

arXiv:0808.0174•Aug 1, 2008•1 citation

Implementing measurements and optimizing queries for the quantum hidden subgroup problem

Asif Shakeel

This dissertation concerns the Hidden Subgroup Problem (HSP) in quantum computation. We explore certain facets of the problem which, we expect, will lead towards a general framework for understanding such problems. We first present an implementation of an optimal measurement, the Pretty Good Measurement (PGM), for the problem of the hidden subgroup problem over the dihedral group. This is a problem for which no efficient algorithm is known. This problem is relevant to the shortest vector in a lattice problem (SVP) in cryptography. We give a representation theoretic implementation of the PGM, achievable with only abelian transforms. The subset sum problem, an NP-complete problem, is needed in identification of certain subspaces. There are some novel ideas and techniques used in the implementation that make it realizable. This brings into focus how a measurement specified through a POVM (positive operator valued measure) is achievable through a basis change in a particular representation. This has connections to the HSP for other groups. We also study the question of optimal query selection to maximize the probability of subgroup identification. This part of the research complements a well-researched topic of finding optimal measurements in the spirit of state discrimination as applied to the hidden subgroup problem. We find the optimal query, the "character query", over a class of queries that are an equal superposition over the group, for oracles that take values in a finite abelian group. This query outperforms the query used in the "standard method" of the HSP. This approach has connections to other domains of quantum computation. We then extend the query selection idea to the case of multiple queries in the HSP and find examples in which this gives significant gains over the standard method. We consider the problems that the analysis of this more general problem entails, and outline a possible program to be followed. This is a part of continuing research

•Jan 1, 2011•0 citations
It has recently been shown that quantum computers can efficiently solve the Heisenberg hidden subgroup problem, a problem whose classical query complexity is exponential. This quantum algorithm was discovered within the framework of using pretty good measurements for obtaining optimal measurements in the hidden subgroup problem. Here we show how to solve the Heisenberg hidden subgroup problem using arguments based instead on the symmetry of certain hidden subgroup states. The symmetry we consider leads naturally to a unitary transform known as the Clebsch-Gordan transform over the Heisenberg group. This gives a new representation theoretic explanation for the pretty good measurement derived algorithm for efficiently solving the Heisenberg hidden subgroup problem and provides evidence that Clebsch-Gordan transforms over finite groups are a new primitive in quantum algorithm design.
We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form /spl Zopf//sub p/ /sup r/ /spl times/ /spl Zopf//sub p/ fixed r (including the Heisenberg group, r = 2). In particular our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP.
Many exponential speedups that have been achieved in quantum computing are obtained via hidden subgroup problems (HSPs). We show that the HSP over Weyl-Heisenberg groups can be solved efficiently on a quantum computer. These groups are well-known in physics and play an important role in the theory of quantum error-correcting codes. Our algorithm is based on non-commutative Fourier analysis of coset states which are quantum states that arise from a given black-box function. We use Clebsch-Gordan decompositions to combine and reduce tensor products of irreducible representations. Furthermore, we use a new technique of changing labels of irreducible representations to obtain low-dimensional irreducible representations in the decomposition process. A feature of the presented algorithm is that in each iteration of the algorithm the quantum computer operates on two coset states simultaneously. This is an improvement over the previously best known quantum algorithm for these groups which required four coset states.
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 first quantum algorithm to offer an exponential speedup (in the query complexity setting) over classical algorithms was Simon's algorithm for identifying a hidden exclusive-or mask. Here we observe how part of Simon's algorithm can be interpreted as a Clebsch-Gordan transform. Inspired by this we show how Clebsch-Gordan transforms can be used to efficiently find a hidden involution on the group G^n where G is the dihedral group of order eight (the group of symmetries of a square.) This problem previously admitted an efficient quantum algorithm but a connection to Clebsch-Gordan transforms had not been made. Our results provide further evidence for the usefulness of Clebsch-Gordan transform in quantum algorithm design.
This dissertation concerns the Hidden Subgroup Problem (HSP) in quantum computation. We explore certain facets of the problem which, we expect, will lead towards a general framework for understanding such problems. We first present an implementation of an optimal measurement, the Pretty Good Measurement (PGM), for the problem of the hidden subgroup problem over the dihedral group. This is a problem for which no efficient algorithm is known. This problem is relevant to the shortest vector in a lattice problem (SVP) in cryptography. We give a representation theoretic implementation of the PGM, achievable with only abelian transforms. The subset sum problem, an NP-complete problem, is needed in identification of certain subspaces. There are some novel ideas and techniques used in the implementation that make it realizable. This brings into focus how a measurement specified through a POVM (positive operator valued measure) is achievable through a basis change in a particular representation. This has connections to the HSP for other groups. We also study the question of optimal query selection to maximize the probability of subgroup identification. This part of the research complements a well-researched topic of finding optimal measurements in the spirit of state discrimination as applied to the hidden subgroup problem. We find the optimal query, the "character query", over a class of queries that are an equal superposition over the group, for oracles that take values in a finite abelian group. This query outperforms the query used in the "standard method" of the HSP. This approach has connections to other domains of quantum computation. We then extend the query selection idea to the case of multiple queries in the HSP and find examples in which this gives significant gains over the standard method. We consider the problems that the analysis of this more general problem entails, and outline a possible program to be followed. This is a part of continuing research