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:2207.02580 · Quantum Information Processing

A generalisation of the Phase Kick-Back

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

Published Mar 13, 2023• 8 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1007/s11128-023-03884-8

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.

arXiv:2405.03850•May 6, 2024•0 citations

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.

International Journal of Modern Physics C•Sep 12, 2025•0 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

Quantum Advantage with Deutsch-Jozsa, Bernstein-Vazirani, and Simon’s Algorithms

Vladimir Silva

In this chapter, we study three algorithms of little practical use but important because they were the first to show that quantum computers can solve problems significantly faster than classical ones. Consider the time complexities O(n) for the algorithms: classical vs. quantum in Table 9-1 (where n is the size of the input).

Apress eBooks•Dec 18, 2023•0 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.

arXiv:1510.04699•New Journal of Physics•Mar 11, 2016•52 citations

Generalization of the Deutsch algorithm using two qudits

Jose Luis Cereceda

Deutsch's algorithm for two qubits (one control qubit plus one auxiliary qubit) is extended to two $d$-dimensional quantum systems or qudits for the case in which $d$ is equal to $2^n$, $n=1,2,...$ . This allows one to classify a certain oracle function by just one query, instead of the $2^{n-1}+1$ queries required by classical means. The given algorithm for two qudits also solves efficiently the Bernstein-Vazirani problem. Entanglement does not occur at any step of the computation.

arXiv:quant-ph/0407253•Jul 29, 2004•7 citations
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→{0,1}mf:\{0,1\}^{n}\rightarrow \{0,1\}^{m}f:{0,1}n→{0,1}m f : { 0 , 1 } n → { 0 , 1 } m functions using the eigenvalues of the oracle function Uf\textbf{U}_fUf​ 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.
In our previous work, we defined a quantum algorithmic technique known as the Generalised Phase Kick-Back, or GPKGPKGPK, 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 y\mathbf{y}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 GPKGPKGPK algorithm, while analysing the efficiency of this new solution.
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.
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 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.
Deutsch's algorithm for two qubits (one control qubit plus one auxiliary qubit) is extended to two ddd-dimensional quantum systems or qudits for the case in which ddd is equal to 2n2^n2n, n=1,2,...n=1,2,...n=1,2,... . This allows one to classify a certain oracle function by just one query, instead of the 2n−1+12^{n-1}+12n−1+1 queries required by classical means. The given algorithm for two qudits also solves efficiently the Bernstein-Vazirani problem. Entanglement does not occur at any step of the computation.