Quantum computation has attracted a great deal of attention from the scientific community in recent years. By using the quantum mechanical phenomena of superposition and entanglement, a quantum computer can solve certain problems much faster than classical computers. Several quantum algorithms have been developed to demonstrate this quantum speedup. Two important examples are Shor’s algorithm for the factorization problem, and Grover’s algorithm for the search problem. Significant efforts are on to build a large scale quantum computer for implementing these quantum algorithms. This thesis deals with Grover’s search algorithm, and presents its several generalizations that perform better in specific contexts. While writing the thesis, we have assumed the familiarity of readers with the basics of quantum mechanics and computer science. For a general introduction to the subject of quantum computation, see [1]. In Chapter 1, we formally define the search problem as well as present Grover’s search algorithm [2]. This algorithm, or more generally the quantum amplitude amplification algorithm [3, 4], drives a quantum system from a prepared initial state (s) to a desired target state (t). It uses O(α-1 = | (t−|s)| -1) iterations of the operator g = IsIt on |s), where { IsIt} are selective phase inversions selective phase inversions of the corresponding states. That is a quadratic speedup over the simple scheme of O(α−2) preparations of |s) and subsequent projective measurements. Several generalizations of Grover’s algorithm exist. In Chapter 2, we study further generalizations of Grover’s algorithm. We analyse the iteration of the search operator S = DsI t on |s) where Ds is a more general transformation than Is, and I t is a selective phase rotation of |t) by angle . We find sufficient conditions for S to produce a successful quantum search algorithm. In Chapter 3, we demonstrate that our general framework encapsulates several previous generalizations of Grover’s algorithm. For example, the phase-matching condition for the search operator requires the angles and and to be almost equal for a successful quantum search. In Kato’s algorithm, the search operator is where Ks consists of only single-qubit gates, which are easier to implement physically than multi-qubit gates. The spatial search algorithms consider the search operator where is a spatially local operator and provides implementation advantages over Is. The analysis of Chapter 2 provides a simpler understanding of all these special cases. In Chapter 4, we present schemes to improve our general quantum search algorithm, by controlling the operators through an ancilla qubit. For the case of two dimensional spatial search problem, these schemes yield an algorithm with time complexity . Earlier algorithms solved this problem in time steps, and it was an open question to design a faster algorithm. The schemes can also be used to find, for a given unitary operator, an eigenstate corresponding to a specified eigenvalue. In Chapter 5, we extend the analysis of Chapter 2 to general adiabatic quantum search. It starts with the ground state |s) of an initial Hamiltonian Hs and evolves adiabatically to the target state |t) that is the ground state of the final Hamiltonian The evolution uses a time dependent Hamiltonian HT that varies linearly with time . We show that the minimum excitation gap of HT is proportional to α. Also, the ground state of HT changes significantly only within a very narrow interval of width around the transition point, where the excitation gap has its minimum. This feature can be used to reach the target state (t) using adiabatic evolution for time In Chapter 6, we present a robust quantum search algorithm that iterates the operator on |s) to successfully reach |t), whereas Grover’s algorithm fails if as per the phase-matching condition. The robust algorithm also works when is generalized to multiple target states. Moreover, the algorithm provides a new search Hamiltonian that is robust against certain systematic perturbations. In Chapter 7, we look beyond the widely studied scenario of iterative quantum search algorithms, and present a recursive quantum search algorithm that succeeds with transformations {Vs,Vt} sufficiently close to {Is,It.} Grover’s algorithm generally fails if while the recursive algorithm is nearly optimal as long as , improving the error tolerance of the transformations. The algorithms of Chapters 6-7 have applications in quantum error-correction, when systematic errors affect the transformations The algorithms are robust as long as the errors are small, reproducible and reversible. This type of errors arise often from imperfections in apparatus setup, and so the algorithms increase the flexibility in physical implementation of quantum search. In Chapter 8, we present a fixed-point quantum search algorithm. Its state evolution monotonically converges towards |t), unlike Grover’s algorithm where the evolution passes through |t) under iterations of the operator . In q steps, our algorithm monotonically reduces the failure probability, i.e. the probability of not getting |t), from . That is asymptotically optimal for monotonic convergence. Though the fixed-point algorithm is of not much use for , it is useful when and each oracle query is highly expensive. In Chapter 9, we conclude the thesis and present an overall outlook.

In this dissertation, I have studied four theoretical problems in quantum tunneling, quantum computing, and high-temperature superconductivity. I have developed a generally-useful numerical tool for analyzing impurity-induced resonant-state images observed with scanning tunneling microscope (STM) in high temperature superconductors. The integrated tunneling intensities on all predominant sites have been estimated. The results can be used to test the predictions of any tight-binding model calculation. I have numerically simulated two-dimensional time-dependent tunneling of a Gaussian wave packet through a barrier, which contains charged ions. We have found that a negative ion in the barrier directly below the tunneling tip can deflect the tunneling electrons and drastically reduce the probability for them to reach the point in the target plane directly below the tunneling tip. I have studied an infinite family of sure-success quantum algorithms, which are introduced by C.-R. Hu [Phys. Rev. A {\bf 66}, 042301 (2002)], for solving a generalized Grover search problem. Rigorous proofs are found for several conjectures made by Hu and explicit equations are obtained for finding the values of two phase parameters which make the algorithms sure success. Using self-consistent Hartree-Fock theory, I have studied an extended Hubbard model which includes quasi-long-range Coulomb interaction between the holes (characterized by parameter V). I have found that for sufficiently large V/t, doubly-charged-antiphase-island do become energetically favored localized objects in this system for moderate values of U/t, thus supporting a recent conjecture by C.-R. Hu [Int. J. Mod. Phys. B {\bf 17}, 3284 (2003)].

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.

<p>The effects of open system evolution on single particle interferometry, quantum computation, and the adiabatic approximation are investigated.</p><p>Single particle interferometry: Three concepts concerning completely positive maps (CPMs) and trace preserving CPMs (channels), named subspace preserving (SP) CPMs, subspace local channels, and gluing of CPMs, are introduced. SP channels preserve probability weights on given orthogonal sum decompositions of the Hilbert space of a quantum system. Subspace locality determines what channels act locally with respect to such decompositions. Gluings are the possible total channels obtainable if two evolution devices, characterized by channels, act jointly on a superposition of a particle in their inputs. It is shown that gluings are not uniquely determined by the two channels. We determine all possible interference patterns in single particle interferometry for given channels acting in the interferometer paths. It is shown that the standard interferometric setup cannot distinguish all gluings, but a generalized setup can.</p><p>Quantum computing: The robustness of local and global adiabatic quantum search subject to decoherence in the instantaneous eigenbasis of the search Hamiltonian, is examined. In both the global and local search case the asymptotic time-complexity of the ideal closed case is preserved, as long as the Hamiltonian dynamics is present. In the case of pure decoherence, where the environment monitors the search Hamiltonian, it is shown that the local adiabatic quantum search performs as the classical search with scaling N, and that the global search scales like N^3/2 , where N is the list length. We consider success probabilities p<1 and prove bounds on the run-time with the same scaling as in the conditions for the p → 1 limit.</p><p>Adiabatic evolution: We generalize the adiabatic approximation to the case of open quantum systems in the joint limit of slow change and weak open system disturbances. </p>

The effects of open system evolution on single particle interferometry, quantum computation, and the adiabatic approximation are investigated. Single particle interferometry: Three concepts concerning completely positive maps (CPMs) and trace preserving CPMs (channels), named subspace preserving (SP) CPMs, subspace local channels, and gluing of CPMs, are introduced. SP channels preserve probability weights on given orthogonal sum decompositions of the Hilbert space of a quantum system. Subspace locality determines what channels act locally with respect to such decompositions. Gluings are the possible total channels obtainable if two evolution devices, characterized by channels, act jointly on a superposition of a particle in their inputs. It is shown that gluings are not uniquely determined by the two channels. We determine all possible interference patterns in single particle interferometry for given channels acting in the interferometer paths. It is shown that the standard interferometric setup cannot distinguish all gluings, but a generalized setup can. Quantum computing: The robustness of local and global adiabatic quantum search subject to decoherence in the instantaneous eigenbasis of the search Hamiltonian, is examined. In both the global and local search case the asymptotic time-complexity of the ideal closed case is preserved, as long as the Hamiltonian dynamics is present. In the case of pure decoherence, where the environment monitors the search Hamiltonian, it is shown that the local adiabatic quantum search performs as the classical search with scaling N, and that the global search scales like N3/2 , where N is the list length. We consider success probabilities p&lt;1 and prove bounds on the run-time with the same scaling as in the conditions for the p → 1 limit. Adiabatic evolution: We generalize the adiabatic approximation to the case of open quantum systems in the joint limit of slow change and weak open system disturbances.

This thesis’ aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover. Grover’s algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this thesis is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grover’s algorithm or similar techniques, that can be used as subroutines in many quantum algorithms. The tools we provide are carefully constructed: they are easy to use, and they are asymptotically faster than the best tools previously available. The tools that we supersede include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer. After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible classical algorithm. These algorithms come from graph theory, computational geometry and dynamic programming. We discuss a breadth-first search that is faster than (edges) (the classical limit) in a dense graph, maximum-points-on-a-line in (N3/2 lgN) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.

This thesis aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover. Grovers algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this thesis is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grovers algorithm or similar techniques, that can be used as subroutines in many quantum algorithms. The tools we provide are carefully constructed: they are easy to use, and they are asymptotically faster than the best tools previously available. The tools that we supersede include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer. After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible classical algorithm. These algorithms come from graph theory, computational geometry and dynamic programming. We discuss a breadth-first search that is faster than (edges) (the classical limit) in a dense graph, maximum-points-on-a-line in (N3/2 lgN) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.

Le transport des ondes joue un rôle majeur dans les systèmes de communication comme le Wifi ou les fibres optiques. Les principaux problèmes rencontrés dans ces systèmes concernent la protection contre les intrusions, la consommation d’énergie et le filtrage modal. Nous proposons différentes expériences micro-ondes mettant toutes en œuvre une mise en forme des ondes, pour traiter ces problèmes. Dans une cavité micro-ondes, des états de diffusion particuliers sont générés en s’appuyant uniquement sur des mesures de transmission et sur le formalisme du temps de retard de Wigner-Smith. Ces états sont capables d’éviter une région déterminée de la cavité, de se concentrer sur un point particulier, ou de suivre une trajectoire d’une particule classique. Le filtrage de mode est mis en œuvre dans un guide d’ondes aux frontières ondulées et en présence de pertes dépendant de la position. Le profil du guide est choisi de façon à ce que les deux modes de Bloch qui se propagent encerclent un point exceptionnel. Cette trajectoire s’accompagne d’une transition non-adiabatique entre les deux modes et d'un filtrage asymétrique de ces modes. La thèse présente également des travaux liés à la problématique des algorithmes de « recherche quantique », notamment l’algorithme de Grover. Cette recherche est mise en œuvre dans un réseau en nid d’abeilles de résonateurs micro-ondes couplés, bien décrits par un modèle de liaisons fortes (le système constitue un analogue micro-ondes du graphène). Une expérience de preuve de principe propose la recherche de deux résonateurs distincts reliés au réseau. La loi d’échelle attendue pour cet algorithme est expérimentalement obtenue dans une chaîne linéaire / Transport of waves plays an important role in modern communication systems like Wi-Fi or optical fibres. Typical problems in such systems concern security against possible intruders, energy consumption, time efficiency and the possibility of mode filtering. Microwave experiments are suited to study this kind of problems, because they offer a good control of the experimental parameters. Thus we can implement the method of wave shaping to investigate atypical transport phenomena, which address the mentioned problems. Wave front shaping solely based on the transmission together with the Wigner-Smith time delay formalism allows me to establish special scattering states in situ. These scattering states avoid a pre-selected region, focus on a specific spot or follow trajectories of classical particles, so called particle-like scattering states. Mode filtering is induced inside a waveguide with wavy boundaries and position dependent loss. The boundary profiles are chosen in such a way that the two propagating modes describe an encircling of an exceptional point in the Bloch picture. The asymmetric mode filtering is found due to the appearing non-adiabatic transitions. Another part of my work deals with Grover’s quantum search. I put such a search into practice in a two-dimensional graphene-lattice using coupled resonators, which form a tight-binding analogue. In this proof of principle experiment we search for different resonators attached to the graphene-lattice. Furthermore, the scaling behaviour of the quantum search is quantified for a linear chain of resonators