Entanglement in valence-bond-solid states and quantum search

The present dissertation covers two independent subjects: (i) The quantum entanglement in Valence-Bond-Solid states, and (ii) quantum database search algorithms. Both subjects are presented in a self-contained and pedagogical way.(i) The first chapter is a through introduction to the subject of quantum entanglement in Valence-Bond-Solid (VBS) states defined on a lattice or graph. The VBS state was first introduced as the ground state of the celebrated Affleck-Kennedy-Lieb-Tasaki (AKLT) spin chain model in statistical mechanics. Then it became essential in condensed matter physics, quantum information and measurement-based quantum computation. Recent studies elucidated important entanglement properties of the VBS state. We start with the definition of a general AKLT model and the construction of VBS ground states. A subsystem is introduced and described by the density matrix. Exact spectrum properties of the density matrix are proved and discussed. Density matrices of 1-dimensional models are diagonalized and the entanglement entropies (the von Neumann entropy and Renyi entropy) are calculated. The entropies take saturated value and the density matrix is proportional to a projector in the large subsystem limit.(ii) The second chapter is a detailed introduction to the subject of quantum database search algorithms. The problem of searching a large database (a Hilbert space) for a target item is performed by the famous Grover algorithm which locates the target item with probability 1 and a quadratic speed up compared with the corresponding classical algorithm. If the database is partitioned into blocks and one is searching for the block containing the target item instead of the target item itself, then the problem is referred to as partial search. Partial search trades accuracy for speed and the most efficient version is the Grover-Radhakrishnan-Korepin (GRK) algorithm. The target block can be further partitioned into subblocks so that GRK can be performed in a sequence called a hierarchy. We formulate the Grover search and GRK partial search and prove that a GRK hierarchy is less efficient than a direct GRK partial search.