Grover's search algorithm is renowned for its dramatic speedup in solving many important scientific problems. The recently proposed Variational Quantum Search (VQS) algorithm has shown an exponential advantage over Grover's algorithm for up to 26 qubits. However, its advantage for larger numbers of qubits has not yet been proven. Here we show that the exponentially deep circuit required by Grover's algorithm can be replaced by a multi-controlled NOT gate together with either a single layer of Ry gates or two layers of circuits consisting of Hadamard and NOT gates, which is valid for any number of qubits greater than five. We prove that the VQS, with a single layer of Ry gates as its Ansatz, has near-perfect reachability in finding the good element of an arbitrarily large unstructured data set, and its reachability exponentially improves with the number of qubits, where the reachability is defined to quantify the ability of a given Ansatz to generate an optimal quantum state. Numerical studies further validate the excellent reachability of the VQS. Proving the near-perfect reachability of the VQS, with a depth-1 Ansatz, for any number of qubits completes an essential step in proving its exponential advantage over Grover's algorithm for any number of qubits, and the latter proving is significant as it means that the VQS can efficiently solve NP-complete problems.
翻译:Grover的搜索算法因其在解决许多重要的科学问题方面的迅猛加速而出名。最近提出的量子搜索算法(VQS)的变异式量子搜索算法(VQS)已经显示比Grover的算法具有指数性优势,最高可达度为26 qubits。然而,它对于数量更多的qubits的优势还没有被证明。在这里,我们表明,Grover的算法所需的指数性深路可被多控的NO门以及单层Ry门或由Hadadamard和NOT门组成的两层电路所取代。对于超过5倍的任何量子门都是有效的。我们证明,以单一层Ry门作为Ansaztr的算法,VQQS在寻找任意大型无结构数据集的良好元素方面几乎不易达,其可达性也随着QS的可达度的可达度而快速提高,对于VS的精确性可达度来说,其接近的精确性可达度是任何一步。