混合态数据库的Grover算法数学形式及其搜索成功率

Grover提出了容量为N的数据库量子搜索法.只需进行O(平方根N)次迭代就能以几乎为1的概率实现对目标的搜索.本文将文献[1]的Grover搜索法推广到混合态情形,给出了一个基于混合态的Grover搜索法,并分析了该搜索法成功的概率上界.进一步发现搜索法成功的概率完全依赖于所使用的初态(混合态).该结论为了解量子噪声对Grover搜索法的影响提供一定的理论依据.最后通过例子说明了如何实施基于混合态的Grover搜索法.     

Adiabatic quantum search scheme with atoms in a cavity driven by lasers

We propose an implementation of the quantum search algorithm of a marked item in an unsorted list of N items by adiabatic passage in a cavity-laser-atom system. We use an ensemble of N identical three-level atoms trapped in a single-mode cavity and driven by two lasers. In each atom, the same level represents a database entry. One of the atoms is marked by having an energy gap between its two ground states. Appropriate time delays between the two laser pulses allow one to populate the marked state starting from an initial entangled state within a decoherence-free adiabatic subspace. The time to achieve such a process is shown to exhibit the square root N Grover speedup.     

Partial evolution based local adiabatic quantum search

Recently, Zhang and Lu provided a quantum search algorithm based on partial adiabatic evolution, which beats the time bound of local adiabatic search when the number of marked items in the unsorted database is larger than one. Later, they found that the above two adiabatic search algorithms had the same time complexity when there is only one marked item in the database. In the present paper, following the idea of Roland and Cerf [Roland J and Cerf N J 2002 Phys. Rev. A 65 042308], if within the small symmetric evolution interval defined by Zhang et al., a local adiabatic evolution is performed instead of the original “global” one, this “new” algorithm exhibits slightly better performance, although they are progressively equivalent with M increasing. In addition, the proof of the optimality for this partial evolution based local adiabatic search when M=1 is also presented. Two other special cases of the adiabatic algorithm obtained by appropriately tuning the evolution interval of partial adiabatic evolution based quantum search, which are found to have the same phenomenon above, are also discussed.     

An Exact Quantum Search Algorithm with Arbitrary Database

In standard Grover’s algorithm for quantum searching, the probability of finding a marked state is not exactly 1, and some modified versions of Grover’s algorithm that search a marked state from an evenly distributed database with full successful rate have been presented. In this article, we present a generalized quantum search algorithm that searches M marked states from an arbitrary distributed N-item quantum database with a zero theoretical failure rate, where N is not necessary to be the power of 2. We analyze the general properties of our search algorithm, we find that our algorithm has periodicity with a period of 2J + 1, and it is effective with certainty for J + (2J + 1)m times of iteration, where m is an arbitrary nonnegative number.     

Implementation of quantum search scheme by adiabatic passage in a cavity--laser--atom system

This paper proposes a scheme for implementing the adiabatic quantum search algorithm of different marked items in an unsorted list of N items with atoms in a cavity driven by lasers. N identical three-level atoms are trapped in a single-mode cavity. Each atom is driven by a set of three pulsed laser fields. In each atom, the same level represents a database entry. Two of the atoms are marked differently. The marked atom has an energy gap between its two ground states. The two different marked states can be sought out respectively starting from an initial entangled state by controlling the ratio of three pulse amplitudes. Moreover, the mechanism, based on adiabatic passage, constitutes a decoherence-free method in the sense that spontaneous emission and cavity damping are avoided since the dynamics follows the dark state. Furthermore, this paper extends the algorithm with m (m>2) atoms marked in an ideal situation. Any different marked state can be sought out.     

基于相位匹配的量子行走搜索算法及电路实现

量子行走是经典随机行走在量子力学框架下的对应, 理论上可以用来解决一类无序数据库的搜索问题. 因为携带信息的量子态的扩散速度与经典相比有二次方式的增长, 所以量子行走优于经典随机行走, 量子行走的特性值得加以利用. 量子行走作为一种新发现的物理现象的数学描述, 引发了一种新的思维方式, 孕育了一种新的理论计算模型. 最新研究表明, 量子行走本身也是一种通用计算模型, 可被视为设计量子算法的高级工具, 因此受到部分计算机理论科学领域学者的关注和研究. 对于多数问题求解方案的量子算法的设计, 理论上可以只在量子行走模型下进行考虑. 基于Grover算法的相位匹配条件, 本文提出了一个新的基于量子行走的搜索算法. 理论演算表明: 一般情况下本算法的时间复杂度与Grover算法相同, 但是当搜索的目标数目多于总数的1/3时, 本算法搜索成功的概率要大于Grover算法. 本文不但利用Grover算法中相位匹配条件构造了一个新的量子行走搜索算法, 而且在本研究室原有的量子电路设计研究成果的基础上给出了该算法的量子电路表述.     

Quantum Query Complexity for Searching Multiple Marked States from an Unsorted Database

An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover＇s original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long＇s algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a ＂duality computer＂ and show its advantage over other algorithms.     

Fixed-point quantum search

The quantum search algorithm consists of an iterative sequence of selective inversions and diffusion type operations, as a result of which it is able to find a state with desired properties (target state) in an unsorted database of size N in only sqrt[N] queries. This is achieved by designing the iterative transformations in a way that each iteration results in a small rotation of the state vector in a two-dimensional Hilbert space that includes the target state; if we choose the right number of iterative steps, we will stop just at the target state. This Letter shows that by replacing the selective inversions by selective phase shifts of pi/3, the algorithm preferentially converges to the target state irrespective of the step size or number of iterations. This feature leads to robust search algorithms and also to new schemes for quantum control and error correction.     

Quantum Query Complexity for Searching Multiple Marked States from an Unsorted Database

An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover's original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long's algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a "duality computer" and show its advantage over other algorithms.     

Implementation of quantum search algorithm using classical Fourier optics

We report on an experiment on Grover's quantum search algorithm showing that classical waves can search a N-item database as efficiently as quantum mechanics can. The transverse beam profile of a short laser pulse is processed iteratively as the pulse bounces back and forth between two mirrors. We directly observe the sought item being found in approximately square root[N] iterations, in the form of a growing intensity peak on this profile. Although the lack of quantum entanglement limits the size of our database, our results show that entanglement is neither necessary for the algorithm itself, nor for its efficiency.     

Arbitrary Phase Rotation of the Marked State Cannot Be Used for Grover's Quantum Search Algorithm

A misunderstanding that an arbitrary phase rotation of the marked state together with the inversion about average operation can be used to construct a (less efficient) quantum search algorithm is cleared. The π rotation of the phase of the marked state is not only the choice for efficiency, but also vital in Grover's quantum search algorithm. The results also show that Grover's quantum search algorithm is robust.     

Experimental quantum deletion in an NMR quantum information processor

We report an NMR experimental realization of a rapid quantum deletion algorithm that deletes marked states in an unsorted database.Unlike classical deletion,where search and deletion are equivalent,quantum deletion can be implemented with only a single query,which achieves exponential speed-up compared to the optimal classical analog.In the experimental realization,the GRAPE algorithm was used to obtain an optimized NMR pulse sequence,and the efficient method of maximum-likelihood has been used to reconstruct the experimental output state.     

加权量子搜索算法及其相位匹配条件研究

目前的Grover算法在无序数据库中搜索多个目标时,得到不同目标的几率是相等的,不考虑各个目标重要程度的差异;并且当目标数超过数据库记录总数的四分之一时,搜索到目标的几率迅速下降,当目标数超过记录总数的一半时,算法失效.针对这两个问题,首先提出一种基于加权目标的搜索算法.根据各子目标的重要程度,为每个子目标赋予一个权系数,应用这些权系数将多个子目标表示成一个量子叠加态,这样可使得到每个子目标的几率等于其自身的权系数;其次,提出自适应相位匹配条件,该条件中两次相位旋转的方向相反,大小根据目标量子叠加态和系统初始状态的内积决定.当该内积大于等于((3-√5)/8)^1/2时,至多只需两步搜索,即可以恒等于1的几率得到搜索目标.实验表明,算法及其相位匹配条件是有效的.     

A Necessary Condition for Quantum Adiabaticity Applied to the Adiabatic Grover Search

Numerous sufficient conditions for adiabaticity of the evolution of a driven quantum system have been known for quite a long time. In contrast, necessary adiabatic conditions are scarce. Recently a practicable necessary condition well suited for many-body systems has been proved. Here we tailor this condition for estimating run times of adiabatic quantum algorithms. As an illustration, the condition is applied to the adiabatic algorithm for searching in an unstructured database (adiabatic Grover search algorithm). We find that the thus obtained lower bound on the run time of this algorithm reproduces \( \sqrt{N} \) scaling (with N being the number of database entries) of the explicitly known optimum run time. This is in contrast to the poor performance of the known sufficient adiabatic conditions, which guarantee adiabaticity only for a run time on the order of O(N), which does not constitute any speedup over the classical database search. This observation highlights the merits of the new adiabatic condition and its potential relevance to adiabatic quantum computing.     

Decoherence in optimized quantum random-walk search algorithm

This paper investigates the effects of decoherence generated by broken-link-type noise in the hypercube on an optimized quantum random-walk search algorithm. When the hypercube occurs with random broken links, the optimized quantum random-walk search algorithm with decoherence is depicted through defining the shift operator which includes the possibility of broken links. For a given database size, we obtain the maximum success rate of the algorithm and the required number of iterations through numerical simulations and analysis when the algorithm is in the presence of decoherence. Then the computational complexity of the algorithm with decoherence is obtained. The results show that the ultimate effect of broken-link-type decoherence on the optimized quantum random-walk search algorithm is negative.     

Experimental implementation of local adiabatic evolution algorithms by an NMR quantum information processor

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, using the local adiabatic evolution, the algorithms given by J. Roland and N.J. Cerf for Grover's search [J. Roland, N.J. Cerf, Quantum search by local adiabatic evolution, Phys. Rev. A 65 (2002) 042308] and by Saurya Das, Randy Kobes, and Gabor Kunstatter for the Deutsch-Jozsa algorithm [S. Das, R. Kobes, G. Kunstatter, Adiabatic quantum computation and Deutsh's algorithm, Phys. Rev. A 65 (2002) 062301], yield a complexity of order N (where N=2(n) and n is the number of qubits). In this paper, we report the experimental implementation of these local adiabatic evolution algorithms on a 2-qubit quantum information processor, by Nuclear Magnetic Resonance.     

Fast quantum search algorithm for databases of arbitrary size and its implementation in a cavity QED system

We propose a method for implementing the Grover search algorithm directly in a database containing any number of items based on multi-level systems. Compared with the searching procedure in the database with qubits encoding, our modified algorithm needs fewer iteration steps to find the marked item and uses the carriers of the information more economically. Furthermore, we illustrate how to realize our idea in cavity QED using Zeeman?s level structure of atoms. And the numerical simulation under the influence of the cavity and atom decays shows that the scheme could be achieved efficiently within current state-of-the-art technology.     

Synthesis of quantum superpositions by quantum computation

The quantum search algorithm can be looked at as a technique for synthesizing a particular kind of superposition-one whose amplitude is concentrated in a single basis state. This basis state is defined by a binary function f(&xmacr;) that is nonzero in this desired basis state and zero everywhere else. This paper extends the quantum search algorithm to an algorithm that can create an arbitrarily specified superposition on a space of size N in O(sqrt[N] ) steps. The superposition is specified by a complex valued function f(&xmacr;) that specifies the desired amplitude of the system in basis state &xmacr;.     

Quantum random access memory

A random access memory (RAM) uses n bits to randomly address N=2(n) distinct memory cells. A quantum random access memory (QRAM) uses n qubits to address any quantum superposition of N memory cells. We present an architecture that exponentially reduces the requirements for a memory call: O(logN) switches need be thrown instead of the N used in conventional (classical or quantum) RAM designs. This yields a more robust QRAM algorithm, as it in general requires entanglement among exponentially less gates, and leads to an exponential decrease in the power needed for addressing. A quantum optical implementation is presented.