Abstract In this paper, we further verify the validity of the quantum partial adiabatic search algorithm which was initialized in the previous related works by revisiting its quantum circuit model. The main results got here are as follows. When considering implementing quantum partial adiabatic evolution on a quantum circuit, a correction is given for the time slice estimation for the first stage during this approximation in the previous related works, new evidence is provided for a time complexity cost $O(\sqrt{N}/M)$ O ( N / M ) of quantum partial adiabatic algorithm is impossible, and the correct time complexity $O(\sqrt{N/M})$ O ( N / M ) of it is emphasized once more according to its circuit correspondence, in which N is the total number of elements in the search problem of which M of them are the marked ones. The findings exposed are hopeful for revisiting quantum partial adiabatic evolution and its connection with the quantum circuit model.Abstract In this paper, we further verify the validity of the quantum partial adiabatic search algorithm which was initialized in the previous related works by revisiting its quantum circuit model. The main results got here are as follows. When considering implementing quantum partial adiabatic evolution on a quantum circuit, a correction is given for the time slice estimation for the first stage during this approximation in the previous related works, new evidence is provided for a time complexity cost $O(\sqrt{N}/M)$ O ( N / M ) of quantum partial adiabatic algorithm is impossible, and the correct time complexity $O(\sqrt{N/M})$ O ( N / M ) of it is emphasized once more according to its circuit correspondence, in which N is the total number of elements in the search problem of which M of them are the marked ones. The findings exposed are hopeful for revisiting quantum partial adiabatic evolution and its connection with the quantum circuit model.

EPJ Quantum TechnologyJul 25, 20247 citations

A quantum search algorithm based on partial adiabatic evolution

Yingyu Zhang, Heping Hu, Songfeng Lu

This paper presents and implements a specified partial adiabatic search algorithm on a quantum circuit. It studies the minimum energy gap between the first excited state and the ground state of the system Hamiltonian and it finds that, in the case of M = 1, the algorithm has the same performance as the local adiabatic algorithm. However, the algorithm evolves globally only within a small interval, which implies that it keeps the advantages of global adiabatic algorithms without losing the speedup of the local adiabatic search algorithm.This paper presents and implements a specified partial adiabatic search algorithm on a quantum circuit. It studies the minimum energy gap between the first excited state and the ground state of the system Hamiltonian and it finds that, in the case of M = 1, the algorithm has the same performance as the local adiabatic algorithm. However, the algorithm evolves globally only within a small interval, which implies that it keeps the advantages of global adiabatic algorithms without losing the speedup of the local adiabatic search algorithm.

Chinese Physics BApr 1, 201113 citations

Partial evolution based local adiabatic quantum search

Jie Sun, Songfeng Lu, Fang Liu +1 more

Recently, Zhang and Lu provided a quantum search algorithm based on partial adiabatic evolution, which beats the time bound of local adiabatic search when the number of marked items in the unsorted database is larger than one. Later, they found that the above two adiabatic search algorithms had the same time complexity when there is only one marked item in the database. In the present paper, following the idea of Roland and Cerf [Roland J and Cerf N J 2002 Phys. Rev. A 65 042308 ], if within the small symmetric evolution interval defined by Zhang et al., a local adiabatic evolution is performed instead of the original "global" one, this "new" algorithm exhibits slightly better performance, although they are progressively equivalent with M increasing. In addition, the proof of the optimality for this partial evolution based local adiabatic search when M = 1 is also presented. Two other special cases of the adiabatic algorithm obtained by appropriately tuning the evolution interval of partial adiabatic evolution based quantum search, which are found to have the same phenomenon above, are also discussed.Recently, Zhang and Lu provided a quantum search algorithm based on partial adiabatic evolution, which beats the time bound of local adiabatic search when the number of marked items in the unsorted database is larger than one. Later, they found that the above two adiabatic search algorithms had the same time complexity when there is only one marked item in the database. In the present paper, following the idea of Roland and Cerf [Roland J and Cerf N J 2002 Phys. Rev. A 65 042308 ], if within the small symmetric evolution interval defined by Zhang et al., a local adiabatic evolution is performed instead of the original "global" one, this "new" algorithm exhibits slightly better performance, although they are progressively equivalent with M increasing. In addition, the proof of the optimality for this partial evolution based local adiabatic search when M = 1 is also presented. Two other special cases of the adiabatic algorithm obtained by appropriately tuning the evolution interval of partial adiabatic evolution based quantum search, which are found to have the same phenomenon above, are also discussed.

Chinese Physics BJan 1, 201212 citations

Role of coherence in adiabatic search algorithms

Feng‐Guang Li, Wan‐Su Bao, Shuo Zhang +4 more

Physics Letters AJul 3, 20184 citations

O(\sqrt{N}/M)

O ( N / M ) of quantum partial adiabatic algorithm is impossible, and the correct time complexity

O(\sqrt{N/M})

O ( N / M ) of it is emphasized once more according to its circuit correspondence, in which N is the total number of elements in the search problem of which M of them are the marked ones. The findings exposed are hopeful for revisiting quantum partial adiabatic evolution and its connection with the quantum circuit model.