International Journal of Modern Physics C

Further applications of the generalized phase kick-back

Joaquín Ossorio-Castillo, Ulises Pastor–Díaz, José M. Tornero

Published Sep 12, 2025• 0 citations

Abstract

In our previous work, we defined a quantum algorithmic technique known as the Generalized Phase Kick-Back, or GPK, and analyzed its applications to the Deutsch–Jozsa, the Bernstein–Vazirani and the Simon p roblem. In this paper we continue analyzing the potential of this technique, defining the concept of [Formula: see text]-balanced functions and solving a new problem, which further generalizes the generalized Deutsch–Jozsa problem (the fully balanced image problem). This problem also underlines the relation between quantum computation and Boolean function theory.

DOI: 10.1142/s0129183125430053

Related papers

Further Applications of the Generalised Phase Kick-Back

Ossorio-Castillo, Joaquín, Ulises Pastor–Díaz, José M. Tornero

arXiv:2405.03850May 6, 20240 citations

A generalisation of the Phase Kick-Back

Joaquín Ossorio-Castillo, Ulises Pastor–Díaz, José M. Tornero

arXiv:2207.02580Quantum Information ProcessingMar 13, 20238 citations

Quantum Query Algorithms

Walid E. Gomaa

Nov 19, 20250 citations

Phase-creation algorithm to solve an extended Deutsch problem by a quantum computer

Hiroshi Ozawa

Physical Review AApr 18, 20010 citations

Phase-creation algorithm to solve and extended Deutsch problem with an implementation on an NMR quantum computer (Analytical Study of Quantum Information and Related Fields)

Hiroshi Ozawa

数理解析研究所講究録May 1, 20020 citations

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

Subhamoy Maitra, Partha Mukhopadhyay

arXiv:quant-ph/0410042Oct 6, 20044 citations

International Journal of Modern Physics C

Further applications of the generalized phase kick-back

Joaquín Ossorio-Castillo, Ulises Pastor–Díaz, José M. Tornero

Published Sep 12, 2025• 0 citations

Publisher

Abstract

DOI: 10.1142/s0129183125430053

Related papers

Further Applications of the Generalised Phase Kick-Back

Ossorio-Castillo, Joaquín, Ulises Pastor–Díaz, José M. Tornero

In our previous work, we defined a quantum algorithmic technique known as the Generalised Phase Kick-Back, or $GPK$ , and analysed its applications in generalising some classical quantum problems, such as the Deutsch-Jozsa problem or the Bernstein-Vazirani problem. We also proved that using this technique we can solve Simon's problem in a more efficient manner. In this paper we continue analysing the potential of this technique, defining the concept of $\mathbf{y}$ -balanced functions and solving a new problem, which further generalises the generalised Deutsch-Jozsa problem (the fully balanced image problem). This problem also underlines the relation between quantum computation and Boolean function theory, and, in particular, the Walsh and Fourier-Hadamard transforms. We finish our discussion by solving the generalised version of Simon's problem using the $GPK$ algorithm, while analysing the efficiency of this new solution.In our previous work, we defined a quantum algorithmic technique known as the Generalised Phase Kick-Back, or $GPK$, and analysed its applications in generalising some classical quantum problems, such as the Deutsch-Jozsa problem or the Bernstein-Vazirani problem. We also proved that using this technique we can solve Simon's problem in a more efficient manner. In this paper we continue analysing the potential of this technique, defining the concept of $\mathbf{y}$-balanced functions and solving a new problem, which further generalises the generalised Deutsch-Jozsa problem (the fully balanced image problem). This problem also underlines the relation between quantum computation and Boolean function theory, and, in particular, the Walsh and Fourier-Hadamard transforms. We finish our discussion by solving the generalised version of Simon's problem using the $GPK$ algorithm, while analysing the efficiency of this new solution.

arXiv:2405.03850May 6, 20240 citations

A generalisation of the Phase Kick-Back

Joaquín Ossorio-Castillo, Ulises Pastor–Díaz, José M. Tornero

Abstract In this paper, we present a generalisation of the Phase Kick-Back technique, which is central to some of the classical algorithms in quantum computing. We will begin by recalling the Phase Kick-Back technique to then introduce the new generalised version for $f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}$ f : { 0 , 1 } n → { 0 , 1 } m functions using the eigenvalues of the oracle function $\textbf{U}_f$ U f . After that, we will present a new generalised version of the Deutsch–Jozsa problem and how it can be solved using the previously defined technique. We will also deal with a generalised version of the Bernstein–Vazirani problem and solve it using the generalised Phase Kick-Back. Finally, we show how we can use this technique to obtain an algorithm for Simon’s problem that improves the classical one.Abstract In this paper, we present a generalisation of the Phase Kick-Back technique, which is central to some of the classical algorithms in quantum computing. We will begin by recalling the Phase Kick-Back technique to then introduce the new generalised version for $$f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}$$ f : { 0 , 1 } n → { 0 , 1 } m functions using the eigenvalues of the oracle function $$\textbf{U}_f$$ U f . After that, we will present a new generalised version of the Deutsch–Jozsa problem and how it can be solved using the previously defined technique. We will also deal with a generalised version of the Bernstein–Vazirani problem and solve it using the generalised Phase Kick-Back. Finally, we show how we can use this technique to obtain an algorithm for Simon’s problem that improves the classical one.

arXiv:2207.02580Quantum Information ProcessingMar 13, 20238 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.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, 20250 citations

Phase-creation algorithm to solve an extended Deutsch problem by a quantum computer

Hiroshi Ozawa

The Deutsch-Jozsa algorithm to implement an f-controlled-NOT transformation on a quantum computer was generalized to create arbitrary phases. This phase-creation algorithm was applied to solve an extended Deutsch problem for a function that maps ${0,1{}}^{n}$ to ${0,1{}}^{m}.$ Implementation of the algorithm on a NMR quantum computer is discussed.The Deutsch-Jozsa algorithm to implement an f-controlled-NOT transformation on a quantum computer was generalized to create arbitrary phases. This phase-creation algorithm was applied to solve an extended Deutsch problem for a function that maps ${0,1{}}^{n}$ to ${0,1{}}^{m}.$ Implementation of the algorithm on a NMR quantum computer is discussed.

Physical Review AApr 18, 20010 citations

Phase-creation algorithm to solve and extended Deutsch problem with an implementation on an NMR quantum computer (Analytical Study of Quantum Information and Related Fields)

Hiroshi Ozawa

The Deutsch-Jozsa algorithm to implement an $f$ -controUed-NOT transformation on a quantum computer was generalized to create arbitrary phases.This phase-creation algorithm was applied to solve an extended Deutsch problem for afunction that maps $\{0, 1\}^{n}$ to $\{0, 1\}^{m}$ .Implementation of the algorithm on an NMR quantum computer is discussed.The Deutsch-Jozsa algorithm to implement an $f$ -controUed-NOT transformation on a quantum computer was generalized to create arbitrary phases.This phase-creation algorithm was applied to solve an extended Deutsch problem for afunction that maps $\{0, 1\}^{n}$ to $\{0, 1\}^{m}$ .Implementation of the algorithm on an NMR quantum computer is discussed.

数理解析研究所講究録May 1, 20020 citations

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.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/0410042Oct 6, 20044 citations

In our previous work, we defined a quantum algorithmic technique known as the Generalised Phase Kick-Back, or

GPK

, and analysed its applications in generalising some classical quantum problems, such as the Deutsch-Jozsa problem or the Bernstein-Vazirani problem. We also proved that using this technique we can solve Simon's problem in a more efficient manner. In this paper we continue analysing the potential of this technique, defining the concept of

\mathbf{y}

-balanced functions and solving a new problem, which further generalises the generalised Deutsch-Jozsa problem (the fully balanced image problem). This problem also underlines the relation between quantum computation and Boolean function theory, and, in particular, the Walsh and Fourier-Hadamard transforms. We finish our discussion by solving the generalised version of Simon's problem using the

GPK

algorithm, while analysing the efficiency of this new solution.

f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}

f : { 0 , 1 } n → { 0 , 1 } m functions using the eigenvalues of the oracle function

\textbf{U}_f

U f . After that, we will present a new generalised version of the Deutsch–Jozsa problem and how it can be solved using the previously defined technique. We will also deal with a generalised version of the Bernstein–Vazirani problem and solve it using the generalised Phase Kick-Back. Finally, we show how we can use this technique to obtain an algorithm for Simon’s problem that improves the classical one.

{0,1{}}^{n}

{0,1{}}^{m}.

Implementation of the algorithm on a NMR quantum computer is discussed.

The Deutsch-Jozsa algorithm to implement an

f

-controUed-NOT transformation on a quantum computer was generalized to create arbitrary phases.This phase-creation algorithm was applied to solve an extended Deutsch problem for afunction that maps

\{0, 1\}^{n}

\{0, 1\}^{m}

.Implementation of the algorithm on an NMR quantum computer is discussed.

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.