Grover search is a renowned quantum search algorithm that leverages quantum superposition to find a marked item with quadratic speedup. However, when implemented on Noisy Intermediate-scale Quantum (NISQ) hardware, the required repeated iterations of the oracle and diffusion operators increase exponentially with the number of qubits, resulting in significant noise accumulation. To address this, we propose a hybrid quantum-classical architecture that replaces quantum iterations with updates from a classical optimizer. This optimizer minimizes the expectation value of an oracle Hamiltonian with respect to a parameterized quantum state representing the target bit string. Our parameterized quantum circuit is much shallower than Grover search circuit, and we found that it outperforms Grover search on noisy simulators and NISQ hardware. When the number of qubits is greater than 5, our approach still maintains usable success probability, while the success probability of Grover search is at the same level as random guessing.
Grover search is a renowned quantum search algorithm that leverages quantum superposition to find a marked item with quadratic speedup. However, when implemented on Noisy Intermediate-scale Quantum (NISQ) hardware, the required repeated iterations of the oracle and diffusion operators increase exponentially with the number of qubits, resulting in significant noise accumulation. To address this, we propose a hybrid quantum-classical architecture that replaces quantum iterations with updates from a classical optimizer. This optimizer minimizes the expectation value of an oracle Hamiltonian with respect to a parameterized quantum state representing the target bit string. Our parameterized quantum circuit is much shallower than Grover search circuit, and we found that it outperforms Grover search on noisy simulators and NISQ hardware. When the number of qubits is greater than 5, our approach still maintains usable success probability, while the success probability of Grover search is at the same level as random guessing.
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.
Classical database join operations are a significant performance bottleneck in data-intensive applications, typically requiring quadratic time proportional to the size of the input. Quantum search algorithms, such as Grover’s algorithm, promise asymptotic speedups for unstructured search and can be adapted to accelerate equality-based joins. In this paper, we present a systematic simulation study of a Grover-based quantum join primitive and a hybrid classical-quantum join scheme, comparing them with a baseline classical nested-loop join. Parameterised Grover circuits have been implemented for marked-item search, together with resource estimation (qubit count, circuit depth, and gate counts), using the Qiskit Aer simulator. The classical join is modelled as a nested-loop equality join over two arrays, while the hybrid scheme uses a classical Bloom filter to reduce the candidate space, followed by a Grover search over the remaining items. To approximate near term hardware, we incorporate depolarizing gate noise and readout noise via Aer noise models and investigate two mitigation techniques: readout error calibration and zero noise extrapolation. Our simulations, conducted in a Python environment without GPU acceleration, demonstrate that the Grover based and hybrid joins exhibit the expected sub-quadratic scaling in runtime compared to the classical nested-loop join for problem sizes up to N = 215. We additionally observe that realistic noise significantly degrades the raw success probability of the quantum join, while combining readout mitigation with zero noise extrapolation partially restores accuracy. These results provide a resource-aware and noise-aware baseline for evaluating quantum-accelerated joins on future fault-tolerant or high-fidelity noisy intermediate-scale quantum (NISQ) devices.
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 quantum search algorithm provides a proven quadratic speedup over classical linear search for unstructured databases. While its theoretical advantage is well established, experimental validation on real noisy intermediate-scale quantum (NISQ) hardware remains limited by noise, decoherence, and hardware constraints. In this work, we present an experimental comparison between classical linear search and Grover's quantum search algorithm executed on IBM Quantum real superconducting hardware using Qiskit Runtime. A four-qubit implementation corresponding to a 16-element search space is evaluated across multiple experimental runs. The results demonstrate consistent amplitude amplification, achieving an average success probability of 54.25% and an amplification factor of 8.68× over random guessing. Although classical execution remains faster in wall-clock time due to quantum hardware overhead, the experiment empirically validates the algorithmic advantage of Grover's search and quantifies the performance gap between ideal and real quantum processors in the NISQ era.
The Grover algorithm is a fundamental quantum algorithm that achieves a quadratic speedup for unstructured search problems, requiring O(√N) queries instead of O(N) classically. It works by repeatedly applying an oracle and a diffusion operator to amplify the probability of marked states. This advantage makes it relevant to cryptography, optimization, constraint satisfaction, and as a general primitive via amplitude amplification in areas like quantum machine learning and simulation. However, practical implementations are severely constrained by current Noisy Intermediate Scale Qualtum machines with limited coherence, deep oracle circuits and lack of scalable QRAM, restricting demonstrations to small-scale experiments with reproducibility challenges.
The hardware noise and drift, combined with the fragility of stationary hybrid algorithms like the variational quantum eigensolver (VQE), limit the usefulness of noise quantum advantage accessed through Noisy intermediate-scale quantum (NISQ) processors, but allow near-term quantum advantage. In this paper, a Hybrid Quantum-Classical Adaptive Intelligence Framework is suggested, which bridges the gap between quantum hardware, a parameterized quantum circuit, explicit error-mitigation routines, and a controller trained through learning. The quantum subsystem prepares variational states and calculates the expectation values of the problem Hamiltonian, and an AI/ML model approximates an online noise probability signal and moves an optimizer based on reinforcement learning (RL). The RL policy chooses the parameter updates and enables mitigation measures depending on noise-sensitive state functions, such as energy, gradient norm, and estimated noise level. It was demonstrated experimentally using a simulated NISQ-style molecular Hamiltonian that the adaptive controller can reduce the error in the absolute ground state of the system by about 52.8 percent versus a standard static VQE baseline using the same ansatz. The integrated classifier that drives the process of mitigation is accurate with 97 percent accuracy, 100 percent precision, 92 percent recall, 95.9 F1-score, and 99.5 AUC, which shows reliable decision-making with minimal false alarms. All these findings indicate that the close-knit quantum-classical adaptivity can significantly contribute to the robustness and accuracy of VQE-like workloads on NISQ and serve as a scalable template to design noise-aware hybrid algorithms in the future.