Quantum mechanics can find a needle in a haystack every time
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910993105289216 |
|---|---|
| author | Mohit, Fatemeh Guanzon, Joshua McKinlay, Jaden Weinhold, Till J. Myers, Casey R. Almeida, Marcelo P. Rambach, Markus White, Andrew G. |
| author_facet | Mohit, Fatemeh Guanzon, Joshua McKinlay, Jaden Weinhold, Till J. Myers, Casey R. Almeida, Marcelo P. Rambach, Markus White, Andrew G. |
| contents | 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 \pm 0.05\%$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_06435 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum mechanics can find a needle in a haystack every time Mohit, Fatemeh Guanzon, Joshua McKinlay, Jaden Weinhold, Till J. Myers, Casey R. Almeida, Marcelo P. Rambach, Markus White, Andrew G. Quantum Physics 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 \pm 0.05\%$. |
| title | Quantum mechanics can find a needle in a haystack every time |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2506.06435 |