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.     

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     

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.     

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.     

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.     

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.     

Negativity in the generalized Valence Bond Solid state

Using a graphical presentation of the spin S one-dimensional Valence Bond Solid (VBS) state, based on the representation theory of the \({\textit{SU}}(2)\) Lie algebra of spins, we compute the spectrum of a mixed-state reduced density matrix. This mixed state of two blocks of spins A and B is obtained by tracing out the spins outside A and B, in the pure VBS state density matrix. We find in particular that the negativity of the mixed state is nonzero only for adjacent subsystems. The method introduced here can be generalized to the computation of entanglement properties in Levin–Wen models, that possess a similar algebraic structure to the VBS state in the ground state.