Narrow Results

Grover’s algorithm is a quantum query algorithm solving the unstructured search problem of size $N$ using $O(\sqrt{N})$ queries. It provides a significant speed-up over any classical algorithm [3].

The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [2, 6].

We study the behavior of Grover’s algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of marked elements in $O(\sqrt{N})$ queries.

We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of a limiting state ${\rho }_{lim}$.

A new approach to the classical limit of Grover’s algorithm is discussed by assuming a very rapid dephasing of a system between consecutive Grover’s unitary operations, which drives pure quantum states to decohered mixed states. One can identify a specific element among $N$ unsorted elements by a probability of the order of unity after $k\sim N$ steps of classical amplification, which is realized by a combination of Grover’s unitary operation and rapid dephasing, in contrast to $k\sim \pi \sqrt{N}/4$ steps in quantum mechanical amplification. The initial two-state system with enormously unbalanced existence probabilities, which is realized by a chosen specific state and a superposition of all the rest of the states among $N$ unsorted states, is crucial in the present analysis of classical amplification. This analysis illustrates Grover’s algorithm in extremely noisy circumstances. A similar increase from $k\sim \sqrt{N}$ to $k\sim N$ steps due to the loss of quantum coherence takes place in the analog model of Farhi and Gutmann where the entanglement does not play an obvious role. This supports a view that entanglement is crucial in quantum computation to describe quantum states by a set of qubits, but the actual speedup of the quantum computation is based on quantum coherence.

Among many classic heuristic search algorithms, the Grover quantum search algorithm (QSA) can play a role of secondary acceleration. Based on the properties of the two-qubit Grover QSA, a quantum dialogue (QD) protocol is proposed. In addition, our protocol also utilizes the unitary operations and single-particle measurements. The transmitted quantum state (except for the decoy state used for detection) can transmit two-bits of security information simultaneously. Theoretical analysis shows that the proposed protocol has high security.

In this work, we consider a family of sure-success quantum algorithms, which is grouped into even and odd members for solving a generalized Grover search problem. We prove the matching conditions for both groups and give the corresponding formulae for evaluating the iterations or oracle calls required in the search computation. We also present how to adjust the phase angles in the generalized Grover operator to ensure the sure-success if minimal oracle calls are demanded in the search.

Unsorted database search problem is an important science and engineering problem. We proposed quantum algorithm to solve the problem by dividing the database binarily and then use a probabilistic verifier algorithm to determine if the item is within one part of the divided database. We analyzed the computational complexity of this algorithm, and found that in general, the number of steps is proportional to that in the standard Grover algorithm. However in some cases, it is less than that of the Grover algorithm.

We present a quantum deletion algorithm that deletes a marked basis-state from an even superposition of all N basis-states. This algorithm uses only a single query and achieves exponential speed-up compared with classical analog where Θ(N) queries are required.

Quantum direct communications, including deterministic secure quantum communication and quantum secure direct communication protocol using two-qubit quantum search algorithm are proposed in this paper. Secret messages are encoded by two-qubit unitary operations and exchanged by the two communication parties directly. We discussed the security of the protocol under intercept-resend attack and individual attack. We found that the protocols are secure against eavesdropping attacks.