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

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

Design of quantum VQ iteration and quantum VQ encoding algorithm taking O（√N） steps for data compression

Vector quantization (VQ) is an important data compression method. The key of the encoding of VQ is to find the closest vector among N vectors for a feature vector. Many classical linear search algorithms take $O(N)$ steps of distance computing between two vectors. The quantum VQ iteration and corresponding quantum VQ encoding algorithm that takes $O(\sqrt N )$ steps are presented in this paper. The unitary operation of distance computing can be performed on a number of vectors simultaneously because the quantum state exists in a superposition of states. The quantum VQ iteration comprises three oracles, by contrast many quantum algorithms have only one oracle, such as Shor's factorization algorithm and Grover's algorithm. Entanglement state is generated and used, by contrast the state in Grover's algorithm is not an entanglement state. The quantum VQ iteration is a rotation over subspace, by contrast the Grover iteration is a rotation over global space. The quantum VQ iteration extends the Grover iteration to the more complex search that requires more oracles. The method of the quantum VQ iteration is universal.     

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.     

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.     

Efficient State Preparation via Ion Trap Quantum Computing and Quantum Searching Algorithm

We present a scheme to-prepare a quantum state in an ion trap with probability approaching to one by means of ion trap quantum computing and Grover's quantum search algorithm acting on trapped ions.     

量子相关词汇搜索

本文讨论了基于量子并行计算和叠加态原理的量子搜索算法,并结合概率论,给出了从无结构的海量数据(库)中搜索相关词汇(组)的方法,并说明该方法远远优越于经典搜索算法。     

First experimental demonstration of an exact quantum search algorithm in nuclear magnetic resonance system

The success probability of searching an objective item from an unsorted database using standard Grover's algorithm is usually not exactly 1. It is exactly 1 only when it is used to find the target state from a database with four items. Exact search is always important in theoretical and practical applications. The failure rate of Grover's algorithm becomes big when the database is small, and this hinders the use of the commonly used divide-and-verify strategy. Even for large database, the failure rate becomes considerably large when there are many marked items. This has put a serious limitation on the usability of the Grover's algorithm. An important improved version of the Grover's algorithm, also known as the improved Grover algorithm, solves this problem. The improved Grover algorithm searches arbitrary number of target states from an unsorted database with full success rate. Here, we give the first experimental realization of the improved Grover algorithm, which finds a marked state with certainty, in a nuclear magnetic resonance system. The optimal control theory is used to obtain an optimized control sequence. The experimental results agree well with the theoretical predictions.     

Grover量子搜索算法及改进

简单地介绍了量子搜索算法中的相位匹配条件、 改进的成功率为100%的量子搜索算法和量子搜索算法中的主要误差等. We briefly introduced some of our recent work related to the phase matching condition in quantum searching algorithms and the improved Grover algorithm. When one replaces the two phase inversions in the Grover algorithm with arbitrary phase rotations, the modified algorithm usually fails in searching the marked state unless a phase matching condition is satisfied between the two phases. The Grover algorithm is not 100% in success rate, an improved Grover algorithm with zero failure rate is given by replacing the phase inversions with angles that depends on the size of the database. Other aspects of the Grover algorithm such as the SO(3) picture of quantum searching, the dominant gate imperfections in the Grover algorithm are also mentioned.     

Experimental realization of one-way quantum computing with two-photon four-qubit cluster states

We report an experimental realization of one-way quantum computing on a two-photon four-qubit cluster state. This is accomplished by developing a two-photon cluster state source entangled both in polarization and spatial modes. With this special source, we implemented a highly efficient Grover's search algorithm and high-fidelity two-qubit quantum gates. Our experiment demonstrates that such cluster states could serve as an ideal source and a building block for rapid and precise optical quantum computation.     

Use of non-adiabatic geometric phase for quantum computing by NMR

Geometric phases have stimulated researchers for its potential applications in many areas of science. One of them is fault-tolerant quantum computation. A preliminary requisite of quantum computation is the implementation of controlled dynamics of qubits. In controlled dynamics, one qubit undergoes coherent evolution and acquires appropriate phase, depending on the state of other qubits. If the evolution is geometric, then the phase acquired depend only on the geometry of the path executed, and is robust against certain types of error. This phenomenon leads to an inherently fault-tolerant quantum computation. Here we suggest a technique of using non-adiabatic geometric phase for quantum computation, using selective excitation. In a two-qubit system, we selectively evolve a suitable subsystem where the control qubit is in state |1, through a closed circuit. By this evolution, the target qubit gains a phase controlled by the state of the control qubit. Using the non-adiabatic geometric phase we demonstrate implementation of Deutsch-Jozsa algorithm and Grover's search algorithm in a two-qubit system.     

Novel strategy for database searching in spin liouville space by NMR ensemble computing

Quantum computing by nuclear magnetic resonance using pseudopure spin states is bound by the maximal speed of quantum computing algorithms operating on pure states. In contrast to these quantum computing algorithms, a novel algorithm for searching an unsorted database is presented here that operates on truly mixed states in spin Liouville space. It provides an exponential speedup over Grover's quantum search algorithm with the sensitivity scaling exponentially with the number of spins, as for pseudopure state implementations. The minimal decoherence time required is exponentially shorter than that for Grover's algorithm.     

NMR analogue of the generalized Grover‘s algorithm of multiple marked states and its application

The generalized Grover's algorithm for the case in which there are multiple marked states is demonstrated on a nuclear magnetic resonance (NMR) quantum computer. The Walsh－Hadamard transform and the phase inversion are all replaced. NMR analogues of Einstein－Podolsky－Rosen states (pseudo-EPR states) are synthesized using the above algorithm.     

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.     

Computational leakage: Grover's algorithm with imperfections

We study the effects of dissipation or leakage on the time evolution of Grover's algorithm for a quantum computer. We introduce an effective two-level model with dissipation and randomness (imperfections), which is based upon the idea that ideal Grover's algorithm operates in a 2-dimensional Hilbert space. The simulation results of this model and Grover's algorithm with imperfections are compared, and it is found that they are in good agreement for appropriately tuned parameters. It turns out that the main features of Grover's algorithm with imperfections can be understood in terms of two basic mechanisms, namely, a diffusion of probability density into the full Hilbert space and a stochastic rotation within the original 2-dimensional Hilbert space. Received 12 August 2002 / Received in final form 14 October 2002 Published online 4 February 2003     

Dense coding scheme using superpositions of Bell-states and its NMR implementation

Dense coding using superpositions of Bell-states is proposed. The generalized Grover's algorithm is used to prepare the initial entangled states, and the reverse process of the quantum algorithm is used to determine the entangled state in the decoding measurement. Compared with the previous schemes, the superpositions of two Bell-states are exploited. Our scheme is demonstrated using a nuclear magnetic resonance (NMR) quantum computer. The corresponding manipulations are obtained. Experimental results show a good agreement between theory and experiment. We also generalize the scheme to transmit eight messages by introducing an additional two-state system.     

The quadratic speedup in Grover's search algorithm from the entanglement perspective

We show that Grover's algorithm can be described as an iterative change of the bipartite entanglement, which leads to a necessary and sufficient condition for quadratic speedup. This allows us to reestablish, from the entanglement perspective, that Grover's search algorithm is the only optimal pure state search algorithm.     

Implementation of conditional phase-shift gate for quantum information processing by NMR,using transition-selective pulses

Experimental realization of quantum information processing in the field of nuclear magnetic resonance (NMR) has been well established. Implementation of conditional phase-shift gate has been a significant step, which has lead to realization of important algorithms such as Grover's search algorithm and quantum Fourier transform. This gate has so far been implemented in NMR by using coupling evolution method. We demonstrate here the implementation of the conditional phase-shift gate using transition selective pulses. As an application of the gate, we demonstrate Grover's search algorithm and quantum Fourier transform by simulations and experiments using transition selective pulses.     

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.     

基于量子并行粒子群优化算法的分数阶混沌系统参数估计

分数阶混沌系统参数估计的本质是多维参数优化问题, 其对于实现分数阶混沌控制与同步至关重要. 提出一种基于量子并行特性的粒子群优化新算法, 用于解决分数阶混沌的系统参数估计问题. 利用量子计算的并行特性, 设计出了一种新的量子编码, 使每代运算的可计算次数呈指数增加. 在此基础上, 构建了由量子当前旋转角、个体最优旋转角和全局最优旋转角共同组成的粒子演化方程, 以约束粒子在量子空间中的运动行为, 使算法的搜索能力得到了较大提高. 以分数阶Lorenz混沌系统和分数阶Chen混沌系统的参数估计为例, 进行了未知参数估计的数值仿真, 结果显示本算法具有良好的有效性、鲁棒性和通用性.