Abstract We report better-than-classical success probabilities for a complete Grover quantum search algorithm on the largest scale demonstrated to date, of up to five qubits, using two different IBM platforms. This is enabled by error suppression via robust dynamical decoupling. Further improvements arise after the use of measurement error mitigation, but the latter is insufficient by itself for achieving better-than-classical performance. For two qubits, we demonstrate a 99.5% success probability via the use of the [[4, 2, 2]] quantum error-detection (QED) code. This constitutes a demonstration of quantum algorithmic breakeven via QED. Along the way, we introduce algorithmic error tomography (AET), a method that provides a holistic view of the errors accumulated throughout an entire quantum algorithm, filtered via the errors detected by the QED code used to encode the circuit. We demonstrate that AET provides a stringent test of an error model based on a combination of amplitude damping, dephasing, and depolarization.
Abstract We report better-than-classical success probabilities for a complete Grover quantum search algorithm on the largest scale demonstrated to date, of up to five qubits, using two different IBM platforms. This is enabled by error suppression via robust dynamical decoupling. Further improvements arise after the use of measurement error mitigation, but the latter is insufficient by itself for achieving better-than-classical performance. For two qubits, we demonstrate a 99.5% success probability via the use of the [[4, 2, 2]] quantum error-detection (QED) code. This constitutes a demonstration of quantum algorithmic breakeven via QED. Along the way, we introduce algorithmic error tomography (AET), a method that provides a holistic view of the errors accumulated throughout an entire quantum algorithm, filtered via the errors detected by the QED code used to encode the circuit. We demonstrate that AET provides a stringent test of an error model based on a combination of amplitude damping, dephasing, and depolarization.
Quantum error detection (QED) offers a promising pathway to fault tolerance in near-term quantum devices by balancing error suppression with minimal resource overhead. However, its practical utility hinges on optimizing design parameters-such as syndrome measurement frequency-to avoid diminishing returns from detection overhead. In this work, we present a comprehensive framework for fault-tolerant compilation and simulation of quantum algorithms using [[n, n-2, 2]] codes, which enable low-qubit-overhead error detection and a simple nearly fault-tolerant universal set of operations. We demonstrate and analyze our pipeline with a purely statistical interpretation and through the implementation of Grover's search algorithm. Our results are used to answer the question is quantum error detection a worthwhile avenue for early-term fault tolerance, and if so how can we get the most out of it? Simulations under the circuit-level noise model reveal that finding optimal syndrome schedules improves algorithm success probabilities by an average of 6.7x but eventual statistical limits from post-selection in noisy/resource-limited regimes constrain scalability. Furthermore, we propose a simple data-driven approach to predict fault tolerant compilation parameters, such as optimal syndrome schedules, and expected fault tolerant performance gains based on circuit and noise features. These results provide actionable guidelines for implementing QED in early-term quantum experiments and underscore its role as a pragmatic, constant-overhead error mitigation layer for shallow algorithms. To aid in further research, we release all simulation data computed for this work and provide an experimental QED compiler at https://codeqraft.xyz/qed.
Abstract When quantum computing becomes a wide-spread commercial reality, Quantum Search Algorithms (QSA) and especially Grover’s QSA will inevitably be one of their main applications, constituting their cornerstone. Most of the literature assumes that the quantum circuits are free from decoherence. Practically, decoherence will remain unavoidable as is the Gaussian noise of classic circuits imposed by the Brownian motion of electrons, hence it may have to be mitigated. In this contribution, we investigate the effect of quantum noise on the performance of QSAs, in terms of their success probability as a function of the database size to be searched, when decoherence is modelled by depolarizing channels’ deleterious effects imposed on the quantum gates. Moreover, we employ quantum error correction codes for limiting the effects of quantum noise and for correcting quantum flips. More specifically, we demonstrate that, when we search for a single solution in a database having 4096 entries using Grover’s QSA at an aggressive depolarizing probability of 10−3, the success probability of the search is 0.22 when no quantum coding is used, which is improved to 0.96 when Steane’s quantum error correction code is employed. Finally, apart from Steane’s code, the employment of Quantum Bose-Chaudhuri-Hocquenghem (QBCH) codes is also considered.
Abstract Quantum search algorithm (also known as Grover's algorithm) lays the foundation for many other quantum algorithms. Although it is very simple, its implementation is limited on noisy intermediate-scale quantum (NISQ) processors. Grover's algorithm was designed without considering the physical resources, such as depth, in the real implementations. Therefore, Grover's algorithm can be improved for NISQ devices. In this paper, we demonstrate how to implement quantum search algorithms better on NISQ devices. We present detailed benchmarks of the five-qubit quantum search algorithm on different quantum processors, including IBMQ, IonQ, and Honeywell quantum devices. We report the highest success probability of the five-qubit search algorithm compared to previous works. Our results show that designing the error-aware quantum search algorithms is possible, which can maximally harness the power of NISQ computers.
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.
Grover’s quantum search algorithm delivers quadratic speedup over classical counterparts for finding an item in unstructured database. But the accuracy of the algorithm degrades as the number of qubits are increased. Noises of various types affect the accuracy of the Grover’s algorithm. The imperfect measurement on the qubit results in measurement errors appears to be one of the factors which limit the scalability of near-term quantum devices/algorithms. This paper is focused on the implementation of measurement error mitigation technique on Grover’s algorithm up to 4-qubits. The measurement error mitigation model for Grover’s algorithm is developed and implemented on the real-time quantum computer. The accuracy of Grover’s algorithm up to 4-qubits with and without measurement errors is evaluated and compared. The results indicate that measurement error mitigation technique mitigates the measurement errors of the Grover’s algorithm and improves its accuracy.
The promise of quantum computing is closer to reality today than ever before, thanks to rapid progress in the development of quantum hardware. Even as qubit lifetimes and gate fidelities continue to improve, realizing robust, fault-tolerant quantum computers is contingent upon the successful implementation of quantum error correction (QEC). Conventional QEC schemes have rather high resource overheads and low threshold requirements, making them challenging to implement on present day hardware. Here, we use a recently developed noise-adapted 3-qubit QEC scheme to demonstrate break-even performance against native amplitude-damping (AD) noise on IBM quantum hardware. We use variational quantum circuits to construct hardware-efficient encoding and decoding circuits. This scheme is probabilistic due to the non-unitary nature of the recovery operators, which are implemented via the block-encoding technique. We demonstrate logical qubit lifetimes exceeding those of the physical qubits by performing multiple rounds of QEC. To further protect the qubits from dephasing due to crosstalk, we incorporate dynamical decoupling into our noise-adapted QEC scheme in a seamless fashion. To account for the post-selection overhead, we define a measure of gain, that allows for faithful performance benchmarking of the protocol. Our analysis suggests that the performance of our protocol is limited primarily by the measurement readout fidelity, and is bound to improve with successive generations of quantum processors.