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/0304090

Hidden symmetry detection on a quantum computer

Ralf Schützhold, William George Unruh

Published Apr 12, 2003• 0 citations
arXivHTMLPDF

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). PACS: 03.67.Lx, 89.70.+c.

DOI
10.48550/arxiv.quant-ph/0304090

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).

Quantum Information and Computation•Jan 1, 2007•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

Hidden Symmetry Subgroup Problems

Thomas Decker, Gábor Ivanyos, Miklós Sántha +1 more

We advocate a new approach for addressing hidden structure problems and finding efficient quantum algorithms. We introduce and investigate the hidden symmetry subgroup problem (HSSP), which is a generalization of the well-studied hidden subgroup problem (HSP). Given a group acting on a set and an oracle whose level sets define a partition of the set, the task is to recover the subgroup of symmetries of this partition inside the group. The HSSP provides a unifying framework that, besides the HSP, encompasses a wide range of algebraic oracle problems, including quadratic hidden polynomial problems. While the HSSP can have provably exponential quantum query complexity, we obtain efficient quantum algorithms for various interesting cases. To achieve this, we present a general method for reducing the HSSP to the HSP, which works efficiently in several cases related to symmetries of polynomials. The HSSP therefore connects in a rather surprising way certain hidden polynomial problems with the HSP. Using this connection, we obtain the first efficient quantum algorithm for the hidden polynomial problem for multivariate quadratic polynomials over fields of constant characteristic. We also apply the new methods to polynomial function graph problems and present an efficient quantum procedure for constant degree multivariate polynomials over any field. This result improves in several ways the currently known algorithms.

arXiv:1107.2189•SIAM Journal on Computing•Jan 1, 2013•7 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). PACS: 03.67.Lx, 89.70.+c.
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).
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.
We advocate a new approach for addressing hidden structure problems and finding efficient quantum algorithms. We introduce and investigate the hidden symmetry subgroup problem (HSSP), which is a generalization of the well-studied hidden subgroup problem (HSP). Given a group acting on a set and an oracle whose level sets define a partition of the set, the task is to recover the subgroup of symmetries of this partition inside the group. The HSSP provides a unifying framework that, besides the HSP, encompasses a wide range of algebraic oracle problems, including quadratic hidden polynomial problems. While the HSSP can have provably exponential quantum query complexity, we obtain efficient quantum algorithms for various interesting cases. To achieve this, we present a general method for reducing the HSSP to the HSP, which works efficiently in several cases related to symmetries of polynomials. The HSSP therefore connects in a rather surprising way certain hidden polynomial problems with the HSP. Using this connection, we obtain the first efficient quantum algorithm for the hidden polynomial problem for multivariate quadratic polynomials over fields of constant characteristic. We also apply the new methods to polynomial function graph problems and present an efficient quantum procedure for constant degree multivariate polynomials over any field. This result improves in several ways the currently known algorithms.