arXiv:2405.03850

Further Applications of the Generalised Phase Kick-Back

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

Published May 6, 2024• 0 citations

Abstract

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.

DOI: 10.48550/arxiv.2405.03850

Related papers

Further applications of the generalized phase kick-back

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

International Journal of Modern Physics CSep 12, 20250 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

Generalised phase kick-back: the structure of computational algorithms from physical principles

Ciarán M. Lee, John H. Selby

arXiv:1510.04699New Journal of PhysicsMar 11, 201652 citations

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

Subhamoy Maitra, Partha Mukhopadhyay

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

Generalized Deutsch-Jozsa problem and the optimal quantum algorithm

Daowen Qiu, Shenggen Zheng

Physical Review AJun 20, 201831 citations

arXiv:2405.03850

Further Applications of the Generalised Phase Kick-Back

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

Published May 6, 2024• 0 citations

arXiv HTML PDF

Abstract

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.

DOI: 10.48550/arxiv.2405.03850

Related papers

Further applications of the generalized phase kick-back

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

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

International Journal of Modern Physics CSep 12, 20250 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

Generalised phase kick-back: the structure of computational algorithms from physical principles

Ciarán M. Lee, John H. Selby

The advent of quantum computing has challenged classical conceptions of which problems are efficiently solvable in our physical world. This motivates the general study of how physical principles bound computational power. In this paper we show that some of the essential machinery of quantum computation—namely reversible controlled transformations and the phase kick-back mechanism—exist in any operational-defined theory with a consistent notion of information. These results provide the tools for an exploration of the physics underpinning the structure of computational algorithms. We investigate the relationship between interference behaviour and computational power, demonstrating that non-trivial interference behaviour is a general resource for post-classical computation. In proving the above, we connect higher-order interference to the existence of post-quantum particle types, potentially providing a novel experimental test for higher-order interference. Finally, we conjecture that theories with post-quantum interference—the higher-order interference of Sorkin—can solve problems intractable even on a quantum computer.The advent of quantum computing has challenged classical conceptions of which problems are efficiently solvable in our physical world. This motivates the general study of how physical principles bound computational power. In this paper we show that some of the essential machinery of quantum computation—namely reversible controlled transformations and the phase kick-back mechanism—exist in any operational-defined theory with a consistent notion of information. These results provide the tools for an exploration of the physics underpinning the structure of computational algorithms. We investigate the relationship between interference behaviour and computational power, demonstrating that non-trivial interference behaviour is a general resource for post-classical computation. In proving the above, we connect higher-order interference to the existence of post-quantum particle types, potentially providing a novel experimental test for higher-order interference. Finally, we conjecture that theories with post-quantum interference—the higher-order interference of Sorkin—can solve problems intractable even on a quantum computer.

arXiv:1510.04699New Journal of PhysicsMar 11, 201652 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

Generalized Deutsch-Jozsa problem and the optimal quantum algorithm

Daowen Qiu, Shenggen Zheng

The Deutsch-Jozsa algorithm is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. It was proposed by Deutsch and Jozsa in 1992 with improvements by Cleve, Ekert, Macchiavello, and Mosca in 1998. The Deutsch-Jozsa problem is a promise problem and we can equivalently describe it as a partial function ${\text{DJ}}_{n}^{0}:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ defined as ${\text{DJ}}_{n}^{0}(x)=1$ for $|x|=n/2, {\text{DJ}}_{n}^{0}(x)=0$ for $|x|=0,n$ , and it is undefined for the rest of the cases, where $n$ is even, and $|x|$ is the Hamming weight of $x$ . The optimal quantum algorithm needs only one query to compute ${\text{DJ}}_{n}^{0}$ but the classical deterministic algorithm requires ${2}^{n\ensuremath{-}1}+1$ queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as ${\text{DJ}}_{n}^{k}(x)=1$ for $|x|=n/2, {\text{DJ}}_{n}^{k}(x)=0$ for $|x|$ in the set ${0,1,...,k,n\ensuremath{-}k,n\ensuremath{-}k+1,...,n}$, and it is undefined for the rest of the cases, where $0\ensuremath{\le}k<n/2$. In particular, we give and prove an optimal exact quantum query algorithm with complexity $k+1$ for computing the generalized Deutsch-Jozsa problem ${\text{DJ}}_{n}^{k}$ . It is clear that the case of $k=0$ is in accordance with the Deutsch-Jozsa problem. Also, we give a method for finding the approximate and exact degrees of symmetric partial Boolean functions.The Deutsch-Jozsa algorithm is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. It was proposed by Deutsch and Jozsa in 1992 with improvements by Cleve, Ekert, Macchiavello, and Mosca in 1998. The Deutsch-Jozsa problem is a promise problem and we can equivalently describe it as a partial function ${\text{DJ}}_{n}^{0}:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ defined as ${\text{DJ}}_{n}^{0}(x)=1$ for $|x|=n/2, {\text{DJ}}_{n}^{0}(x)=0$ for $|x|=0,n$, and it is undefined for the rest of the cases, where $n$ is even, and $|x|$ is the Hamming weight of $x$. The optimal quantum algorithm needs only one query to compute ${\text{DJ}}_{n}^{0}$ but the classical deterministic algorithm requires ${2}^{n\ensuremath{-}1}+1$ queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as ${\text{DJ}}_{n}^{k}(x)=1$ for $|x|=n/2, {\text{DJ}}_{n}^{k}(x)=0$ for $|x|$ in the set ${0,1,...,k,n\ensuremath{-}k,n\ensuremath{-}k+1,...,n}$, and it is undefined for the rest of the cases, where $0\ensuremath{\le}k<n/2$. In particular, we give and prove an optimal exact quantum query algorithm with complexity $k+1$ for computing the generalized Deutsch-Jozsa problem ${\text{DJ}}_{n}^{k}$. It is clear that the case of $k=0$ is in accordance with the Deutsch-Jozsa problem. Also, we give a method for finding the approximate and exact degrees of symmetric partial Boolean functions.

Physical Review AJun 20, 201831 citations

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

GPK

\mathbf{y}

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.

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.

{\text{DJ}}_{n}^{0}(x)=1

for

|x|=n/2, {\text{DJ}}_{n}^{0}(x)=0

for

|x|=0,n

, and it is undefined for the rest of the cases, where

n

is even, and

|x|

is the Hamming weight of

x

. The optimal quantum algorithm needs only one query to compute

{\text{DJ}}_{n}^{0}

but the classical deterministic algorithm requires ${2}^{n\ensuremath{-}1}+1$ queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as

{\text{DJ}}_{n}^{k}(x)=1

for

|x|=n/2, {\text{DJ}}_{n}^{k}(x)=0

for

|x|

in the set ${0,1,...,k,n\ensuremath{-}k,n\ensuremath{-}k+1,...,n}$, and it is undefined for the rest of the cases, where $0\ensuremath{\le}k<n/2$. In particular, we give and prove an optimal exact quantum query algorithm with complexity

k+1

for computing the generalized Deutsch-Jozsa problem

{\text{DJ}}_{n}^{k}

. It is clear that the case of

k=0

is in accordance with the Deutsch-Jozsa problem. Also, we give a method for finding the approximate and exact degrees of symmetric partial Boolean functions.