A quantum algorithm to solve the parity problem is better than its most efficient classical counter- part with a separation that is polynomial in the number of queries. This was shown by E. Bernstein and U. Vazirani and was one of the earliest indications that the quantum information processing can outperform the classical one by a significant margin. The problem and its solution both is usually stated for a 2-level system since we generally work with bits/qubits. However, many works have been done generalizing known quantum computing techniques to higher level systems. Following this, we look at a generalization of the Bernstein-Vazirani algorithm implemented on a general qudit system.
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 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
DJn0(x)=1 for
∣x∣=n/2,DJn0(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
DJn0 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
DJnk(x)=1 for
∣x∣=n/2,DJnk(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
DJnk. 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.
Abstract: Over the last decade has been a lot of interest in new types of computable machines, due partly over the fears on conventional, classical, computing. Research by leading physicists, mathematicians and computer scientists has shown quantum computers could be the future, as they may be able to solve some computationally difficult problems much faster than is currently possible on a classical computer. David Deutsch has already created a working model for a quantum computer, the quantum Turing machine or QTM Deutsch [1985]. This has been proved as a model for computation on a quantum and has allowed algorithms to be developed. Deutsch-Josza’s algorithm, as all known quantum algorithms that provide exponential speedup over classical systems do, answers a question about a global property of a solution space. This paper describes the generalization of the Deutsch-Josza algorithm to n d-dimensional quantum systems or qudits. Key–Words: quantum computing, quantum dits, quantum algorithm 1