A Grover-Based Quantum Algorithm for Solving Perfect Mazes via Fitness-Guided Search
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916870666321920 |
|---|---|
| author | Wu, Michelle L. |
| author_facet | Wu, Michelle L. |
| contents | We present a quantum algorithm for solving perfect mazes by casting the pathfinding task as a structured search problem. Building on Grover's amplitude amplification, the algorithm encodes all candidate paths in superposition and evaluates their proximity to the goal using a reversible fitness operator based on quantum arithmetic. A Grover-compatible oracle marks high-fitness states, and an adaptive cutoff strategy refines the search iteratively. We provide formal definitions, unitary constructions, and convergence guarantees, along with a resource analysis showing efficient scaling with maze size and path length. The framework serves as a foundation for quantum-hybrid pathfinding and planning. The full algorithmic pipeline is specified from encoding to amplification, including oracle design and fitness evaluation. The approach is readily extensible to other search domains, including navigation over tree-like or acyclic graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_21937 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Grover-Based Quantum Algorithm for Solving Perfect Mazes via Fitness-Guided Search Wu, Michelle L. Quantum Physics Emerging Technologies Quantum Algebra 81P68, 68Q12 F.1.2; F.2.2; I.2.8 We present a quantum algorithm for solving perfect mazes by casting the pathfinding task as a structured search problem. Building on Grover's amplitude amplification, the algorithm encodes all candidate paths in superposition and evaluates their proximity to the goal using a reversible fitness operator based on quantum arithmetic. A Grover-compatible oracle marks high-fitness states, and an adaptive cutoff strategy refines the search iteratively. We provide formal definitions, unitary constructions, and convergence guarantees, along with a resource analysis showing efficient scaling with maze size and path length. The framework serves as a foundation for quantum-hybrid pathfinding and planning. The full algorithmic pipeline is specified from encoding to amplification, including oracle design and fitness evaluation. The approach is readily extensible to other search domains, including navigation over tree-like or acyclic graphs. |
| title | A Grover-Based Quantum Algorithm for Solving Perfect Mazes via Fitness-Guided Search |
| topic | Quantum Physics Emerging Technologies Quantum Algebra 81P68, 68Q12 F.1.2; F.2.2; I.2.8 |
| url | https://arxiv.org/abs/2507.21937 |