Generalized Approaches for Quantum Algorithms using Random Walk

MS Thesis

Abstract

Random walks constitute a prominent tool employed in computational mathematics to address various problems, predominantly related to the exploration of extensive combinatorial structures. The Quantum Walk algorithm offers a twofold acceleration in computations compared to its classical equivalent by leveraging the potential of superposition. Comparators play a pivotal role in the quantum random walk algorithm. Quantum Bit String Comparators (QBSCs), essential in quantum computing, assess n-qubit sequences to ascertain relationships such as equality or magnitude, analogous to conditional statements in programming. Their adaptability in quantum algorithms marks their significance. Creating efficient comparators for varying n-qubit lengths remains challenging due to resource demands and resulting delays. Current designs cater to fixed-length input, limiting their use to different qubit lengths. This hurdle hampers broader quantum algorithm applications. Overcoming this challenge by creating adaptable QBSCs for variable qubit lengths is pivotal to unlocking quantum computing's potential for solving diverse computational problems. In quantum computing, utilizing superposition allows for string similarity comparisons at higher levels. This method is useful when aiming to assess the similarity or dissimilarity between two strings. The similarity comparator, leveraging superposition, requires only logarithmic ($\log(n)$) qubits. This means that the string similarity comparator can deliver results using just $\log(n)$ qubits, providing information about the extent of similarity and dissimilarity between the given strings. In this paper, we present novel concepts involving a generalized bit string comparator and a generalized discrete quantum random walk. The comparator is specifically designed for application within a character movement game utilizing quantum random walks. The character's motion within the game significantly relies on the outcomes derived from a random walk. Moreover, the character's movement is contingent on both the target state and the output state of the random walk. Our designs are meticulously crafted to guide the state of a character to its intended destination. This is achieved by comparing two logic states represented by $n$-qubit configurations. These states correspond to the current position of the character and the result obtained from a quantum random walk. When the quantity of qubits escalates within a quantum walk, the ratio of decoherence exhibits a corresponding increment. This phenomenon is indicative of the proportional amplification of decoherence with an augmented number of qubits. Existing efficient comparators are tailored to fixed-length inputs, limiting their applicability at higher levels. This paper introduces a novel design for comparing two n-qubit logic states using only two ancillary bits. The proposed design is thoroughly evaluated for qubit requirements, ancillary bit usage, quantum cost, quantum delay, gate operations, and circuit complexity across various input lengths. By leveraging the outcomes derived from a quantum random walk, our engineered algorithms enable the assessment and comparison of these two states. Through this comparison process within the quantum realm, our designs facilitate the determination of the most optimal path to navigate the character to its destination.