
etd AT Indian Institute of Science >
Division of Physical and Mathematical Sciences >
Physics (physics) >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/2005/492

Title:  Quantum Algorithms Using Nuclear Magnetic Resonance Quantum Information Processor 
Authors:  Mitra, Avik 
Advisors:  Kumar, Anil 
Keywords:  Nuclear Magnetic Resonance (NMR) Quantum Information Processor Adiabatic Algorithms Quantum Games Quantum Search Algorithm Quantum Computation Quantum Information Processing 
Submitted Date:  Oct2007 
Series/Report no.:  G21689 
Abstract:  The present work, brieﬂy 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 conﬂict between two or more players who take decisions that inﬂuence their welfare. Classical game theory has been applied to various ﬁelds 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 payoﬀ if they share quantum correlations. However, the payoﬀ 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 ﬁnd 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 conﬂicting 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 DeutschJozsa 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 DeutschJozsa and the (ii) Grover’s search algorithm using local adiabatic evolution has been presented. In adiabatic algorithm, the system is ﬁrst 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 ﬁnal Hamiltonian. The system is evolved under a linear combination of the beginning and the ﬁnal Hamiltonian. During each step of the evolution the interpolating Hamiltonian slowly changes from the beginning to the ﬁnal Hamiltonian, thus evolving the ground state of the beginning Hamiltonian towards the ground state of the ﬁnal Hamiltonian. At the end of the evolution the system is in the ground state of the ﬁnal Hamiltonian which is the solution. The ﬁnal Hamiltonian, for each of the two cases of adiabatic algorithm described in this chapter, are constructed depending on the problem deﬁnition.
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 ﬁnal 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 ‘phasematching’ conditions are imposed on the algorithm. To overcome this problem, a modiﬁed 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 modiﬁed operator converges to the target state while the original Grover’s algorithm fails. Chapter 5, presents the experimental NMR implementation of the modiﬁed 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 WalshHadamard and phaseﬂip 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 knowhow. This thesis endeavors in this direction and probes the experimental feasibility of the quantum algorithms in an NMR quantum information processor. 
URI:  http://etd.iisc.ernet.in/handle/2005/492 
Appears in Collections:  Physics (physics)

Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.
