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

LMS Journal of Computation and Mathematics

Extending the Promise of the Deutsch–Jozsa–Høyer Algorithm for Finite Groups

Michael Batty, Andrew J. Duncan, Samuel L. Braunstein

Published Jan 1, 2006• 3 citations
Publisher

Abstract

Abstract Høyer has given a generalisation of the Deutsch–Jozsa algorithm which uses the Fourier transform on a group G which is (in general) non-Abelian. His algorithm distinguishes between functions which are either perfectly balanced (m-to-one) or constant, with certainty, and using a single quantum query. Here, we show that this algorithm (which we call the Deutsch–Jozsa–Høyer algorithm) can in fact deal with a broader range of promises, which we define in terms of the irreducible representations of G.

DOI
10.1112/s1461157000001182

Related papers

Extending the Promise of the Deutsch--Jozsa--Hoyer Algorithm for Finite Groups

Batty, Michael, Samuel L. Braunstein, Andrew J. Duncan

Hoyer has given a generalisation of the Deutsch--Jozsa algorithm which uses the Fourier transform on a group G which is (in general) non-Abelian. His algorithm distinguishes between functions which are either perfectly balanced (m-to-one) or constant, with certainty, and using a single quantum query. Here, we show that this algorithm (which we call the Deutsch--Jozsa--Hoyer algorithm) can in fact deal with a broader range of promises, which we define in terms of the irreducible representations of G.

arXiv:quant-ph/0412067•Dec 8, 2004•1 citation

A Generalization of the Deutsch-Jozsa Algorithm to Multi-Valued Quantum Logic

Yale Fan

We generalize the binary Deutsch-Jozsa algorithm to n- valued logic using the quantum Fourier transform. Our algorithm is not only able to distinguish between constant and balanced Boolean functions in a single query, but can also find closed expressions for classes of affine functions in quantum oracles, accurate to a constant term.

arXiv:0809.0932•IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2007•26 citations

Quantum Query Algorithms

Walid E. Gomaa

This presentation gives a comprehensive overview of quantum query algorithms, beginning with an introduction to the query model of computation where input is accessed via an oracle function. It then details several foundational quantum algorithms that demonstrate a quantum advantage over classical approaches: Deutsch's problem is solved with a single query using phase kickback to determine if a function is constant or balanced; the Deutsch-Jozsa algorithm extends this to n-bit inputs, efficiently distinguishing constant from balanced functions with one query versus an exponential need classically; the Bernstein-Vazirani algorithm identifies a hidden string with one query, outperforming classical linear requirements; and Simon's algorithm, which finds a hidden period in a two-to-one function with a linear number of queries, showcases an exponential speedup over the best classical probabilistic algorithms.

•Nov 19, 2025•0 citations

Beyond z=0. The Deutsch-Jozsa decided monochromatic languages

Eraldo Pereira Marinho

The present work points out that the Deutsch-Jozsa algorithm was the first formal description of a quantum decider. In particular, it is studied here the class of languages whose indicator functions allow the Deutsch-Jozsa algorithm to output a monochromatic result, beyond the trivial case z = 0 for constant indicator functions. To illustrate examples of randomly balanced languages and some monochromatic cases, it was performed classical computational simulations of the Deutsch-Jozsa quantum algorithm for the specific cases of 4 and 6 qubits, respectively. The general case of the Deutsch-Jozsa decided languages are named balanced languages, and their outcomes from the simulation suggest that such languages are equivalent to the quantum superposition of the monochromatic cases.

arXiv:1812.07844•Dec 19, 2018•1 citation

Deutsch–Jozsa, quantum Fourier transform, and Grover quantum database search algorithms

E. Desurvire

This mathematically intensive chapter takes us through our first steps in the domain of quantum computation (QC) algorithms . The simplest of them is the Deutsch algorithm , which makes it possible to determine whether or not a Boolean function is constant for any input. The key result is that this QC algorithm provides the answer at once, whereas in the classical case it would take two independent calculations. I describe next the generalization of the former algorithm to n qubits, referred to as the Deutsch–Jozsa algorithm . Although they have no specific or useful applications in quantum computing, both algorithms represent a most elegant means of introducing the concept of quantum computation parallelism . I then describe two most important QC algorithms, which nicely exploit quantum parallelism. The first is the quantum Fourier transform (QFT), for which a detailed analysis of QFT circuits and quantum-gate requirements is also provided. As will be shown in the next chapter, a key application of QFT concerns the famous Shor's algorithm , which makes it possible to factor numbers into primes in terms of polynomials. The second algorithm, no less famous than Shor's, is referred to as the Grover quantum database search , whose application is the identification of database items with a quadratic gain in speed. Deutsch algorithm Our exploration of quantum algorithms shall begin with the solution of a very basic problem: finding whether or not a Boolean function f ( x ) is a constant.

Cambridge University Press eBooks•Feb 19, 2009•0 citations

Quantum computation of Fourier transforms over symmetric groups

Robert Beals

Many algorithmic developments in quantum complexity theory, including Shor's celebrated algorithms for factoring and discrete logs, have made use of Fourier transforms over abelian groups.That is, at some point in the computation, the macline is in a superposition of states corresponding to elements of a finite abelian group G, and in quantum polynomial time (i.e., polynomial in log IGI), the machine is transformed according to the Fourier transform to a superposition of states corresponding to the irreducible representations of G.We give a quantum polynomial time algorithm for the Fourier transform for the symmetric groups Sn, adapting results obtained by Clausen and Diaconis-Rockmore to the quantum setting.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1997•140 citations
Abstract Høyer has given a generalisation of the Deutsch–Jozsa algorithm which uses the Fourier transform on a group G which is (in general) non-Abelian. His algorithm distinguishes between functions which are either perfectly balanced (m-to-one) or constant, with certainty, and using a single quantum query. Here, we show that this algorithm (which we call the Deutsch–Jozsa–Høyer algorithm) can in fact deal with a broader range of promises, which we define in terms of the irreducible representations of G.
Hoyer has given a generalisation of the Deutsch--Jozsa algorithm which uses the Fourier transform on a group G which is (in general) non-Abelian. His algorithm distinguishes between functions which are either perfectly balanced (m-to-one) or constant, with certainty, and using a single quantum query. Here, we show that this algorithm (which we call the Deutsch--Jozsa--Hoyer algorithm) can in fact deal with a broader range of promises, which we define in terms of the irreducible representations of G.
This presentation gives a comprehensive overview of quantum query algorithms, beginning with an introduction to the query model of computation where input is accessed via an oracle function. It then details several foundational quantum algorithms that demonstrate a quantum advantage over classical approaches: Deutsch's problem is solved with a single query using phase kickback to determine if a function is constant or balanced; the Deutsch-Jozsa algorithm extends this to n-bit inputs, efficiently distinguishing constant from balanced functions with one query versus an exponential need classically; the Bernstein-Vazirani algorithm identifies a hidden string with one query, outperforming classical linear requirements; and Simon's algorithm, which finds a hidden period in a two-to-one function with a linear number of queries, showcases an exponential speedup over the best classical probabilistic algorithms.
The present work points out that the Deutsch-Jozsa algorithm was the first formal description of a quantum decider. In particular, it is studied here the class of languages whose indicator functions allow the Deutsch-Jozsa algorithm to output a monochromatic result, beyond the trivial case z = 0 for constant indicator functions. To illustrate examples of randomly balanced languages and some monochromatic cases, it was performed classical computational simulations of the Deutsch-Jozsa quantum algorithm for the specific cases of 4 and 6 qubits, respectively. The general case of the Deutsch-Jozsa decided languages are named balanced languages, and their outcomes from the simulation suggest that such languages are equivalent to the quantum superposition of the monochromatic cases.
This mathematically intensive chapter takes us through our first steps in the domain of quantum computation (QC) algorithms . The simplest of them is the Deutsch algorithm , which makes it possible to determine whether or not a Boolean function is constant for any input. The key result is that this QC algorithm provides the answer at once, whereas in the classical case it would take two independent calculations. I describe next the generalization of the former algorithm to n qubits, referred to as the Deutsch–Jozsa algorithm . Although they have no specific or useful applications in quantum computing, both algorithms represent a most elegant means of introducing the concept of quantum computation parallelism . I then describe two most important QC algorithms, which nicely exploit quantum parallelism. The first is the quantum Fourier transform (QFT), for which a detailed analysis of QFT circuits and quantum-gate requirements is also provided. As will be shown in the next chapter, a key application of QFT concerns the famous Shor's algorithm , which makes it possible to factor numbers into primes in terms of polynomials. The second algorithm, no less famous than Shor's, is referred to as the Grover quantum database search , whose application is the identification of database items with a quadratic gain in speed. Deutsch algorithm Our exploration of quantum algorithms shall begin with the solution of a very basic problem: finding whether or not a Boolean function f ( x ) is a constant.
Many algorithmic developments in quantum complexity theory, including Shor's celebrated algorithms for factoring and discrete logs, have made use of Fourier transforms over abelian groups.That is, at some point in the computation, the macline is in a superposition of states corresponding to elements of a finite abelian group G, and in quantum polynomial time (i.e., polynomial in log IGI), the machine is transformed according to the Fourier transform to a superposition of states corresponding to the irreducible representations of G.We give a quantum polynomial time algorithm for the Fourier transform for the symmetric groups Sn, adapting results obtained by Clausen and Diaconis-Rockmore to the quantum setting.