Theoretical Study On Grover Quantum Search Algorithm

Quantum computation, which processes information by using the principles of quan-tum mechanics, is a frontier discipline that is freshly developed. During the past twodecades, the study on the theory of quantum computation shows that quantum computa-tion can outperform classical computation in many aspects, especially for the problems ofquantum system simulation, large prime factorization, searching in a disorder database,etc.. For searching several marked items in a disorder database, Grover quantum search al-gorithm achieves quadratic speedup for several (although not all) heuristic classical searchalgorithm. Grover quantum search algorithm neglects the character of the searching ele-ments and concentrates on the indices of those elements, thus it has strong universalness.In the meantime, it can efficiently decode DES coding system and has potential purposefor speeding up the search of cryptographic key in coding system. In this paper, we focuson the phase matching problem, physical realization, and application of Grover quantumsearch algorithm. The main contents are presented as the followings:Quantum entanglement, which is the fundamental cause that produces quantumspeedup, is an important quantum resource in quantum information processing and lies atthe heart of quantum computation. Based on the linear optics and cavity QED technolo-gies, we present physical schemes for preparing quantum multipartite entangled states.The experimental setup comprises simple linear optical elements, maximally and non-maximally entangled two-photon polarization states, and conventional photon detectors.In the detection process, the use of conventional photon detectors greatly decreases thehigh-quality requirements of detectors in realistic experiments.We investigate the phase matching problem in Grover quantum search algorithm byusing the method of mathematical calculation, and presentπ/3.61 phase search algorithm.In this algorithm, the success probability for searching is at least 94.11%.π/3.61 phasesearch algorithm overcomes the weakness that the success probability of getting correctresults usually decreases ?eetly with the increase of marked items when Grover quantumsearch algorithm is applied to search an unordered database. In the meantime, this workalso indicates that Grover quantum search algorithm is considerably robust to certainkinds of perturbations and is robust against modest noise in the initialization procedure; we present a scheme for implementing two-qubit Grover quantum search based on theatom-atom dipole-dipole interaction and the atom-cavity interaction in cavity QED. In thisscheme, all the two-qubit conditional phase operations required to achieve the two-qubitGrover quantum search can be implemented directly without performing any auxiliarysingle-qubit rotation operations. Moreover, the scheme is insensitive to both the cavitydecay and the thermal field with the assistance of a strong classical field.We present parity determination algorithm and quadratic residue algorithm basedon Grover quantum search algorithm. In the parity determination algorithm, the parity offunction f(x) can be determined by counting exactly the number of satisfying f(x) = -1.We discuss the up and low bounds of the computational complexity of this algorithm. Inthe quadratic residue algorithm, the cost of the algorithm mainly depends on the calcula-tions of quadratic residue modulo M and the number of iterations. In classical computer,it needs M/2 calculations for solving quadratic residue equation. While in quantum com-puter, it needs only O(M^1/2) steps with the success probability of 100%, which realizesquadratic speedup compared with classical computation.We present a method to measure directly the concurrence of an arbitrary two-qubitpure state system based on generalized Grover quantum search algorithm. We constructthe explicit generalized Grover quantum iteration operator and the concurrence can be cal-culated by applying quantum algorithm to two available copies of the bipartite system, anda final measurement on the auxiliary working qubits gives a better estimation of the con-currence. The implementation of the scheme would be an important step toward quantuminformation processing and more complex entanglement measure of finite-dimensionalquantum system with an arbitrary number of qubits. In the meantime, the scheme woulddirectly show the power of quantum computer.We present quantum circuits and physical protocols for implementing quantum dis-crete Fourier transformation based on cavity QED. Firstly, we present a physical protocolfor the implementation of N-bit quantum discrete Fourier transformation by using sin-gle atom-cavity interaction. In the protocol we design a tunable two-qubit conditionalphase gate by sending the atoms through a series of classical fields and cavities and bychanging the frequency of the cavity appropriately. All the one-bit and two-bit quantumgate operations can be achieved before the decoherence sets in, which are very powerfulfor the implementation of N-bit quantum Fourier transformation. Secondly, we present a physical protocol for implementing N-bit quantum discrete Fourier transformation byusing single two-atom-cavity interaction. In this protocol, we give a new quantum cir-cuit for implementing the quantum discrete Fourier transformation by using CNOT andSWCZ gate operations instead of the controlled-R_k and SWAP gate operations, togetherwith several one-qubit operatons. We also present the explicit atom-cavity interaction andatom-microwave interaction processes for the implementation of the quantum circuit. Inthe meantime, we present the detailed experimental procedure and analyze the experi-mental feasibility of the two protocols.