The standard quantum search algorithm lacks a feature, enjoyed by many classical algorithms, of having a fixed-point, i.e. a monotonic convergence towards the solution. Here we present two variations of the quantum search algorithm, which get around this limitation. The first replaces selective inversions in the algorithm by selective phase shifts of
3π. The second controls the selective inversion operations using two ancilla qubits, and irreversible measurement operations on the ancilla qubits drive the starting state towards the target state. Using
q oracle queries, these variations reduce the probability of finding a non-target state from
ε to
ε2q+1, which is asymptotically optimal. Similar ideas can lead to robust quantum algorithms, and provide conceptually new schemes for error correction.
One iterative in Grover's original quantum search algorithm consists of two Hadamard–Walsh transformations, a selective amplitude inversion and a diffusion amplitude inversion. We concentrate on the relation among the probability of success of the algorithm, the phase shifts, the number of target items and the number of iterations via replacing the two amplitude inversions by phase shifts of an arbitrary ϕ = ϕ(0 ⩽ ϕ, ϕ ⩽ 2π). Then, according to the relation we find out the optimal phase shifts when the number of iterations is given. We present a new quantum search algorithm based on the optimal phase shifts of 1.018 after 0.5π/ iterations. The new algorithm can obtain either a single target item or multiple target items in the search space with the probability of success at least 93.43%.
The standard quantum search lacks a feature, enjoyed by many classical algorithms, of having a fixed point, i.e. monotonic convergence towards the solution. Recently a fixed point quantum search algorithm has been discovered, referred to as the Phase-\pi/3 search algorithm, which gets around this limitation. While searching a database for a target state, this algorithm reduces the error probability from \epsilon to \epsilon^{2q+1} using q oracle queries, which has since been proved to be asymptotically optimal. A different algorithm is presented here, which has the same worst-case behavior as the Phase-\pi/3 search algorithm but much better average-case behavior. Furthermore the new algorithm gives \epsilon^{2q+1} convergence for all integral q, whereas the Phase-\pi/3 search algorithm requires q to be (3^{n}-1)/2 with n a positive integer. In the new algorithm, the operations are controlled by two ancilla qubits, and fixed point behavior is achieved by irreversible measurement operations applied to these ancillas. It is an example of how measurement can allow us to bypass some restrictions imposed by unitarity on quantum computing.
A quantum algorithm is a set of instructions for a quantum computer, however, unlike algorithms in classical computer science their results cannot be guaranteed. Quantum search algorithm can be described as the rotation of state vectors in a Hilbert space. The state vectors uniformly rotate by iterative sequences until they hit the target position. To optimize the algorithm, it is necessary to have the precise knowledge about some parameters like the number of target positions and total number of states. Here, we demonstrate the implementation of optimal fixed-point quantum search algorithm in IBMQ simulator developed by IBM corporation. We perform the search algorithm for one-iteration for two, three, four and five qubit systems and confirm the accuracy of our results through histogram.
The standard quantum search lacks a feature, enjoyed by many classical algorithms, of having a fixed point, i.e. monotonic convergence towards the solution. Recently a fixed point quantum search algorithm has been discovered, referred to as the Phase-
π/3 search algorithm, which gets around this limitation. While searching a database for a target state, this algorithm reduces the error probability from
ε to
ε2q+1 using
q oracle queries, which has since been proved to be asymptotically optimal. A different algorithm is presented here, which has the same worst-case behavior as the Phase-
π/3 search algorithm but much better average-case behavior. Furthermore the new algorithm gives
ε2q+1 convergence for all integral
q, whereas the Phase-
π/3 search algorithm requires
q to be
(3n−1)/2 with
n a positive integer. In the new algorithm, the operations are controlled by two ancilla qubits, and fixed point behavior is achieved by irreversible measurement operations applied to these ancillas. It is an example of how measurement can allow us to bypass some restrictions imposed by unitarity on quantum computing.
Quantum search algorithm can be described as the rotation of state vectors in a Hilbert space. The state vectors uniformly rotate by iterative sequences until they hit the target position. To optimize the algorithm, it is necessary to have the precise knowledge about some parameters like the number of target positions. Here we demonstrate the implementation of optimal fixed-point quantum search (OFPQS) algorithm in a five-qubit quantum computer developed by IBM Corporation. We perform the OFPQS algorithm for one and two-iterations and confirm the accuracy of our results by state tomography process.