Algoritmi di ricerca quantistica assistiti da entanglement

Grover’s algorithm provides a quadratic speed-up for unstructured search, while quantum-walk-based spatial search extends this advantage to geometrically constrained settings, where topological properties become relevant. In this thesis, we investigate whether entanglement between two quantum registers can enhance the success probability of quantum search algorithms beyond the standard single-register framework, in both the single-solution and multiple-solution settings. We analyze both spatial search on a two-dimensional lattice and combinatorial Grover search by preparing two walkers in symmetric, antisymmetric, and more general entangled states, and by evolving them in parallel under tensor-product search operators. Numerical simulations show that antisymmetric states can yield a finite-size enhancement in success probability, with different asymptotic decay behaviors depending on the structure of the solution space, while symmetric configurations are generally less favorable. We then derive analytical results for the combinatorial case and prove that, under unitary tensor-product evolution and maximally entangled initial states, the interference term responsible for the enhancement vanishes in the asymptotic limit for large number of qubits in the register. This establishes a no-go result for asymptotic entanglement-assisted speed-up within the standard amplitude amplification framework. Our results indicate that entanglement may modify finite-size behavior, but does not radically alter the controlled two-dimensional interference mechanism underlying quantum search speed-up.