The present work, briefly described below, consists of implementation of several quantum algorithms in an NMR Quantum Information Processor. Game theory gives us mathematical tools to analyze situations of conflict between two or more players who take decisions that influence their welfare. Classical game theory has been applied to various fields such as market strategy, communication theory, biological processes, foreign policies. It is interesting to study the behaviour of the games when the players share certain quantum correlations such as entanglement. Various games have been studied under the quantum regime with the hope of obtaining some insight into designing new quantum algorithms. Chapter 2 presents the NMR implementation of three such algorithms. Experimental NMR implementation given in this chapter are: (i) Three qubit ‘Dilemma’ game with corrupt sources’. The Dilemma game deals with the situation where three players have to choose between going/not going to a bar with a seating capacity of two. It is seen that in the players have a higher payoff if they share quantum correlations. However, the pay-off falls rapidly with increasing corruption in the source qubits. Here we report the experimental NMR implementation of the quantum version of the Dilemma game with and without corruption in the source qubits. (ii) Two qubit ‘Ulam’s game’. This is a two player game where one player has to find out the binary number thought by the other player. This problem can be solved with one query if quantum resources are used. This game has been implemented in a two qubit system in an NMR quantum information processor. (iii) Two qubit ‘Battle of Sexes’ game. This game deal with a situation where two players have conflicting choices but a deep desire to be together. This leads to a dilemma in the classical case. Quantum mechanically this dilemma is resolved and a unique solution emerges. The NMR implementation of the quantum version of this game is also given in this chapter. Quantum adiabatic algorithm is a method of solving computational problems by evolving the ground state of a slowly varying Hamiltonian. The technique uses evolution of the ground state of a slowly varying Hamiltonian to reach the required output state. In some cases, such as the adiabatic versions of Grover’s search algorithm and Deutsch-Jozsa algorithm, applying the global adiabatic evolution yields a complexity similar to their classical algorithms. However, if one uses local adiabatic evolutions, their complexity is of the order √N (where N=2n) [37, 38]. In Chapter 3, the NMR implementation of (i) the Deutsch-Jozsa and the (ii) Grover’s search algorithm using local adiabatic evolution has been presented. In adiabatic algorithm, the system is first prepared in the equal superposition of all the possible states which is the ground state of the beginning Hamiltonian. The solution is encoded in the ground state of the final Hamiltonian. The system is evolved under a linear combination of the beginning and the final Hamiltonian. During each step of the evolution the interpolating Hamiltonian slowly changes from the beginning to the final Hamiltonian, thus evolving the ground state of the beginning Hamiltonian towards the ground state of the final Hamiltonian. At the end of the evolution the system is in the ground state of the final Hamiltonian which is the solution. The final Hamiltonian, for each of the two cases of adiabatic algorithm described in this chapter, are constructed depending on the problem definition. Adiabatic algorithms have been proved to be equivalent to standard quantum algorithms with respect to complexity [39]. NMR implementation of adiabatic algorithms in homonuclear spin systems face problems due to decoherence and complicated pulse sequences. The decoherence destroys the answer as it causes the final state to evolve to a mixed state and in homonuclear systems there is a substantial evolution under the internal Hamiltonian during the application of the soft pulses which prevents the initial state to converge to the solution state. The resolution of these issues are necessary before one can proceed for the implementation of an adiabatic algorithm in a large system. Chapter 4 demonstrates that by using ‘strongly modulated pulses’ for creation of interpolating Hamiltonian, one can circumvent both the problems and thus successfully implement the adiabatic SAT algorithm in a homonuclear three qubit system. The ‘strongly modulated pulses’ (SMP) are computer optimized pulses in which the evolution under the internal Hamiltonian of the system and RF inhomogeneities associated with the probe is incorporated while generating the SMPs. This results in precise implementation of unitary operators by these pulses. This work also demonstrates that the strongly modulated pulses tremendously reduce the time taken for the implementation of the algorithm, can overcome problems associated with decoherence and will be the modality in future implementation of quantum information processing by NMR. Quantum search algorithm, involving a large number of qubits, is highly sensitive to errors in the physical implementation of the unitary operators. This can put an upper limit to the size of the data base that can be practically searched. The lack of robustness of the quantum search algorithm for a large number of qubits, arises from the fact that stringent ‘phase-matching’ conditions are imposed on the algorithm. To overcome this problem, a modified operator for the search algorithm has been suggested by Tulsi [40]. He has theoretically shown that even when there are errors in implementation of the unitary operators, the search algorithm with his modified operator converges to the target state while the original Grover’s algorithm fails. Chapter 5, presents the experimental NMR implementation of the modified search algorithm with errors and its comparison with the original Grover’s search algorithm. We experimentally validate the theoretical predictions made by Tulsi that the introduction of compensatory Walsh-Hadamard and phase-flip operations refocuses the errors. Experimental Quantum Information Processing is in a nascent stage and it would be too early to predict its future. The excitement on this topic is still very prevalent and many options are being explored to enhance the hardware and software know-how. This thesis endeavors in this direction and probes the experimental feasibility of the quantum algorithms in an NMR quantum information processor.

Quantum computing has generated a lot of interested in the past two decades. Research into powerful models of quantum computation has yielded important and elegant results like an efficient algorithm for factoring and a quadratic speed-up for unordered search. At the same time, given the current difficulty in the physical implementation of these general purpose models, considerable effort has also been made in estimating the power of weaker models of quantum computation: models that have a small quantum component. The first part of this thesis is an investigation into the power of interference in quantum computing. While interference in probability amplitudes is a central feature even in powerful models, it is the only extra resource available to quantum finite automata. Of particular interest is interference in automata that have both classical and quantum states (2QCFA) as proposed by Ambainis and Watrous, since it inquires into the power of a classical deterministic finite automaton when augmented with a quantum component of constant size. Our contributions in this part are as follows: • To abstract out the phenomenon of interference in quantum computing, we propose a model called the 2-way Optical Interference Automata (2OIA). The model consists of a 2DFA augmented with a simple optical arrangement. We show different ways of harnessing the power of interference in the form of algorithms on this model to recognize some non-trivial languages. We then go on to show a language recognizable by a Turing machine using O(n2) space but by no 2OIA. • A natural classical model for comparison with 2QCFA is the weighted automaton, since it has the potential to capture interference in sum of path weights. Using the Cortes-Mohri definition of language recognition, we give an efficient simulation of 2QCFAwith algebraic amplitudes by weighted automata over the complex semi ring. • We introduce quantum non-determinism to the Measure-Once 1-way Quantum Finite Automata of Moore and Crutchfield and Kondacs and Watrous and show that even then, the model can recognize only regular languages with bounded error. • We propose a group theoretic generalization of counter automata that allows a notion of counter reversal complexity. To obtain this generalization, we combine concepts from classical counter automata theory with results in 2QCFA. We examine specific instances of this generalization and compare their ii iii powers. We also show an instance recognizing a language that is not recognized by conventional 2-way counter automata. Finally, we show a strict hierarchy among the 1-way versions of the instances Discussed. The second part of the thesis deals with Quantum Adiabatic Optimization algorithms. A common trick for designing faster quantum adiabatic algorithms is to apply the adiabatic condition locally at every instant. However it is often difficult to determine the instantaneous gap between the lowest two eigen values, which is an essential ingredient in the adiabatic condition. We present a simple linear algebraic technique for obtaining a lower bound on the instantaneous gap even in such a situation. As an illustration, we investigate the adiabatic unordered search of van Dam et al. and Roland and Cerf when the non-zero entries of the diagonal final Hamiltonian are perturbed by a polynomial (in logN, where N is the length of the unordered list) amount. We use our technique to derive a bound on the running time of a local adiabatic schedule in terms of the minimum gap between the lowest two eigenvalues.