Reachability deficit of variational Grover search

Li，Xiao Wei1; Zhang，Xiao Ming2,3; Cheng，Bin2,4; Yung，Man Hong1,5,6

2024

10.1103/PhysRevA.109.012414

Physical Review A   影响因子和分区

2469-9926

2469-9934

The quantum approximate optimization algorithm (QAOA) is promising for achieving quantum computational advantage with near-term quantum devices. It was numerically shown that the QAOA cost functions exhibit a phenomenon called reachability deficit (RD), where the success probability cannot reach unity until the circuit depth exceeds a certain critical value. However, an in-depth theoretical understanding of RD remains lacking. Here we focus on a variational variant of Grover search on multiple marked solutions as a prototype for analyzing the RD problem, where we further relax the criterion of reachability by tolerating a certain probability of failure. Specifically, we obtain a general analytical expression relating the critical depth of the quantum circuit to the solution density. In the dilute limit, the critical depth is consistent with the Grover bound, exhibiting a robust quadratic scaling that is insensitive to the failure probability. Moreover, we also find that the projective mixing Hamiltonian performs significantly better than the traditional mixing Hamiltonian in the QAOA, although it is less favorable in terms of physical implementation. However, by taking into account two-body interactions in the mixing Hamiltonian, the performance becomes on par with the projective mixing Hamiltonian at the cost of O(n2) additional terms. These results represent a simplified but insightful model of the QAOA, fully addressing the dependence of required circuit depth over the ground-state degeneracy.

SCI ; EI

英语

第一

PHYSICS

2-s2.0-85182279482

Scopus

1.Shenzhen Institute for Quantum Science and Engineering,Southern University of Science and Technology,Shenzhen,518055,China
2.Department of Physics,Southern University of Science and Technology,Shenzhen,518055,China
3.Center on Frontiers of Computing Studies,Peking University,Beijing,100871,China
4.Centre for Quantum Software and Information,Faculty of Engineering and Information Technology,University of Technology,Sydney,2007,Australia
5.Guangdong Provincial Key Laboratory of Quantum Science and Engineering,Southern University of Science and Technology,Shenzhen,518055,China
6.Shenzhen Key Laboratory of Quantum Science and Engineering,Southern University of Science and Technology,Shenzhen,518055,China

Li，Xiao Wei,Zhang，Xiao Ming,Cheng，Bin,et al. Reachability deficit of variational Grover search[J]. Physical Review A,2024,109(1).

Li，Xiao Wei,Zhang，Xiao Ming,Cheng，Bin,&Yung，Man Hong.(2024).Reachability deficit of variational Grover search.Physical Review A,109(1).

Li，Xiao Wei,et al."Reachability deficit of variational Grover search".Physical Review A 109.1(2024).