2025/06/06 by F. Mohit, Joshua J. Guanzon, Mohit, Fatemeh +13
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #Neural Networks and Reservoir Computing
paper · pdf · doi:10.48550/arxiv.2506.06435
Grover's algorithm is one of the pioneering demonstrations of the advantages of quantum computing over its classical counterpart, providing - at most - a quadratic speed-up over the classical solution for unstructured database search. The original formulation of Grover's algorithm is non-deterministic, finding the answer with a probability that varies with the size of the search space and the number of marked elements. A recent reformulation introduced a deterministic form of Grover's algorithm that - in principle - finds the answer with certainty. Here we realise the deterministic Grover's algorithm on a programmable photonic integrated circuit, finding that it not only outperforms the original Grover's algorithm as predicted, but is also markedly more robust against technological imperfections. We explore databases of 4 to 10 elements, with every choice of a single marked element, achieving an average success probability of 99.77 ± 0.05%.