Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2004.11347

Multi-layer quantum search and inclusion of NP into BQP

Shan Jin, Xiaoting Wang, Li, Bo

Published Apr 23, 2020• 1 citation
arXivHTMLPDF

Abstract

In this work, we present a multi-layer quantum search method that generates an exponential speedup of the standard Grover's algorithm. As direct applications, any NP problems can be solved efficiently on a quantum circuit with only polynomial gate complexity. In particular, such multi-layer search can solve the factoring problem with an exponential speedup, providing an alternative to Shor's algorithm. Our results show that the exponential speedup of quantum circuits is ubiquitous, and Grover's search is much more powerful than that has been demonstrated. With no contradiction to the quadratic optimality of single-layer query complexity, the great potential of Grover's search is fully released by such multi-layer search design.

DOI
10.48550/arxiv.2004.11347

Related papers

Variational Quantum Search with Exponential Speedup

Junpeng Zhan

Abstract With powerful quantum computers already built1,2, we need more efficient quantum algorithms to achieve quantum supremacy over classical computers in the noisy intermediate-scale quantum (NISQ) era2,3. Grover's search algorithm4,5 and its generalization, quantum amplitude amplification6, provide quadratic speedup in solving many important scientific problems7. However, they still have exponential time complexity as the depths of their quantum circuits increase exponentially with the number of qubits6,7. To address this problem, we propose a new algorithm, Variational Quantum Search (VQS), which is based on the celebrated variational quantum algorithms8,9 and includes a parameterized quantum circuit, known as Ansatz. We show that a depth-10 Ansatz can amplify the total probability of k (k≥1) good elements, out of 2n elements represented by n+1 qubits, from k/2n to nearly 1, as verified for n up to 26, and that the maximum depth of quantum circuits in the VQS increases linearly with the number of qubits. We demonstrate that a depth-56 circuit in VQS can replace a depth-270,989 circuit in Grover's algorithm, and thus VQS is more suitable for NISQ computers. We envisage our VQS could exponentially speed up the solutions to many important problems, including the NP-complete problems, which is widely considered impossible.

•Dec 20, 2022•0 citations

Near-perfect Reachability of Variational Quantum Search with Depth-1 Ansatz

Junpeng Zhan

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.

arXiv:2301.13224•Jan 30, 2023•4 citations

Evolution of Quantum Computing Based on Grover's Search Algorithm

Prakhar Shrivastava, Kapil Kumar Soni, Akhtar Rasool

Quantum computing introduces an efficient way for unfolding complex problems on computing systems. It uses concept of superposition and entanglement, & hence supports intrinsic parallelism for obtaining the speedup in context of time over classical computing. Quantum algorithms can be efficiently implemented over quantum computing system. Most popular quantum algorithms like Grover's and Shor's provide a great foundation to specifically design the algorithms. These algorithms work on improving the lower runtime bounds of classical algorithms. Grover's algorithm exhibits a quadratic polynomial speedup while searching an element among `N' elements unstructured database. The algorithmic strategy can be applied over various computer science related applications and some important are being considered in this article i.e. pattern matching, data mining and machine learning. This article explores quantum fundamentals; history based evolution followed by Grover's search algorithm in detail with cascading advantages, limitations & applications and also finally concludes with the significance of quantum computing & quantum algorithmic domains.

International Conference on Computing, Communication and Networking Technologies (ICCCNT)•Jul 1, 2019•22 citations

The Effective Solving of the Tasks from NP by a Quantum Computer

S. S. Sysoev

The new model of quantum computation is proposed, for which an effective algorithm of solving any task in NP is described. The work is based and inspired be the Grover's algorithm for solving NP-tasks with quadratic speedup compared to the classical computation model. The provided model and algorithm exhibit the exponential speedup over that described by Grover.

arXiv:1401.6030•Jan 23, 2014•2 citations

Exponential convergence dynamics in Grover's search algorithm

Samuel Cogan, Jonathan Raghoonanan, Tim Byrnes

Grover's search algorithm is the cornerstone of many applications of quantum computing, providing a quadratic speed-up over classical methods. One limitation of the algorithm is that it requires knowledge of the number of solutions to obtain an optimal success probability, due to the oscillatory dynamics between the initial and solution states (the ``souffl{é} problem''). While various methods have been proposed to solve this problem, each has its drawbacks in terms of inefficiency or sensitivity to control errors. Here, we modify Grover's algorithm so that, for suitably chosen parameters, the usual oscillatory dynamics are replaced by an approximately exponential convergence into the solution subspace. The basic idea is to couple the solution states to an engineered ancilla reservoir such that the initial state is nonreflectively absorbed. Trotterizing the continuous algorithm yields a quantum circuit that gives equivalent performance, while preserving the same quadratic quantum speedup as the original algorithm.

quant-pharXiv:2512.15100•Quantum Science and Technology•Dec 18, 2025•0 citations

Hardware Efficient Quantum Search Algorithm

Ji Liu, Huiyang Zhou

Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.

arXiv:2103.14196•Mar 26, 2021•15 citations
In this work, we present a multi-layer quantum search method that generates an exponential speedup of the standard Grover's algorithm. As direct applications, any NP problems can be solved efficiently on a quantum circuit with only polynomial gate complexity. In particular, such multi-layer search can solve the factoring problem with an exponential speedup, providing an alternative to Shor's algorithm. Our results show that the exponential speedup of quantum circuits is ubiquitous, and Grover's search is much more powerful than that has been demonstrated. With no contradiction to the quadratic optimality of single-layer query complexity, the great potential of Grover's search is fully released by such multi-layer search design.
Abstract With powerful quantum computers already built1,2, we need more efficient quantum algorithms to achieve quantum supremacy over classical computers in the noisy intermediate-scale quantum (NISQ) era2,3. Grover's search algorithm4,5 and its generalization, quantum amplitude amplification6, provide quadratic speedup in solving many important scientific problems7. However, they still have exponential time complexity as the depths of their quantum circuits increase exponentially with the number of qubits6,7. To address this problem, we propose a new algorithm, Variational Quantum Search (VQS), which is based on the celebrated variational quantum algorithms8,9 and includes a parameterized quantum circuit, known as Ansatz. We show that a depth-10 Ansatz can amplify the total probability of k (k≥1) good elements, out of 2n elements represented by n+1 qubits, from k/2n to nearly 1, as verified for n up to 26, and that the maximum depth of quantum circuits in the VQS increases linearly with the number of qubits. We demonstrate that a depth-56 circuit in VQS can replace a depth-270,989 circuit in Grover's algorithm, and thus VQS is more suitable for NISQ computers. We envisage our VQS could exponentially speed up the solutions to many important problems, including the NP-complete problems, which is widely considered impossible.
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.
Quantum computing introduces an efficient way for unfolding complex problems on computing systems. It uses concept of superposition and entanglement, & hence supports intrinsic parallelism for obtaining the speedup in context of time over classical computing. Quantum algorithms can be efficiently implemented over quantum computing system. Most popular quantum algorithms like Grover's and Shor's provide a great foundation to specifically design the algorithms. These algorithms work on improving the lower runtime bounds of classical algorithms. Grover's algorithm exhibits a quadratic polynomial speedup while searching an element among `N' elements unstructured database. The algorithmic strategy can be applied over various computer science related applications and some important are being considered in this article i.e. pattern matching, data mining and machine learning. This article explores quantum fundamentals; history based evolution followed by Grover's search algorithm in detail with cascading advantages, limitations & applications and also finally concludes with the significance of quantum computing & quantum algorithmic domains.
Grover's search algorithm is the cornerstone of many applications of quantum computing, providing a quadratic speed-up over classical methods. One limitation of the algorithm is that it requires knowledge of the number of solutions to obtain an optimal success probability, due to the oscillatory dynamics between the initial and solution states (the ``souffl{é} problem''). While various methods have been proposed to solve this problem, each has its drawbacks in terms of inefficiency or sensitivity to control errors. Here, we modify Grover's algorithm so that, for suitably chosen parameters, the usual oscillatory dynamics are replaced by an approximately exponential convergence into the solution subspace. The basic idea is to couple the solution states to an engineered ancilla reservoir such that the initial state is nonreflectively absorbed. Trotterizing the continuous algorithm yields a quantum circuit that gives equivalent performance, while preserving the same quadratic quantum speedup as the original algorithm.
Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.