Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Hidden subgroup problem
Summary
The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. The framework captures problems such as factoring, discrete logarithm, graph isomorphism, and the shortest vector problem. This makes it especially important in the theory of quantum computing because Shor's quantum algorithm for factoring is an instance of the hidden subgroup problem for finite Abelian groups, while the other problems correspond to finite groups that are not Abelian.
Given a group , a subgroup , and a set , we say a function hides the subgroup if for all if and only if . Equivalently, is constant on the cosets of H, while it is different between the different cosets of H.
Hidden subgroup problem: Let be a group, a finite set, and a function that hides a subgroup . The function is given via an oracle, which uses bits. Using information gained from evaluations of via its oracle, determine a generating set for .
A special case is when is a group and is a group homomorphism in which case corresponds to the kernel of .
The hidden subgroup problem is especially important in the theory of quantum computing for the following reasons.
Shor's quantum algorithm for factoring and discrete logarithm (as well as several of its extensions) relies on the ability of quantum computers to solve the HSP for finite Abelian groups.
The existence of efficient quantum algorithms for HSPs for certain non-Abelian groups would imply efficient quantum algorithms for two major problems: the graph isomorphism problem and certain shortest vector problems (SVPs) in lattices. More precisely, an efficient quantum algorithm for the HSP for the symmetric group would give a quantum algorithm for the graph isomorphism. An efficient quantum algorithm for the HSP for the dihedral group would give a quantum algorithm for the unique SVP.
There is an efficient quantum algorithm for solving HSP over finite Abelian groups in time polynomial in . For arbitrary groups, it is known that the hidden subgroup problem is solvable using a polynomial number of evaluations of the oracle.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications (14)
Related people (1)
Related concepts (4)
Quantum Fourier transform
In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem. The quantum Fourier transform was discovered by Don Coppersmith.
Shor's algorithm
Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (that is, non-quantum) algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future.
Quantum algorithm
In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer.
Related courses (1)
CS-308: Introduction to quantum computation
The course introduces the paradigm of quantum computation in an axiomatic way. We introduce the notion of quantum bit, gates, circuits and we treat the most important quantum algorithms. We also touch
Related lectures (10)
Hidden Subgroup Algorithm
Continues the discussion on Simon's hidden subgroup problem, focusing on finding a basis.
Hidden Sub-group Problem and Simon Algorithm
Explores the hidden sub-group problem and Simon algorithm in quantum computing.
Groups and Numbers: Hidden Subgroup Problem
Explores groups and numbers, emphasizing the hidden subgroup problem and its complexities in classic and quantum algorithms.