An extension of the Deutsch-Jozsa algorithm to arbitrary qudits

Abstract

Recent advances in quantum computational science promise substantial improvements in the speed with which certain classes of problems can be computed. Various algorithms that utilize the distinctively non-classical characteristics of quantum mechanics have been formulated to take advantage of this promising new approach to computation. One such algorithm was formulated by David Deutsch and Richard Jozsa. By measuring the output of a quantum network that implements this algorithm, it is possible to determine with N – 1 measurements certain global properties of a function f(x), where N is the number of network inputs. Classically, it may not be possible to determine these same properties without evaluating f(x) a number of times that rises exponentially as N increases. Hitherto, the potential power of this algorithm has been explored in the context of qubits, the quantum computational analogue of classical bits. However, just as one can conceive of classical computation in the context of non-binary logic, such as ternary or quaternary logic, so also can one conceive of corresponding higher-order quantum computational equivalents.This thesis investigates the behaviour of the Deutsch-Jozsa algorithm in the context of these higher-order quantum computational forms of logic and explores potential applications for this algorithm. An important conclusion reached is that, not only can the Deutsch-Jozsa algorithm’s known computational advantages be formulated in more general terms, but also a new algorithmic property is revealed with potential practical applications.