Geometrical Picture for Quantum Searching

Lian-Jie Zhao, Yansong Li, Liang Hao +2 more

Wenliang Jin

"For an initial uniform superposition over all pos- sible computational basis states, we explore the perfor- mance of Grover’s search algorithm geometrically when imposing a perturbation on the Walsh-Hadamard trans- formation contained in the Grover iteration. We give the geometric picture to visualize the quantum search process in the three-dimensional space and show that Grover’s search algorithm can work well with an appropriately chosen per- turbation. Thereby we corroborate Grover’s conclusion that if the perturbation is small, then it will have little impact on the implementation of this algorithm. We also prove that Grover’s path cannot achieve a geodesic under a perturba- tion of the Fubini-Study metric."

Lov K. Grover

Gui Lu Long, Chang Cun Tu, Yan Li +2 more

An SO (3) picture of the generalized Grover quantum searching algorithm is constructed. In this picture, various aspects of quantum searching, the phase matching requirement in particular, are easily understood. It also offers a simple quantitative description of quantum searching. Exact formulae for the rotation angle and rotational axis are given. The probability of finding the marked state is just the projection of the state vector onto the z -axis in this picture. Applications of the picture to the standard Grover algorithm and to a generalized quantum search algorithm with arbitrary phase rotations are given.

Thomas G. Wong

Shelby Kimmel, Cedric Yen-Yu Lin, Han-Hsuan Lin

While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal.