We consider Grover's search algorithm on a model quantum computer implemented on a chain of four or five nuclear spins with first- and second-neighbour Ising interactions. Noise is introduced into the system in terms of random fluctuations of the external fields. By averaging over many repetitions of the algorithm, the output state becomes effectively a mixed state. We study its overlap with the nominal output state of the algorithm, which is called the fidelity. We analyse the behaviour of the fidelity as a function of the noise intensity for static and random noise on either the Larmor frequencies or the Rabi frequency, and we compare our results to theoretical predictions and numerical simulations which are based on more abstract quantum computer models.
We implement Grover's quantum search algorithm on a nuclear spin-chain quantum computer, taking Ising-type interactions between nearest and second-nearest neighbours into account. The performance of this implementation is studied by numerical simulations with four spins. We determine the temporal behaviour of the fidelity during the algorithm, and we compute the final fidelity as a function of the Rabi frequency. For the latter, we obtain pronounced maxima at frequencies which fulfil the condition of the 2π k -method with respect to the second-nearest- neighbour interactions.
Many existing static analysis algorithms suffer from cubic bottlenecks because of the need to compute a dynamic transitive closure (DTC). For the first time, this article studies the quantum speedups on searching subtasks in DTC-based static analysis algorithms using quantum search (e.g., Grover’s algorithm). We first introduce our oracle implementation in Grover’s algorithm for DTC-based static analysis and illustrate our quantum search subroutine. Then, we take two typical DTC-based analysis algorithms: context-free-language reachability and set constraint-based analysis, and show that our quantum approach can reduce the time complexity of these two algorithms to truly subcubic ( O(N2Npolylog(N)) ), yielding better results than the upper bound ( O ( N 3 /log N )) of existing classical algorithms. Finally, we conducted a classical simulation of Grover’s search to validate our theoretical approach, due to the current quantum hardware limitation of lacking a practical, large-scale, noise-free quantum machine. We evaluated the correctness and efficiency of our approach using IBM Qiskit on nine open-source projects and randomly generated edge-labeled graphs/constraints. The results demonstrate the effectiveness of our approach and shed light on the promising direction of applying quantum algorithms to address the general challenges in static analysis.