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.     

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.     

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.     

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.     

Quantum computation based on magic-angle-spinning solid state nuclear magnetic resonance spectroscopy

Magic-angle spinning (MAS) solid state nuclear magnetic resonance (NMR) spectroscopy is shown to be a promising technique for implementing quantum computing. The theory underlying the principles of quantum computing with nuclear spin systems undergoing MAS is formulated in the framework of formalized quantum Floquet theory. The procedures for realizing state labeling, state transformation and coherence selection in Floquet space are given. It suggests that by this method, the largest number of qubits can easily surpass that achievable with other techniques. Unlike other modalities proposed for quantum computing, this method enables one to adjust the dimension of the working state space, meaning the number of qubits can be readily varied. The universality of quantum computing in Floquet space with solid state NMR is discussed and a demonstrative experimental implementation of Grover's search is given. Received 19 April 2001     

量子相关词汇搜索

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

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.     

Numerical simulation of NQR/NMR: Applications in quantum computing

A numerical simulation program able to simulate nuclear quadrupole resonance (NQR) as well as nuclear magnetic resonance (NMR) experiments is presented, written using the Mathematica package, aiming especially applications in quantum computing. The program makes use of the interaction picture to compute the effect of the relevant nuclear spin interactions, without any assumption about the relative size of each interaction. This makes the program flexible and versatile, being useful in a wide range of experimental situations, going from NQR (at zero or under small applied magnetic field) to high-field NMR experiments. Some conditions specifically required for quantum computing applications are implemented in the program, such as the possibility of use of elliptically polarized radiofrequency and the inclusion of first- and second-order terms in the average Hamiltonian expansion. A number of examples dealing with simple NQR and quadrupole-perturbed NMR experiments are presented, along with the proposal of experiments to create quantum pseudopure states and logic gates using NQR. The program and the various application examples are freely available through the link http://www.profanderson.net/files/nmr_nqr.php.     

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.     

Kicked-rotor quantum resonances in position space: application to situations of experimental interest

We discuss a model for quantum computing with initially mixed states. Although such a computer is known to be less powerful than a quantum computer operating with pure (entangled) states, it may efficiently solve some problems for which no efficient classical algorithms are known. We suggest a new implementation of quantum computation with initially mixed states in which an algorithm realization is achieved by means of optimal basis independent transformations of qubits.     

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.     

Concepts of spin quantum computing

Quantum computing is based on two-state quantum systems called qubits. Recent proposals for quantum computing included nuclear spin 1/2 as qubits and implementations of several quantum algorithms were demonstrated by applying liquid-state NMR. Here I want to lay out some of the concepts of spin quantum computing including nuclear and electron spins. This article is intended to serve a dual purpose. It should on one hand introduce the reader who is not familiar with magnetic resonance to the spin quantum computing terminology and the concepts of pulsed magnetic resonance. At the same time I want to introduce the NMR expert to the recent developments in quantum computing.     

Spectrum of the volume operator in quantum gravity

The volume operator is an important kinematical quantity in the non-perturbative approach to four-dimensional quantum gravity in the connection formulation. We give a general algorithm for computing its spectrum when acting on four-valent spin network states, evaluate some of the eigenvalue formulae explicitly, and discuss the role played by the Mandelstam constraints.     

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     

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.     

Virtual parallel computing and a search algorithm using matrix product States

We propose a form of parallel computing on classical computers that is based on matrix product states. The virtual parallelization is accomplished by representing bits with matrices and by evolving these matrices from an initial product state that encodes multiple inputs. Matrix evolution follows from the sequential application of gates, as in a logical circuit. The action by classical probabilistic one-bit and deterministic two-bit gates such as NAND are implemented in terms of matrix operations and, as opposed to quantum computing, it is possible to copy bits. We present a way to explore this method of computation to solve search problems and count the number of solutions. We argue that if the classical computational cost of testing solutions (witnesses) requires less than O(n^{2}) local two-bit gates acting on n bits, the search problem can be fully solved in subexponential time. Therefore, for this restricted type of search problem, the virtual parallelization scheme is faster than Grover's quantum algorithm.     

Programmable networks for quantum algorithms

The implementation of a quantum computer requires the realization of a large number of N-qubit unitary operations which represent the possible oracles or which are part of the quantum algorithm. Until now there have been no standard ways to uniformly generate whole classes of N-qubit gates. We develop a method to generate arbitrary controlled phase-shift operations with a single network of one-qubit and two-qubit operations. This kind of network can be adapted to various physical implementations of quantum computing and is suitable to realize the Deutsch-Jozsa algorithm as well as Grover's search algorithm.     

Spin manipulation in semiconductor quantum dots qubit

Thirty years of effort in semiconductor quantum dots has resulted in significant developments in the control of spin quantum bits(qubits). The natural two-energy level of spin states provides a path toward quantum information processing. In particular, the experimental implementation of spin control with high fidelity provides the possibility of realizing quantum computing. In this review, we will discuss the basic elements of spin qubits in semiconductor quantum dots and summarize some important experiments that have demonstrated the direct manipulation of spin states with an applied electric field and/or magnetic field. The results of recent experiments on spin qubits reveal a bright future for quantum information processing.     

利用仲氢诱导极化技术实现 Deutsch算法

核磁共振系统是实现量子计算的有效物理体系之一．但是随着量子位数的不断增加,运用核磁共振技术实现计算任务存在明显的局限性,原因之一是量子计算的初始态-赝纯态,随着量子位数的增加,信号指数性的衰减,量子位数越多制备赝纯态所需的脉冲序列越复杂,越不容易实现,不利于量子位数的扩展;另外,由于核磁共振中制备的赝纯态实际上也是一种混合态,用于实现量子信息任务时存在一定的争议．该文介绍的利用仲氢诱导极化技术(PHIP)制备出的实验初态,能够解决初态处于混合态的问题,并且信号强度显著增强,作者利用此态实现了 ALTADENA 条件下的两量子位的 Deutsch-Jozsa 量子算法和 PASADENA 条件下的三量子位的Deutsch-Like 量子算法．