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

Hidden symmetry detection on a quantum computer

Ralf Schützhold, William George Unruh

Published Jan 1, 2007• 0 citations
Publisher

Abstract

The fastest quantum algorithms (for the solution of classical computational tasks) known so far are basically variations of the hidden subgroup problem with {$f(U[x])=f(x)$}. Following a discussion regarding which tasks might be solved efficiently by quantum computers, it will be demonstrated by means of a simple example, that the detection of more general hidden (two-point) symmetries {$V\{f(x),f(U[x])\}=0$} by a quantum algorithm can also admit an exponential speed-up. E.g., one member of this class of symmetries {$V\{f(x),f(U[x])\}=0$} is discrete self-similarity (or discrete scale invariance).

DOI
10.26421/qic7.1-2-4

Related papers

Hidden symmetry detection on a quantum computer

Ralf Schützhold, William George Unruh

The fastest quantum algorithms (for the solution of classical computational tasks) known so far are basically variations of the hidden subgroup problem with {$f(U[x])=f(x)$}. Following a discussion regarding which tasks might be solved efficiently by quantum computers, it will be demonstrated by means of a simple example, that the detection of more general hidden (two-point) symmetries {$V\{f(x),f(U[x])\}=0$} by a quantum algorithm can also admit an exponential speed-up. E.g., one member of this class of symmetries {$V\{f(x),f(U[x])\}=0$} is discrete self-similarity (or discrete scale invariance). PACS: 03.67.Lx, 89.70.+c.

arXiv:quant-ph/0304090•Apr 12, 2003•0 citations

Hidden symmetry detection on a quantum computer

Ralf Schützhold, William George Unruh

The fastest quantum algorithms (for the solution of classical computational problems) known so far are basically variations of the hidden subgroup problem f(U[x])=f(x). By means of some simple examples it is demonstrated that the detection of more general hidden (two-point) symmetries V{f(x),f(U[x])}=0 by a quantum computer can also admit an exponential speed-up. PACS: 03.67.Lx, 03.67.-a, 89.70.+c.

•Apr 12, 2003•0 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

Efficient Quantum Algorithms (In German: Effiziente Quantenalgorithmen)

Andreas Klappenecker, Martin Roetteler

Ever since the discovery of efficient quantum algorithms for factoring and computing discrete logarithms by Shor in 1994, the interest in quantum algorithms was growing within the theoretical computer science as well as the physics community. Surprisingly, the number of quantum algorithms found so far is quite small, although the number of researchers working on the subject is rapidly increasing. In fact, the task of designing new quantum algorithms has been proven to be extremely difficult. We give an overview of the problems for which an efficient quantum algorithm is known and briefly describe the underlying ideas. One large area of problems where a quantum computer appears to be superior to classical computers are the so-called hidden subgroup problems. We explain the relevance and the motivation behind this abstract class of problems.

•Jan 1, 2006•0 citations

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

Quantum Algorithms

Michele Mosca

This article surveys the state of the art in quantum computer algorithms, including both black-box and non-black-box results. It is infeasible to detail all the known quantum algorithms, so a representative sample is given. This includes a summary of the early quantum algorithms, a description of the Abelian Hidden Subgroup algorithms (including Shor's factoring and discrete logarithm algorithms), quantum searching and amplitude amplification, quantum algorithms for simulating quantum mechanical systems, several non-trivial generalizations of the Abelian Hidden Subgroup Problem (and related techniques), the quantum walk paradigm for quantum algorithms, the paradigm of adiabatic algorithms, a family of ``topological'' algorithms, and algorithms for quantum tasks which cannot be done by a classical computer, followed by a discussion.

•Aug 4, 2008•27 citations
The fastest quantum algorithms (for the solution of classical computational tasks) known so far are basically variations of the hidden subgroup problem with {f(U[x])=f(x)f(U[x])=f(x)f(U[x])=f(x)}. Following a discussion regarding which tasks might be solved efficiently by quantum computers, it will be demonstrated by means of a simple example, that the detection of more general hidden (two-point) symmetries {V{f(x),f(U[x])}=0V\{f(x),f(U[x])\}=0V{f(x),f(U[x])}=0} by a quantum algorithm can also admit an exponential speed-up. E.g., one member of this class of symmetries {V{f(x),f(U[x])}=0V\{f(x),f(U[x])\}=0V{f(x),f(U[x])}=0} is discrete self-similarity (or discrete scale invariance).
The fastest quantum algorithms (for the solution of classical computational tasks) known so far are basically variations of the hidden subgroup problem with {f(U[x])=f(x)f(U[x])=f(x)f(U[x])=f(x)}. Following a discussion regarding which tasks might be solved efficiently by quantum computers, it will be demonstrated by means of a simple example, that the detection of more general hidden (two-point) symmetries {V{f(x),f(U[x])}=0V\{f(x),f(U[x])\}=0V{f(x),f(U[x])}=0} by a quantum algorithm can also admit an exponential speed-up. E.g., one member of this class of symmetries {V{f(x),f(U[x])}=0V\{f(x),f(U[x])\}=0V{f(x),f(U[x])}=0} is discrete self-similarity (or discrete scale invariance). PACS: 03.67.Lx, 89.70.+c.
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.
Ever since the discovery of efficient quantum algorithms for factoring and computing discrete logarithms by Shor in 1994, the interest in quantum algorithms was growing within the theoretical computer science as well as the physics community. Surprisingly, the number of quantum algorithms found so far is quite small, although the number of researchers working on the subject is rapidly increasing. In fact, the task of designing new quantum algorithms has been proven to be extremely difficult. We give an overview of the problems for which an efficient quantum algorithm is known and briefly describe the underlying ideas. One large area of problems where a quantum computer appears to be superior to classical computers are the so-called hidden subgroup problems. We explain the relevance and the motivation behind this abstract class of problems.
This article surveys the state of the art in quantum computer algorithms, including both black-box and non-black-box results. It is infeasible to detail all the known quantum algorithms, so a representative sample is given. This includes a summary of the early quantum algorithms, a description of the Abelian Hidden Subgroup algorithms (including Shor's factoring and discrete logarithm algorithms), quantum searching and amplitude amplification, quantum algorithms for simulating quantum mechanical systems, several non-trivial generalizations of the Abelian Hidden Subgroup Problem (and related techniques), the quantum walk paradigm for quantum algorithms, the paradigm of adiabatic algorithms, a family of ``topological'' algorithms, and algorithms for quantum tasks which cannot be done by a classical computer, followed by a discussion.