Simple Algorithm for Partial Quantum Search

Quite often in database search, we only need to extract portion of the information about the satisfying item. We consider this problem in the following form: the database of N items is separated into K blocks of size b = N / K elements each and an algorithm has just to find the block containing the item of interest. The queries are exactly the same as in the standard database search problem. We present a quantum algorithm for this problem of partial search that takes about 0.34 fewer iterations than the quantum search algorithm.     

Quest for Fast Partial Search Algorithm

The Grover quantum algorithm can find a target item in a database faster than any classical algorithm. In partial search, one trades accuracy for speed, and a part of the database (a block) containing the target item can be found even faster. We consider different partial search algorithms and argue that the algorithm originally suggested by Grover and Radhakrishnan and modified by Korepin is the optimal one. The efficiency of an algorithm is measured by the number of queries to the oracle.     

Thermodynamic Interpretation of the Quantum Error Correcting Criterion

Shannon's fundamental coding theorems relate classical information theory to thermodynamics. More recent theoretical work has been successful in relating quantum information theory to thermodynamics. For example, Schumacher proved a quantum version of Shannon's 1948 classical noiseless coding theorem. In this note, we extend the connection between quantum information theory and thermodynamics to include quantum error correction. There is a standard mechanism for describing errors that may occur during the transmission, storage, and manipulation of quantum information. One can formulate a criterion of necessary and sufficient conditions for the errors to be detectable and correctable. We show that this criterion has a thermodynamical interpretation. PACS: 03.67; 05.30; 63.10     

Block spin density matrix of the inhomogeneous AKLT model

We study the inhomogeneous generalization of a 1-dimensional AKLT spin chain model. Spins at each lattice site could be different. Under certain conditions, the ground state of this AKLT model is unique and is described by the Valence-Bond-Solid (VBS) state. We calculate the density matrix of a contiguous block of bulk spins in this ground state. The density matrix is independent of spins outside the block. It is diagonalized and shown to be a projector onto a subspace. We prove that for large block the density matrix behaves as the identity in the subspace. The von Neumann entropy coincides with Renyi entropy and is equal to the saturated value.      

Quantum partial search for uneven distribution of multiple target items

Quantum partial search algorithm is an approximate search. It aims to find a target block (which has the target items). It runs a little faster than full Grover search. In this paper, we consider quantum partial search algorithm for multiple target items unevenly distributed in a database (target blocks have different number of target items). The algorithm we describe can locate one of the target blocks. Efficiency of the algorithm is measured by number of queries to the oracle. We optimize the algorithm in order to improve efficiency. By perturbation method, we find that the algorithm runs the fastest when target items are evenly distributed in database.     

Spectrum of the density matrix of a large block of spins of the XY model in one dimension

We consider reduced density matrix of a large block of consecutive spins in the ground states of the XY spin chain on an infinite lattice. We derive the spectrum of the density matrix using expression of Rényi entropy in terms of modular functions. The eigenvalues λ _n form exact geometric sequence. For example, for strong magnetic field λ _n = C exp(−π τ ₀ n), here τ ₀ > 0 and C > 0 depend on anisotropy and magnetic field. Different eigenvalues are degenerated differently. The largest eigenvalue is unique, but degeneracy g _n increases sub-exponentially as eigenvalues diminish: g_n ~ exp(p?{n/3}){g_{n}sim exp{(pi sqrt{n/3})}}. For weak magnetic field expressions are similar.     

A review on quantum search algorithms

The use of superposition of states in quantum computation, known as quantum parallelism, has significant advantage in terms of speed over the classical computation. It is evident from the early invented quantum algorithms such as Deutsch’s algorithm, Deutsch–Jozsa algorithm and its variation as Bernstein–Vazirani algorithm, Simon algorithm, Shor’s algorithms, etc. Quantum parallelism also significantly speeds up the database search algorithm, which is important in computer science because it comes as a subroutine in many important algorithms. Quantum database search of Grover achieves the task of finding the target element in an unsorted database in a time quadratically faster than the classical computer. We review Grover’s quantum search algorithms for a singe and multiple target elements in a database. The partial search algorithm of Grover and Radhakrishnan and its optimization by Korepin called GRK algorithm are also discussed.     

Quantum Partial Search of a Database with Several Target Items

We consider unstructured database separated into blocks of equal size. Blocks containing target items are called target blocks. Blocks without target items are called non-target blocks. We present a fast quantum algorithm, which finds one of the target blocks. The algorithm uses the same oracle, which the main Grover algorithm does. We study the simplest case, when each target block has the same number of target items. Our algorithm is based on Boyer, Brassard, Hoyer, and Tapp algorithm of searching database with several target items and on Grover–Radhakrishnan algorithm of partial search. We minimize the number of queries to the oracle. We analyze the algorithm for blocks of large size. In next publications we shall consider more general case when the number of target items is different in different target blocks.