Dissertations / Theses on the topic 'Grover’s algorithm'

Image analysis and classification have become a very active research topic in recent decades. The practical applications where classification of images is of importance range from technology to geographical, civil, military, and biological sciences. This article proposes an efficient image classification algorithm based on a recently developed regression method. Groves of regression trees are used with image feature sampling to learn patterns from images that are later used to define a probabilistic framework for classification purposes. This new method can generalize well with small number of training subwindows. By comparing several publicly available datasets, this paper shows how the new method outperforms several state of the art techniques.

Kvantová výpočetní technika je rychle rostoucí obor informatiky, který přenáší principy kvantových jevu do našeho každodenního života. Díky své kvantové podstatě získávají kvantové počítače převahu nad klasickými počítači. V této práci jsme se zaměřili na vysvětlení základů kvantového počítání a jeho implementaci na kvantovém počítači. Zejména se zaměřujeme na popis fungování, konstrukci a implementaci Groverova algoritmu jako jednoho ze základních kvantových algoritmů. Demonstrovali jsme sílu tohoto kvantového algoritmu při prohledávání databáze a porovnávali ho s klasickými nekvantovými algoritmy pomocí implementace prostřednictvím simulačního prostředí QISKit. Pro simulaci jsme použili QASM Simulator a State vector Simulator Aer backends a ukázali, že získané výsledky korelují s dříve diskutovanými teoretickými poznatky. Toto ukazuje, že Groverův algoritmus umožňuje kvadratické zrychlení oproti klasickému nekvantovému vyhledávacímu algoritmu, Použitelnost algoritmu stejně jako ostatních kvantových algoritmů je ale stále omezena několika faktory, mezi které patří vysoké úrovně dekoherence a chyby hradla.

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 presents a novel quantum algorithm that solves the Chromatic Number problem. Complexity analysis of this algorithm revealed a run time of O(2n/2n2(log2n)2). This is an improvement over the best known algorithm, with a run time of 2nnO(1) [1]. This algorithm uses the Quantum Search algorithm (often called Grover's Algorithm), and the Quantum Counting algorithm. Chromatic Number is an example of an NP-Hard problem, which suggests that other NP-Hard problems can also benefit from a speed-up provided by quantum technology. This has wide implications as many real world problems can be framed as NP-Hard problems, so any speed-up in the solution of these problems is highly sought after. A bulk of this thesis consists of a review of the underlying principles of quantum mechanics and quantum computing, building to the Quantum Search and Quantum Counting algorithms. The review is written with the assumption that the reader has no prior knowledge on quantum computing. This culminates with a presentation of algorithms for generating the quantum circuits required to solve K-Coloring and Chromatic Number.

Cette thèse s'intéresse à deux types de systèmes de différents degrés de liberté en interaction, et soumis à des fluctuations quantiques.Dans le premier projet abordé dans le manuscrit, on établit un diagramme de phase d'électrons en interactions dans un cristal bidimensionnel à géométrie kagome. Ce diagramme de phase est dressé en fonction de deux paramètres étant les interactions coulombiennes entre électrons sur un même atome pour le premier, et sur des atomes plus proches voisins pour le second. Les énergies caractéristiques de ces deux interactions sont quantifiées par rapport à une énergie de référence étant celle des fluctuations quantiques. On met alors en évidence quatre phases dont deux sont nouvelles, alors que les deux autres font le lien avec la littérature déjà existante, et sont en accord avec cette dernière. Ces deux nouvelles phases émergent lorsque l'énergie de répulsion coulombienne entre électrons sur un même atome domine devant l’énergie caractéristique des fluctuations quantiques. En présence d’une forte répulsion coulombienne entre électrons sur des atomes plus proches voisins, les charges électroniques ne peuvent se délocaliser pour former des ondes de Bloch et sont soumis à ce que l’on appelle une contrainte locale de charge. Apparaissent alors sous la compétition de ces deux interactions coulombiennes, des modes unidimensionnels collectifs le long des chaines d’atomes antiferromagnétiquement ordonnées. Ces modes ont la particularité d’être stabilisés à la fois par les fluctuations des degrés de liberté de spin, et de charge des électrons. La seconde de ces nouvelles phases émerge lorsque la répulsion coulombienne entre électrons sur des atomes voisins devient faible devant les fluctuations quantiques. La contrainte locale est alors relâchée et les électrons forment des ondes de Bloch le long de ce qui s’apparente à des bulles quantiques unidimensionnelles et polarisées en spin. Ces bulles sont alors piégées dans un cristal d’électrons inversement polarisés, avec lesquels elles sont en interaction antiferromagnétique.Le second projet porte sur l’étude d’un aimant moléculaire de Terbium Double-Decker. Cette molécule peut être modélisée par trois degrés de liberté interagissant en cascade les uns avec les autres. Le premier d’entre eux est un degré de liberté de spin nucléaire porté par le noyau de l’ion terbium de la molécule. Ce spin nucléaire est en interaction d’échange avec un degré de liberté de spin électronique porté par les électrons de l’ion terbium. Enfin, en première approximation, ce spin électronique génère un champ dipolaire auquel sont soumis les deux ligands de l’aimant moléculaire. Ces deux ligands sont couplés à deux électrodes de source et de drain, assurant le transport d’électrons uniques à travers ces deniers. Le tout forme donc un transistor à électron unique dans lequel les ligands servent de boîte quantique. Par mesure de magnéto-conductance, il est donc possible par une lecture en cascade, de remonter à l’état du spin électronique et du spin nucléaire. La première étape du projet a donc consisté à établir un modèle décrivant l’aimant moléculaire couplé à ces deux électrodes, afin de prédire les mesures de conductance réalisées au travers du transistor lors des thèses de Stefen Thiele et Clément Godfrin. Les résultats théoriques et expérimentaux obtenus sont en accord quantitatifs.D’autres part, à l’aide de champs électriques radio-fréquences, il est possible de manipuler expérimentalement et de façon cohérente le spin nucléaire. Cette manipulation cohérente du spin nucléaire se fait par l’intermédiaire du nuage électronique de l’ion, et permet ainsi d’être en mesure de réaliser un algorithme quantique sur le spin nucléaire de l’ion terbium. La réalisation d’un programme de simulation a permis de guider la réalisation expérimentale de l’algorithme de Grover, lequel a été implémenté avec succès au cours de la thèse de Clément Godfrin<br>This thesis focuses on two different spin and charge systems, interacting under the effect of quantum fluctuations.The first project highlights the phase diagram of interacting electrons on a kagome lattice. This diagram is driven by two Coulomb repulsions. The first is a on site repulsion, and the second a nearest neighbor one. These two repulsions are in competition with quantum fluctuations of electronic charges. Four phases are depicted, two are unknown and the two other are in agreement with the literature. The two new phases are stabilized in the strong on site repulsion regime. When nearest neighbor repulsions are strong enough to induce a charge local constraint, the system enters in a so called Heisenberg-Loop Phase. These loops are antiferromagnetically arranged and can be described by a Heisenberg-like model in which both charge and spin play surprisingly a role in the exchange interaction. The second new phase is stabilized in the regime where nearest neighbor interactions are too weak to maintain the local constraint. Then, half of the electrons are delocalized in unidimensional Bloch states similar to quantum polarized electronic bubbles. These bubbles are trapped in an inversely polarized electronic cristal formed by the other electrons. This peculiar phase is favored by both quantum charge fluctuations in the bubbles, and antiferromagnetic exchanges between their electrons and the cristal ones.The second project deals with a Terbium Double-Decker molecular magnet. This molecule is modeled by three interacting degrees of freedom. The first is a nuclear spin of the Terbium ion, and the second is the electronic spin of this same ion. The two spins interact via a magnetic exchange.In a first approximation, the effect of the electronic spin is to induce a dipolar field. Finally, the last degree of freedom is carried by two ligands under the influence of the dipolar field. The ligands play the role of a read-out quantum dot, and by conductance measurements through this last one, we can probe the electronic spin and then, the nuclear spin. The first step of this project highlights the modeling of the global system. Then numerical computations are depicted and are in a quantitative agreement with the experimental measurements realized during the thesis of Stefan Thiele and Clément Godfrin.On the other hand, by applying electrical Radio Frequency Fields, we can drive quantum fluctuations on the nuclear spin. This quantum manipulation of the spin is realized by the dynamic deformation of the electron cloud under the effect of the Radio Frequency Field. As a result, we are able to implement a Grover Quantum Algorithm on the nuclear field. This thesis focuses on the realization of a simulation program that was a tool used by Clément Godfrin to successfully implement the Grover Algorithm

la versión de onda semiclásica del algoritmo cuántico de búsqueda basada en un sistema de osciladores armónicos simples, no especifica un atributo importante que está presente en el algoritmo de Grover, como lo es el entrelazamiento. Al tomar en cuenta el entrelazamiento en la versión de onda, se halla que, el período de oscilación no concuerda con el tiempo de ejecución del algoritmo de Grover, de dicha observación se proponen dos argumentos, uno cualitativo y el otro cuantitativo, para que el tiempo y el tiempo coincidan. Para el argumento cualitativo se emplea la naturaleza probabilística del algoritmo cuántico. Dentro del argumento cuantitativo se identifica un parámetro en la versión de onda que está relacionado con el entrelazamiento. La diferencia con el tiempo de ejecución se resuelve eligiendo valores apropiados de tal parámetro que incorpora entrelazamiento. La utilidad de los argumentos actuales es evidente si la versión de onda del algoritmo cuántico de búsqueda se implementa experimentalmente a través de un sistema de N puntos cuánticos con un potencial de oscilación armónico de conexión para cada uno de los N puntos que deben estar acoplados a un único punto cuántico adicional que se entrelaza con todos ellos. Con el fin de obtener resultados óptimos, las constantes de acoplamiento deben ejecutarse de la manera descrita en el presente trabajo.<br>CONACyT UAEMEX

Este trabajo trata sobre la aplicación de dos algoritmos de búsqueda a la selección de individuos óptimos en la población inicial de un algoritmo genético, y la consiguiente comparación entre ambos. El primero de ellos es el algoritmo meta-heurístico GRASP, y el segundo es el algoritmo cuántico de Grover. El algoritmo cuántico de Grover forma parte de una nueva generación en las ciencias de la computación: la computación cuántica. Y por tanto hace uso de conceptos matemáticos y físicos completamente distintos a los usados en la programación clásica. En esta tesis se presenta un análisis general de ambos algoritmos, siendo de especial mención el análisis del algoritmo cuántico de Grover, ya que incluye un modelo matemático del funcionamiento del mismo. Este modelo será de suma importancia para simular la ejecución del algoritmo de Grover en una computadora clásica, dada la carencia de una computadora cuántica sobre la cual realizar esto. Luego, se preparan dos procesos experimentales, los cuales se usarán para realizar la comparación de eficacia y eficiencia entre las ejecuciones de los dos algoritmos. Posteriormente, se presenta el diseño e implementación de los algoritmos, ambos aplicados a la selección de individuos de un algoritmo genético genérico. Una vez ambos algoritmos se encuentren correctamente implementados y funcionales, se ejecutarán las pruebas experimentales que permitan realizar la comparación entre ellos. Finalmente se realizan las conclusiones y observaciones del caso en base a los resultados numéricos obtenidos en la fase experimental.<br>Tesis

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.

Standard quantum computation proceeds via the unitary evolution of physical qubits (two-level systems) that carry the information. A remarkably different model is one-way quantum computing where a quantum algorithm is implemented by a set of irreversible measurements on a large array of entangled qubits,, known as the cluster state. The order and sequence of these measurements allow for different algorithms to be implemented. With a large enough cluster state and a method in which to perform single-qubit measurements the desired computation can be realised. We propose a potential implementation of one-way quantum computing using qubits encoded in the orbital angular momentum degree of freedom of single photons. Photons are good carriers of quantum information because of their weak interaction with the environment and the orbital angular momentum of single photons offers access to an infinite-dimensional Hilbert space for encoding information. Spontaneous parametric down-conversion is combined with a series of optical elements to generate a four-photon orbital angular momentum entangled cluster state and single-qubit measurements are carried out by means of digital holography. The proposed set-up, which is based on an experiment that utilised polarised photons, can be used to realise Grover’s search algorithm which performs a search through an unstructured database of four elements. Our application is restricted to a two-dimensional subspace of a multi-dimensional system, but this research facilitates the use of orbital angular momentum qubits for quantum information processing and points towards the usage of photonic qudits (multi-level systems). We also review the application of Dirac notation to paraxial light beams on a classical and quantum level. This formalism is generally employed in quantum mechanics but the analogy with paraxial optics allows us to represent the classical states of light by means of Dirac kets. An analysis of the analogy between the classical and quantum states of light using this formalism, is presented.<br>Thesis (M.Sc.)-University of KwaZulu-Natal, Durban, 2011.

Random walks describe diffusion processes, where movement at every time step is restricted only to neighbouring locations. Classical random walks are constructed using the non-relativistic Laplacian evolution operator and a coin toss instruction. In quantum theory, an alternative is to use the relativistic Dirac operator. That necessarily introduces an internal degree of freedom (chirality), which may be identified with the coin. The resultant walk spreads quadratically faster than the classical one, and can be applied to a variety of graph theoretical problems. We study in detail the problem of spatial search, i.e. finding a marked site on a hypercubic lattice in d-dimensions. For d=1, the scaling behaviour of classical and quantum spatial search is the same due to the restriction on movement. On the other hand, the restriction on movement hardly matters for d ≥ 3, and scaling behaviour close to Grover’s optimal algorithm(which has no restriction on movement) can be achieved. d=2 is the borderline critical dimension, where infrared divergence in propagation leads to logarithmic slow down that can be minimised using clever chirality flips. In support of these analytic expectations, we present numerical simulation results for d=2 to d=9, using a lattice implementation of the Dirac operator inspired by staggered fermions. We optimise the parameters of the algorithm, and the simulation results demonstrate that the number of binary oracle calls required for d= 2 and d ≥ 3 spatial search problems are O(√NlogN) and O(√N) respectively. Moreover, with increasing d, the results approach the optimal behaviour of Grover’s algorithm(corresponding to mean field theory or d → ∞ limit). In particular, the d = 3 scaling behaviour is only about 25% higher than the optimal value.