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:1912.01549 · Journal of Physics Conference Series

On the Connection Between Deutsch-Jozsa Algorithm and Bent Functions

Eraldo Pereira Marinho

Published Jan 1, 2021• 0 citations
arXivHTMLPDF

Abstract

Abstract It is presently shown that the Deutsch-Jozsa algorithm is connected to the concept of bent function. Particularly, it is noticeable that the quantum circuit used to denote the well-known quantum algorithm is by itself the quantum computer that performs the Walsh transform of a Boolean function. Consequently, the output from the Deutsch-Jozsa algorithm when the hidden function is bent corresponds to a flat spectrum of quantum states.

DOI
10.1088/1742-6596/1730/1/012111

Related papers

Deutsch-Jozsa Algorithm Revisited in the Domain of Cryptographically Significant Boolean Functions

Subhamoy Maitra, Partha Mukhopadhyay

Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let $f$ be an $n$-variable Boolean function and its Walsh spectra is denoted by $W_f(ω)$ at the point $ω\in \{0, 1\}^n$. The Boolean function is available in the form of an oracle. We like to find an $ω$ such that $W_f(ω) \neq 0$ as this will provide one of the linear functions which are correlated to $f$. We show that the quantum algorithm proposed by Deutsch and Jozsa (1992) solves the above mentioned problem in constant time. However, the best known classical algorithm to solve this problem requires exponential time in $n$. We also analyse certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch-Jozsa algorithm performs on them.

arXiv:quant-ph/0410042•Oct 6, 2004•4 citations

THE DEUTSCH–JOZSA ALGORITHM REVISITED IN THE DOMAIN OF CRYPTOGRAPHICALLY SIGNIFICANT BOOLEAN FUNCTIONS

Subhamoy Maitra, PARTHA MUKHOPADHYAY

Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems, one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let f be an n-variable Boolean function and its Walsh spectra is denoted by Wf(ω) at the point ω ∈ {0, 1}n. The Boolean function is available in the form of an oracle. We like to find a ω such that Wf(ω) ≠ 0 as this will provide one of the linear functions which are correlated to f. We show that the quantum algorithm proposed by Deutsch and Jozsa7 solves this problem in constant time. However, the best known classical algorithm to solve the problem requires exponential time in n. We also analyze certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch–Jozsa algorithm performs on them.

International Journal of Quantum Information•May 31, 2005•13 citations

Walsh transforms and efficient quantum algorithms

Takashi Mihara

In this paper, we show structures of efficient quantum algorithms on a quantum Turing machine. First, we denote a relationship between Simon's algorithm and Walsh transforms. Next, we also show that a quantum Turing machine can efficiently solve the Deutsch–Jozsa problem by using interference among configurations instead of observation. Moreover, based on these results, we are led to structures of more general quantum algorithms. Finally, we show a problem that can be efficiently solved by using this type of algorithm and a Walsh transform. © 2000 Scripta Technica, Electron Comm Jpn Pt 3, 83(8): 71–80, 2000

Electronics and Communications in Japan (Part III Fundamental Electronic Science)•Aug 1, 2000•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

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 Computing Concepts with Deutsch Jozsa Algorithm

Poornima Aradyamath, N. M. Naghabhushana, Rohitha Ujjinimatad

In this paper, we briefly review the basic concepts of quantum computation, entanglement, quantum cryptography and quantum fourier transform. Quantum algorithms like Deutsch Jozsa, Shor’s factorization and Grover’s data search are developed using fourier transform and quantum computation concepts to build quantum computers. Researchers are finding a way to build quantum computer that works more efficiently than classical computer. Among the standard well known algorithms in the field of quantum computation and communication we describe mathematically Deutsch Jozsa algorithm in detail for 2 and 3 qubits. Calculation of balanced and unbalanced states is shown in the mathematical description of the algorithm.

JOIV International Journal on Informatics Visualization•Jan 10, 2019•6 citations
Abstract It is presently shown that the Deutsch-Jozsa algorithm is connected to the concept of bent function. Particularly, it is noticeable that the quantum circuit used to denote the well-known quantum algorithm is by itself the quantum computer that performs the Walsh transform of a Boolean function. Consequently, the output from the Deutsch-Jozsa algorithm when the hidden function is bent corresponds to a flat spectrum of quantum states.
Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let fff be an nnn-variable Boolean function and its Walsh spectra is denoted by Wf(ω)W_f(ω)Wf​(ω) at the point ω∈{0,1}nω\in \{0, 1\}^nω∈{0,1}n. The Boolean function is available in the form of an oracle. We like to find an ωωω such that Wf(ω)≠0W_f(ω) \neq 0Wf​(ω)=0 as this will provide one of the linear functions which are correlated to fff. We show that the quantum algorithm proposed by Deutsch and Jozsa (1992) solves the above mentioned problem in constant time. However, the best known classical algorithm to solve this problem requires exponential time in nnn. We also analyse certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch-Jozsa algorithm performs on them.
Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems, one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let f be an n-variable Boolean function and its Walsh spectra is denoted by Wf(ω) at the point ω ∈ {0, 1}n. The Boolean function is available in the form of an oracle. We like to find a ω such that Wf(ω) ≠ 0 as this will provide one of the linear functions which are correlated to f. We show that the quantum algorithm proposed by Deutsch and Jozsa7 solves this problem in constant time. However, the best known classical algorithm to solve the problem requires exponential time in n. We also analyze certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch–Jozsa algorithm performs on them.
In this paper, we show structures of efficient quantum algorithms on a quantum Turing machine. First, we denote a relationship between Simon's algorithm and Walsh transforms. Next, we also show that a quantum Turing machine can efficiently solve the Deutsch–Jozsa problem by using interference among configurations instead of observation. Moreover, based on these results, we are led to structures of more general quantum algorithms. Finally, we show a problem that can be efficiently solved by using this type of algorithm and a Walsh transform. © 2000 Scripta Technica, Electron Comm Jpn Pt 3, 83(8): 71–80, 2000
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.
In this paper, we briefly review the basic concepts of quantum computation, entanglement, quantum cryptography and quantum fourier transform. Quantum algorithms like Deutsch Jozsa, Shor’s factorization and Grover’s data search are developed using fourier transform and quantum computation concepts to build quantum computers. Researchers are finding a way to build quantum computer that works more efficiently than classical computer. Among the standard well known algorithms in the field of quantum computation and communication we describe mathematically Deutsch Jozsa algorithm in detail for 2 and 3 qubits. Calculation of balanced and unbalanced states is shown in the mathematical description of the algorithm.