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/0208184 · Fundamenta Informaticae

Quantum Testers for Hidden Group Properties

Katalin Friedl, Miklós Sántha, Frédéric Magniez, Pranab Sen

Published Jan 1, 2009• 16 citations
arXivHTMLPDF

Abstract

We construct efficient or query efficient quantum property testers for two existential group properties which have exponential query complexity both for their decision problem in the quantum and for their testing problem in the classical model of computing. These are periodicity in groups and the common coset range property of two functions having identical ranges within each coset of some normal subgroup. Our periodicity tester is efficient in Abelian groups and generalizes, in several aspects, previous periodicity testers. This is achieved by introducing a technique refining the majority correction process widely used for proving robustness of algebraic properties. The periodicity tester in non-Abelian groups and the common coset range tester are query efficient.

DOI
10.3233/fi-2009-0046

Related papers

Efficient quantum algorithms for (Gapped) group testing and junta testing

Andris Ambainis, Aleksandrs Belovs, Oded Regev +1 more

In the k-junta testing problem, a tester has to efficiently decide whether a given function f: {0,1}n → {0,1} is a k-junta (i.e., depends on at most k of its input bits) or is ∈-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity Ō(√∈) and time complexity Ō(n√∈). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atici and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of ω(k1/3) queries for junta-testing (for constant ∈).

•Jan 1, 2016•20 citations

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

Andris Ambainis, Aleksandrs Belovs, Oded Regev +1 more

In the k-junta testing problem, a tester has to efficiently decide whether a given function f: {0, 1}n → {0, 1} is a k-junta (i.e., depends on at most k of its input bits) or is ∊-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity and time complexity . This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Ω(k1/3) queries for junta-testing (for constant ∊).

ACM-SIAM Symposium on Discrete Algorithms (SODA)•Dec 21, 2015•41 citations

Hidden translation and orbit coset in quantum computing

Katalin Friedl, Gábor Ivanyos, Frédéric Magniez +2 more

We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of non-abelian groups including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in Z pn, whenever p is a fixed prime. For the induction step, we introduce the problem Orbit Coset generalizing both Hidden Translation and Hidden Subgroup, and prove a powerful self-reducibility result: Orbit Coset in a finite group G is reducible to Orbit Coset in G/N and subgroups of N, for any solvable normal subgroup N of G.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2003•132 citations

Hidden translation and orbit coset in quantum computing

Katalin Friedl, Gábor Ivanyos, Frédéric Magniez +2 more

We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of non-abelian groups including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in Z pn, whenever p is a fixed prime. For the induction step, we introduce the problem Orbit Coset generalizing both Hidden Translation and Hidden Subgroup, and prove a powerful self-reducibility result: Orbit Coset in a finite group G is reducible to Orbit Coset in G/N and subgroups of N, for any solvable normal subgroup N of G.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 2003•10 citations

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

Andris Ambainis, Aleksandrs Belovs, Oded Regev +1 more

In the $k$-junta testing problem, a tester has to efficiently decide whether a given function $f:\{0,1\}^n\rightarrow \{0,1\}$ is a $k$-junta (i.e., depends on at most $k$ of its input bits) or is $ε$-far from any $k$-junta. Our main result is a quantum algorithm for this problem with query complexity $\tilde O(\sqrt{k/ε})$ and time complexity $\tilde O(n\sqrt{k/ε})$. This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of $Ω(k^{1/3})$ queries for junta-testing (for constant $ε$).

arXiv:1507.03126•Jul 11, 2015•14 citations

Efficient quantum algorithms to find substructures on finite algebras

J. M. Hernández Cáceres, I. F. Rúa, Elías F. Combarro

When classifying a collection of finite algebras (for instance, in the computational classification of finite semifields), an important task is the determination of substructures such as the right, middle, and left nuclei, the nucleus, and the center. Finding these structures may become computationally expensive when there is no additional information about the algebra properties. In this paper, we introduce quantum algorithms than solve this task efficiently, by formulating it as an instance of the Hidden Subgroup Problem (HSP) {over Abelian groups}. We give detailed constructions of the quantum circuits involved in the process and prove that the overall (quantum) complexity of our algorithm is polynomial in the dimension of the algebra, while a similar approach with classical computers would require an exponential number of queries to the HSP function

Quantum Information and Computation•Dec 1, 2023•1 citation
We construct efficient or query efficient quantum property testers for two existential group properties which have exponential query complexity both for their decision problem in the quantum and for their testing problem in the classical model of computing. These are periodicity in groups and the common coset range property of two functions having identical ranges within each coset of some normal subgroup. Our periodicity tester is efficient in Abelian groups and generalizes, in several aspects, previous periodicity testers. This is achieved by introducing a technique refining the majority correction process widely used for proving robustness of algebraic properties. The periodicity tester in non-Abelian groups and the common coset range tester are query efficient.
In the k-junta testing problem, a tester has to efficiently decide whether a given function f: {0,1}n → {0,1} is a k-junta (i.e., depends on at most k of its input bits) or is ∈-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity Ō(√∈) and time complexity Ō(n√∈). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atici and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of ω(k1/3) queries for junta-testing (for constant ∈).
In the k-junta testing problem, a tester has to efficiently decide whether a given function f: {0, 1}n → {0, 1} is a k-junta (i.e., depends on at most k of its input bits) or is ∊-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity and time complexity . This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Ω(k1/3) queries for junta-testing (for constant ∊).
We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of non-abelian groups including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in Z pn, whenever p is a fixed prime. For the induction step, we introduce the problem Orbit Coset generalizing both Hidden Translation and Hidden Subgroup, and prove a powerful self-reducibility result: Orbit Coset in a finite group G is reducible to Orbit Coset in G/N and subgroups of N, for any solvable normal subgroup N of G.
We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of non-abelian groups including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in Z pn, whenever p is a fixed prime. For the induction step, we introduce the problem Orbit Coset generalizing both Hidden Translation and Hidden Subgroup, and prove a powerful self-reducibility result: Orbit Coset in a finite group G is reducible to Orbit Coset in G/N and subgroups of N, for any solvable normal subgroup N of G.
In the kkk-junta testing problem, a tester has to efficiently decide whether a given function f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow \{0,1\}f:{0,1}n→{0,1} is a kkk-junta (i.e., depends on at most kkk of its input bits) or is εεε-far from any kkk-junta. Our main result is a quantum algorithm for this problem with query complexity O~(k/ε)\tilde O(\sqrt{k/ε})O~(k/ε​) and time complexity O~(nk/ε)\tilde O(n\sqrt{k/ε})O~(nk/ε​). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Ω(k1/3)Ω(k^{1/3})Ω(k1/3) queries for junta-testing (for constant εεε).
When classifying a collection of finite algebras (for instance, in the computational classification of finite semifields), an important task is the determination of substructures such as the right, middle, and left nuclei, the nucleus, and the center. Finding these structures may become computationally expensive when there is no additional information about the algebra properties. In this paper, we introduce quantum algorithms than solve this task efficiently, by formulating it as an instance of the Hidden Subgroup Problem (HSP) {over Abelian groups}. We give detailed constructions of the quantum circuits involved in the process and prove that the overall (quantum) complexity of our algorithm is polynomial in the dimension of the algebra, while a similar approach with classical computers would require an exponential number of queries to the HSP function