Postprocessing can speed up general quantum search algorithms

Abstract

A general quantum search algorithm aims to evolve a quantum system from a known source state $|s⟩$ to an unknown target state $|t⟩$. It uses a diffusion operator $D_s$ having source state as one of its eigenstates and $I_t$, where $I_{\psi }$ denotes the selective phase inversion of $|\psi ⟩$ state. It evolves $|s⟩$ to a particular state $|w⟩$, call it w-state, in $O(B/\alpha )$ time steps where $\alpha$ is $|⟨t|s⟩|$ and $B$ is a characteristic of the diffusion operator. Measuring the w-state gives the target state with the success probability of $O(1/B^2)$ and $O(B^2)$ applications of the algorithm can boost it from $O(1/B^2)$ to $O(1)$, making the total time complexity $O(B^3/\alpha )$. In the special case of Grover's algorithm, $D_s$ is $I_s$ and $B$ is very close to $1$. A more efficient way to boost the success probability is quantum amplitude amplification provided we can efficiently implement $I_w$. Such an efficient implementation is not known so far. In this paper, we present an efficient algorithm to approximate selective phase inversions of the unknown eigenstates of an operator using phase estimation algorithm. This algorithm is used to efficiently approximate $I_w$ which reduces the time complexity of general algorithm to $O(B/\alpha )$. Though $O(B/\alpha )$ algorithms are known to exist, our algorithm offers physical implementation advantages.

Accepted for publication in Physical Review A. arXiv admin note: substantial text overlap with arXiv:1210.4647

References in corpus (7)

• A Quantum Random Walk Search Algorithm
• Faster quantum walk algorithm for the two dimensional spatial search
• Adiabatic Quantum Computation with a 1D projector Hamiltonian
• General framework for quantum search algorithms
• Faster quantum searching with almost arbitrary operators
• Grover like Operator Using Only Single-Qubit Gates
• Quantum search algorithm tailored to clause satisfaction problems

Cited by in corpus (1)

• Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise