1. Bibliographic Information

1.1. Title

A Grover-Based Quantum Algorithm for Solving Perfect Mazes via Fitness-Guided Search

1.2. Authors

Michelle L. Wu

1.3. Journal/Conference

This paper is a preprint, published on arXiv. The arXiv platform (https://arxiv.org/) is a widely respected open-access repository for preprints of scientific papers in physics, mathematics, computer science, quantitative biology, quantitative finance, statistics, electrical engineering and systems science, and economics. While not a peer-reviewed journal or conference in itself, it serves as a crucial venue for rapid dissemination of research findings and early community feedback in the scientific world, especially in rapidly evolving fields like quantum computing.

1.4. Publication Year

2025

1.5. Abstract

The paper introduces a quantum algorithm designed to solve perfect mazes. It reframes the pathfinding problem as a structured search problem leveraging Grover's amplitude amplification. The algorithm initiates by encoding all possible candidate paths into a quantum superposition. It then employs a reversible fitness operator, built upon quantum arithmetic, to evaluate how close each path leads to the goal. A specially designed Grover-compatible oracle marks paths that exhibit high fitness. An adaptive cutoff strategy is integrated to iteratively refine the search, focusing on increasingly better solutions. The authors provide formal definitions, construct the necessary unitary operations, and offer convergence guarantees for the algorithm. A resource analysis indicates efficient scaling with respect to maze size and path length. The proposed framework is presented as a foundational step for quantum-hybrid pathfinding and planning, detailing the entire algorithmic pipeline from encoding to amplification, including oracle design and fitness evaluation. The approach is noted for its extensibility to other search domains, such as navigation over tree-like or acyclic graphs.

1.6. Original Source Link

https://arxiv.org/abs/2507.21937v2

1.7. PDF Link

https://arxiv.org/pdf/2507.21937v2.pdf

2. Executive Summary

2.1. Background & Motivation

The core problem addressed by this paper is maze solving, specifically finding a valid path from a start cell to a goal cell within a perfect two-dimensional maze. This problem is fundamental and has broad applications in robotics, game theory, and artificial intelligence.

The importance of this problem stems from its computational complexity. For perfect mazes, defined as acyclic, fully connected grids, the problem is classified as NP-complete. Classical approaches, such as backtracking and breadth-first search (BFS), suffer from exponential scaling behavior with increasing maze size and branching factor. This exponential scaling severely limits their practical applicability for large or complex maze instances, making them computationally intractable.

Quantum computing emerges as an alternative paradigm offering potential algorithmic speedups by utilizing principles like superposition and interference. Grover's search algorithm, in particular, provides a quadratic improvement for unstructured search problems and forms a strong basis for formulating structured search tasks within the quantum domain. While previous conceptual explorations of quantum maze-solving exist, they often lack rigorous definitions or circuit-level implementations for key components like fitness evaluation and oracle design.

The paper's entry point and innovative idea lie in filling these gaps by providing a complete, rigorously defined, and circuit-level specified quantum algorithm for perfect maze solving. It frames the pathfinding problem as a structured quantum search problem, leveraging the strengths of Grover's algorithm to overcome the exponential scaling challenges faced by classical methods.

2.2. Main Contributions / Findings

The paper makes several primary contributions to the field of quantum algorithms and pathfinding:

• Complete Quantum Algorithmic Framework: It presents a full, end-to-end quantum algorithm for solving perfect mazes, covering all stages from path encoding to amplitude amplification.

• Rigorous Quantum Encoding: It provides a formal method for quantum encoding of all candidate paths in a uniform superposition, along with a proof of correctness (Theorem 1).

• Reversible Fitness Operator: The paper defines and constructs a reversible fitness evaluation operator (Theorem 2) that scores paths based on their proximity to the goal state. This operator utilizes quantum arithmetic primitives and is proven to be unitary, crucial for quantum computation.

• Grover-Compatible Oracle Design: A Grover-compatible oracle is designed that selectively amplifies high-fitness paths by applying a phase flip. The circuit construction and unitarity of the oracle are formally demonstrated.

• Adaptive Cutoff Strategy: An adaptive cutoff strategy is introduced to iteratively refine the search. This strategy allows the algorithm to dynamically adjust the threshold for "high-fitness" paths, ensuring monotonic improvement in observed fitness values (Lemma 1) and finite-time convergence to optimal solutions (Theorem 3, Theorem 4).

• Convergence Guarantees: The paper provides formal convergence guarantees for the adaptive cutoff strategy, proving that it converges to the maximum fitness with high probability within a bounded number of iterations.

• Resource Analysis: A detailed resource analysis is presented, quantifying the time complexity (circuit depth) and resource requirements (qubit count, gate types) of the algorithm. This analysis demonstrates efficient scaling with maze size and path length, highlighting its feasibility for near-term quantum architectures.

• Extensibility: The framework is noted for its extensibility to other search domains, particularly tree-like or acyclic graphs, suggesting its broader applicability beyond perfect mazes.

  These findings solve the problem of developing a theoretically sound and practically implementable quantum algorithm that can potentially offer a quadratic speedup over classical methods for maze solving, thereby addressing the exponential scaling limitation. The rigorous definitions and circuit constructions address the gaps in previous conceptual quantum maze-solving explorations.

3. Prerequisite Knowledge & Related Work

3.1. Foundational Concepts

To understand this paper, a reader needs familiarity with fundamental concepts from classical computing, maze theory, and quantum computing.

3.1.1. Perfect Mazes

A perfect maze is a specific type of maze characterized by two properties:

• Acyclic: There are no loops or cycles within the maze structure. This means that if you follow any path, you will never return to a cell you've already visited without retracing your steps.
• Fully connected: There is exactly one unique path between any two cells in the maze. This implies that every cell is reachable from every other cell, and there are no isolated sections. The paper models the maze as an $m \times m$ grid, where each cell has four cardinal directions (North, East, South, West) that can be open or closed (walls). The problem involves finding a path from a designated start cell to a goal cell.

3.1.2. NP-Complete Problems

NP-complete problems are a class of computational problems for which no known polynomial-time algorithm exists on a classical computer. This means that as the size of the problem grows, the time required to solve it typically increases exponentially, making large instances intractable. Maze solving, in its general form, belongs to this class. Finding a path in a general graph is P-complete (can be solved in polynomial time), but finding the shortest path or specific types of paths in more complex scenarios can be NP-complete. For perfect mazes, while finding any path is relatively easy, the formulation here for path sequences implies a search space that grows exponentially.

3.1.3. Classical Search Algorithms

• Backtracking: A general algorithmic technique for solving computational problems that systematically tries to build up a solution one step at a time. If a partial solution cannot be completed to a valid solution, it "backtracks" to an earlier state and tries a different option. This often explores many redundant paths.
• Breadth-First Search (BFS): An algorithm for traversing or searching tree or graph data structures. It systematically explores all of the neighbor nodes at the present depth level before moving on to nodes at the next depth level. It guarantees finding the shortest path in terms of number of edges in an unweighted graph, but it still explores a large portion of the search space. Both backtracking and BFS can exhibit exponential scaling in terms of time and space complexity depending on the maze's branching factor and size.

3.1.4. Quantum Computing Principles

• Qubits: The basic unit of quantum information, analogous to a classical bit. Unlike a classical bit which can only be 0 or 1, a qubit can be 0, 1, or a superposition of both simultaneously.
• Superposition: A quantum mechanical principle stating that a quantum system can exist in multiple states simultaneously until it is measured. For example, a qubit in superposition can be both $|0\rangle$ and $|1\rangle$ at the same time. This allows quantum computers to process multiple possibilities concurrently.
• Unitary Operations/Gates: Quantum operations are represented by unitary matrices. These operations are reversible and preserve the normalization of quantum states. This property of reversibility is crucial for quantum algorithms, as it means no information is lost during computation, which helps prevent energy dissipation (in principle) and allows for techniques like uncomputation.
• Amplitude Amplification: A general technique used in quantum computing to boost the probability of measuring a desired state. It is the core idea behind Grover's algorithm.

3.1.5. Grover's Algorithm

Grover's algorithm is a quantum search algorithm that can find a specific item in an unstructured database quadratically faster than any classical algorithm. For a database of $N$ items, it can find the target item in $O(\sqrt{N})$ queries, compared to $O(N)$ for classical algorithms. It works by:

• Initialization: Creating a uniform superposition of all possible states.
• Oracle: A quantum oracle (often denoted $U_f$) marks the desired state(s) by applying a phase flip (e.g., multiplying their amplitude by -1).
• Diffuser (Grover Diffusion Operator): An operation that amplifies the amplitudes of the marked states and diminishes the amplitudes of the unmarked states. It effectively reflects the state vector about the initial uniform superposition state.
• Iteration: Repeating the oracle and diffuser operations multiple times. Each iteration rotates the state vector closer to the marked state(s). The optimal number of iterations is approximately $\frac{\pi}{4}\sqrt{\frac{N}{k}}$, where $k$ is the number of marked states.

3.2. Previous Works

The paper explicitly builds upon established techniques in quantum computing and refers to several foundational works:

• Grover's Search Algorithm [3]: The entire algorithm is Grover-based, relying on the principles of amplitude amplification introduced by Lov Grover. The paper formalizes the oracle and diffuser operators within the context of maze solving.
• Quantum Arithmetic Circuits [1, 2]: The reversible fitness operator and oracle comparator circuit are constructed using quantum arithmetic primitives. Specifically, the paper references:
  • Cuccaro's ripple-carry addition circuit [1]: This work describes efficient reversible circuits for addition, which can be adapted for subtraction and comparison.
  • Draper's work on quantum addition [2]: Early work on quantum adders is fundamental for constructing quantum arithmetic units. These works are crucial because quantum operations must be unitary (reversible). Classical arithmetic operations are often irreversible (e.g., $A+B \to S$, where $A$ and $B$ cannot be uniquely recovered from $S$ without additional information). Reversible quantum arithmetic circuits ensure that ancilla qubits can be uncomputed and reused, minimizing qubit requirements and maintaining unitarity.
• Elementary Gates for Quantum Computation [5]: This paper (by Barenco et al.) is a classic in quantum computation, detailing how complex quantum operations can be built from a universal set of elementary gates (e.g., CNOT, Toffoli, single-qubit rotations). The proposed circuits for fitness evaluation and oracle design are understood to be compilable into these elementary gates.
• Time/Space Trade-offs for Reversible Computation [6]: Bennett's work on reversible computation provides theoretical underpinnings for uncomputation techniques. This is essential for minimizing the number of ancilla qubits needed by resetting temporary registers to $|0\rangle$ after use, ensuring reversibility and resource efficiency.
• Quantum-Inspired Maze-Solving [7]: This reference suggests that prior work has explored quantum-inspired or hybrid quantum-classical methods for maze solving. The current paper differentiates itself by providing a complete quantum algorithm with rigorous, circuit-level specifications, addressing the conceptual nature of earlier approaches.

3.3. Technological Evolution

The evolution of search algorithms has progressed from exhaustive classical methods (BFS, DFS, backtracking) to more optimized heuristic-based approaches (A* search). These classical methods, while effective for smaller problems, hit computational bottlenecks (exponential scaling) as problem size increases.

Quantum computing offers a paradigm shift. Early theoretical work (e.g., Shor's algorithm for factoring, Grover's algorithm for search) demonstrated the potential for quantum speedups. The technological evolution involves building increasingly complex quantum processors capable of running these algorithms, moving from small-scale NISQ (Noisy Intermediate-Scale Quantum) devices towards larger, fault-tolerant quantum computers.

This paper's work fits into the current stage of developing practical quantum algorithms for specific problems. It takes a known quantum primitive (Grover's algorithm) and rigorously adapts it to a well-understood classical problem (maze solving), providing detailed circuit designs that were previously conceptual. This bridge between high-level quantum algorithms and low-level circuit implementation is crucial for advancing the field.

3.4. Differentiation Analysis

Compared to main methods in related work, this paper's approach offers several core differences and innovations:

• Rigorous Quantum Implementation vs. Conceptual/Classical-Hybrid:

  • Classical Methods (BFS, Backtracking): These methods explore the search space sequentially, leading to exponential time complexity for larger mazes. This paper offers a quadratic speedup through Grover's algorithm ($O(\sqrt{N})$ vs $O(N)$ for unstructured search, or improved scaling for structured search).
  • Prior Quantum-Inspired/Conceptual Approaches [7]: While previous studies have conceptually explored quantum maze-solving or hybrid classical-quantum approaches, they often lacked the detailed, circuit-level specifications for key components. This paper explicitly addresses this gap by providing formal mathematical definitions, unitary constructions, and convergence analyses for the entire quantum search process.

• Fully Quantum and Reversible Components:

  • Reversible Fitness Operator: A major innovation is the reversible fitness operator built entirely from quantum arithmetic primitives. This ensures the operator is unitary, a fundamental requirement for quantum computation, something not typically considered in classical or "quantum-inspired" approaches. This avoids decoherence and information loss.
  • Grover-Compatible Oracle: The paper details the construction of a Grover-compatible oracle that uses a reversible comparator to mark high-fitness states. This is a complete, specified quantum circuit, unlike potentially abstract oracle definitions in other works.

• Adaptive Cutoff Strategy for Refined Search: The introduction of a monotonic adaptive cutoff strategy is a practical innovation. Instead of requiring prior knowledge of the optimal fitness value or the number of optimal solutions (which is often difficult for Grover's algorithm), this strategy iteratively refines the search, dynamically adjusting the oracle's target. This makes the algorithm more robust and self-correcting, guaranteeing convergence to optimal solutions.

• Formal Proofs and Resource Analysis: The paper provides detailed proofs of correctness and unitarity for its components, alongside a comprehensive resource analysis (qubit count, gate depth). This level of rigor is essential for evaluating the practical feasibility of quantum algorithms on current and future hardware.

  In essence, this paper elevates the concept of quantum maze-solving from an abstract possibility to a concretely specified and mathematically validated algorithm, ready for potential implementation on quantum hardware.

4. Methodology

The proposed quantum algorithm for solving perfect mazes leverages Grover's amplitude amplification. It involves several key stages: problem formalization, quantum encoding, fitness evaluation, oracle design, and iterative amplitude amplification with an adaptive cutoff strategy.

4.1. Principles

The core idea is to cast the maze-solving problem as a structured search problem within a quantum framework. Instead of exhaustively exploring paths sequentially (as in classical algorithms), all possible candidate paths are initially encoded into a uniform superposition. A fitness function then quantifies the "goodness" of each path (how close it gets to the goal). This fitness information is used by a Grover-compatible oracle to mark the high-fitness paths. Through Grover iterations (amplitude amplification), the amplitudes of these marked paths are boosted, making them more likely to be measured. An adaptive cutoff strategy dynamically adjusts what constitutes a "high-fitness" path, progressively focusing the search on better and better solutions until the optimal path is found. All operations are designed to be reversible and unitary, as required by quantum mechanics.

4.2. Core Methodology In-depth (Layer by Layer)

4.2.1. Problem Formalization

The maze is modeled as a perfect $m \times m$ grid. $$\mathcal{M} := \{0, 1, \ldots, m-1\} \times \{0, 1, \ldots, m-1\}$$ where:

• $\mathcal{M}$ represents the set of all cells in the $m \times m$ grid.
• $m$ is the dimension of the square maze (e.g., for a $2 \times 2$ maze, $m=2$). Each cell $(i, j) \in \mathcal{M}$ can have open walls in any of the four cardinal directions: $\{N, E, S, W\}$.

The maze is assumed to be:

• Solvable: At least one path exists from a unique start cell $(i_s, j_s)$ to a goal cell $(i_f, j_f)$.
• Loop-free: The maze forms a tree structure over $\mathcal{M}$, meaning there is exactly one simple path between any two reachable cells.

Path Representation

A path of length $n$ is defined as a sequence of $n$ directional moves: $$P = (d_1, d_2, \ldots, d_n), \quad \mathrm{where} \quad d_k \in \{N, E, S, W\}$$ Each direction is encoded as a 2-bit binary string:

• $N = 00$
• $E = 01$
• $S = 10$
• $W = 11$ Consequently, a path of length $n$ corresponds to a 2n-bit string, or a quantum state on 2n qubits: $$|P\rangle = |d_1\rangle \otimes |d_2\rangle \otimes \dots \otimes |d_n\rangle \in (\mathbb{C}^2)^{\otimes 2n}$$

Search Space

The complete set of candidate paths of length $n$ is: $$\mathcal{P}_n := \{N, E, S, W\}^n, \quad \mathrm{so~that} \quad |\mathcal{P}_n| = 4^n$$ where:

• $\mathcal{P}_n$ is the set of all possible sequences of $n$ moves.

• $|\mathcal{P}_n|$ is the total number of such sequences, which is $4^n$ because there are 4 possible moves for each of the $n$ steps.

  A partial transition function $\delta$ is defined to simulate the movement: $$\delta \left( (i, j), d \right) = \left\{ \begin{array}{ll} (i', j') & \mathrm{if~move~in~} d \mathrm{~from~} (i, j) \mathrm{~is~legal} \\ \perp & \mathrm{if~move~hits~a~wall~or~exits~the~grid} \end{array} \right.$$ where:

• (i, j) is the current cell.

• $d$ is the direction of the move.

• (i', j') is the new cell if the move is legal.

• $\perp$ (read "bottom" or "undefined") indicates an invalid move (hitting a wall or going out of bounds).

  A path $P = (d_1, \ldots, d_n)$ induces a sequence of positions: $$(i_0, j_0) := (i_s, j_s), \quad (i_k, j_k) := \delta \big( (i_{k-1}, j_{k-1}), d_k \big)$$ where:

• $(i_0, j_0)$ is the starting cell.

• $(i_k, j_k)$ is the cell reached after the $k$-th move. If $\delta$ returns $\perp$ at any step $k < n$, the path is considered invalid beyond that point, and end(P) is defined as the last valid cell prior to $\perp$.

Goal Definition

The end function returns the final position of path $P$: $\mathrm{end}(P) := (i_n, j_n)$ The optimization objective is to find a path $P^\star \in \mathcal{P}_n$ that either:

1. Exactly reaches the goal: $\mathrm{end}(P^\star) = (i_f, j_f)$.
2. Minimizes the distance to the goal using a specified metric (e.g., Manhattan distance): $$P^\star := \arg \min_{P \in \mathcal{P}_n} \mathrm{dist}(\mathrm{end}(P), (i_f, j_f))$$ This objective is formalized by the fitness function.

Path Length Parameter

The choice of $n$ (path length) is critical:

• If $n < \mathrm{length}(P^*)$, the true optimal path is excluded from the search space.
• If $n > \mathrm{length}(P^*)$, the search space includes redundant or invalid paths. The paper assumes $n \ge \ell_{\mathrm{min}}$, where $\ell_{\mathrm{min}}$ is the unique path length from $(i_s, j_s)$ to $(i_f, j_f)$. This value can be set heuristically or adapted iteratively. The loop-free nature of perfect mazes (tree structure) is beneficial for pruning.

4.2.2. Quantum Encoding and Superposition

The algorithm begins by encoding candidate paths into quantum states.

A path $P = (d_1, d_2, \ldots, d_n) \in \mathcal{P}_n$ is a sequence of $n$ moves. Each direction $d_k \in \{N, E, S, W\}$ is mapped to a 2-bit binary string using the encoding map $\chi$: $$\begin{array}{rcl} \chi(N) = 00 & \quad & \chi(E) = 01 \\ \chi(S) = 10 & \quad & \chi(W) = 11 \end{array}$$ A path $P$ is then mapped to a 2n-bit binary string: $$\chi(P) = \chi(d_1) \parallel \chi(d_2) \parallel \cdots \parallel \chi(d_n) \in \{0, 1\}^{2n}$$ where $\parallel$ denotes string concatenation.

Quantum Register Representation

Each bit in the 2n-bit string is associated with a qubit. The full quantum register lives in the Hilbert space: $$\mathcal{H} := (\mathbb{C}^2)^{\otimes 2n}, \quad \mathrm{dim} \mathcal{H} = 2^{2n}$$ For each path $P \in \mathcal{P}_n$, its quantum state is defined as: $$|P\rangle := |\chi(P)\rangle \in \mathcal{H}$$ For example, if $P = (N, E, S)$, then $|\chi(P)\rangle = |000110\rangle = |0\rangle \otimes |0\rangle \otimes |0\rangle \otimes |1\rangle \otimes |1\rangle \otimes |0\rangle$.

Uniform Superposition Over Paths

The goal is to prepare a quantum state that is a uniform superposition of all possible encoded paths: $$|\Omega\rangle := \frac{1}{\sqrt{|\mathcal{P}_n|}} \sum_{P \in \mathcal{P}_n} |P\rangle = \frac{1}{2^n} \sum_{P \in \mathcal{P}_n} |\chi(P)\rangle$$

Hadamard Preparation and Encoding Validity

To achieve this, the initial state is set to $|0\rangle^{\otimes 2n}$. Applying Hadamard gates to each qubit, $H^{\otimes 2n} |0\rangle^{\otimes 2n}$, creates a uniform superposition over all 2n-bit binary strings: $$H^{\otimes 2n} |0\rangle^{\otimes 2n} = \frac{1}{\sqrt{2^{2n}}} \sum_{z \in \{0,1\}^{2n}} |z\rangle$$ However, not all 2n-bit strings correspond to valid direction sequences (e.g., if we encode N=00, E=01, S=10, W=11, then 000000... is valid, but 000010... would be invalid if read as single bits). The encoding maps each direction to two bits.

To restrict the superposition to only valid direction encodings, qubits are grouped into $n$ pairs. The Hilbert space is decomposed as: $$\mathcal{H} = \bigotimes_{k=1}^n \mathcal{H}_k, \quad \mathrm{where~} \mathcal{H}_k := \mathbb{C}^2 \otimes \mathbb{C}^2$$ For each 2-qubit block (representing one direction), applying $H^{\otimes 2}$ to $|00\rangle$ creates a uniform superposition over the four possible 2-bit direction encodings: $$H^{\otimes 2} |00\rangle = \frac{1}{2} \sum_{b \in \{0,1\}^2} |b\rangle = \frac{1}{2} (|00\rangle + |01\rangle + |10\rangle + |11\rangle)$$ Then, the full state becomes the desired uniform superposition: $$|\Omega\rangle = \bigotimes_{k=1}^n \left( \frac{1}{2} \sum_{b_k \in \{0,1\}^2} |b_k\rangle \right) = \frac{1}{2^n} \sum_{P \in \mathcal{P}_n} |\chi(P)\rangle$$

Theorem 1 (Superposition Correctness). Let $n \in \mathbb{N}.$ Let $\mathcal{P}_n = \{N, E, S, W\}^n$ be the set of all direction sequences of length $n$, and define the encoding map $\chi : \mathcal{P}_n \to \{0, 1\}^{2n}$ as above. Let $|\Omega\rangle \in (\mathbb{C}^2)^{\otimes 2n}$ be the quantum state defined by: $$|\Omega\rangle := \bigotimes_{k=1}^n \left( H^{\otimes 2} |00\rangle \right)$$ Then: $$|\Omega\rangle = \frac{1}{2^n} \sum_{P \in \mathcal{P}_n} |\chi(P)\rangle$$ That is, $|\Omega\rangle$ is a uniform superposition over all valid direction sequences of length $n$.

Proof. Let $\mathcal{H} := (\mathbb{C}^2)^{\otimes 2n}$. The Hilbert space can be decomposed into $n$ independent 2-qubit subsystems: $$\mathcal{H} = \bigotimes_{k=1}^n \mathcal{H}_k, \quad \mathrm{where~} \mathcal{H}_k = \mathbb{C}^2 \otimes \mathbb{C}^2$$ Each 2-qubit subsystem $\mathcal{H}_k$ will encode one direction $d_k \in \{N, E, S, W\}$ via the injective map $\chi$. Now apply $H^{\otimes 2}$ to each pair of qubits initialized in $|00\rangle$: $$H^{\otimes 2} |00\rangle = \frac{1}{2} \sum_{b \in \{0,1\}^2} |b\rangle = \frac{1}{2} (|00\rangle + |01\rangle + |10\rangle + |11\rangle)$$ This operation creates a uniform superposition over the four possible 2-bit binary strings, which correspond exactly to the four valid direction encodings ($N$, $E$, $S$, $W$). Since all $n$ direction encodings are independent, the total state is formed by taking the tensor product of these individual superpositions: $$\begin{array}{rl} |\Omega\rangle &= \bigotimes_{k=1}^n \left( \frac{1}{2} \sum_{b_k \in \{0,1\}^2} |b_k\rangle \right) \\ &= \frac{1}{2^n} \sum_{(b_1, \ldots, b_n) \in (\{0,1\}^2)^n} |b_1 \rangle \ldots |b_n \rangle \end{array}$$ Each concatenated string $b_1 \parallel \ldots \parallel b_n \in \{0,1\}^{2n}$ is equal to $\chi(P)$ for some $P \in \mathcal{P}_n$ by the definition of the encoding map $\chi$. Therefore, the sum runs over all such encodings: $$|\Omega\rangle = \frac{1}{2^n} \sum_{P \in \mathcal{P}_n} |\chi(P)\rangle$$ Thus, $|\Omega\rangle$ is a uniform superposition over all valid direction sequences of length $n$. $\blacksquare$

4.2.3. Fitness Operator Construction

The fitness function evaluates how close a given path $P \in \mathcal{P}_n$ (encoded as $|x\rangle = |\chi(P)\rangle$) ends to the maze goal cell $(i_f, j_f)$, starting from $(i_s, j_s)$. The directions are $N=00, E=01, S=10, W=11$.

The fitness of path $P$ is defined using the squared Euclidean distance: $$\mathrm{fitness}(P) = C - \left[ (i_{\mathrm{end}} - i_f)^2 + (j_{\mathrm{end}} - j_f)^2 \right]$$ where:

• $i_{\mathrm{end}}, j_{\mathrm{end}}$ are the coordinates of the cell where path $P$ ends.
• $i_f, j_f$ are the coordinates of the goal cell.
• $C = 2^r$ is a power-of-two constant. The constant $C$ must satisfy $C \geq 2(m-1)^2$ to ensure that the fitness value is always non-negative. This fitness is maximized when the path reaches the goal, resulting in a distance of 0. The smallest integer $r \in \mathbb{N}$ such that $C = 2^r$ determines the number of qubits required to store the fitness value.

Definition: Fitness Operator

Definition 1 (Fitness Operator). Let $|x\rangle$ be the quantum register encoding path $P \in \mathcal{P}_n$, and let $|0\rangle_f$ be an ancillary fitness register of $r$ qubits. The fitness operator is the unitary transformation: $$F : |x\rangle |0\rangle_f \mapsto |x\rangle |\mathrm{fitness}(x)\rangle$$ where the fitness is computed via a reversible simulation of the path defined by $|x\rangle$ and stored in $|f\rangle = |\mathrm{fitness}(x)\rangle$.

Quantum Circuit Implementation

The implementation of the fitness operator $F$ requires several quantum registers:

• $|x\rangle$: 2n-qubit path register.

• $|i\rangle, |j\rangle$: Position registers, each of $\lceil \log_2 m \rceil$ qubits, to store the current $i$ and $j$ coordinates.

• $|d\rangle$: Distance register (stores the squared Euclidean distance).

• $|f\rangle$: Fitness register of $r = \lceil \log_2 C \rceil$ qubits, where $C \geq 2(m-1)^2$.

• Ancillae: Temporary registers for subtraction, squaring, and cleanup.

  The circuit for $F$ consists of the following reversible stages:

1. Path Simulation: For each $k=1$ to $n$, the 2-qubit slice $|d_k\rangle$ from $|x\rangle$ (representing the $k$-th direction) is extracted. A direction-controlled update is applied to the position registers $|i\rangle, |j\rangle$: $$\delta(i, j; d_k) := \left\{ \begin{array}{ll} i \mapsto i-1 & \mathrm{if~} d_k = 00 \quad (\text{North}) \\ j \mapsto j+1 & \mathrm{if~} d_k = 01 \quad (\text{East}) \\ i \mapsto i+1 & \mathrm{if~} d_k = 10 \quad (\text{South}) \\ j \mapsto j-1 & \mathrm{if~} d_k = 11 \quad (\text{West}) \end{array} \right.$$ Each update is implemented using multi-controlled add/subtract circuits (e.g., those described in [1]), which are composed of Toffoli and CNOT gates. These operations are inherently reversible.

   • Validity Check: (As detailed in XV. VALIDITY CHECK OPERATOR AND CORRECTNESS in the Appendix) Alongside position updates, a validity flag $|v\rangle$ is maintained. Initially set to $|1\rangle$, it is flipped to $|0\rangle$ if any move leads out of bounds or hits a wall. This is done using reversible comparators and Toffoli gates. If $|v\rangle$ becomes $|0\rangle$, further position updates for that path are effectively ignored or indicate an invalid path.

2. Distance Computation: Let the final position after path simulation be (i, j). The squared Euclidean distance is calculated: $d = (i - i_f)^2 + (j - j_f)^2$ This involves:

   • Using quantum subtractors to compute $|d_i\rangle := |i - i_f\rangle$ and $|d_j\rangle := |j - j_f\rangle$.
   • Applying reversible squaring circuits (e.g., Toffoli-based multipliers as in [2]) to get $|d_i^2\rangle$ and $|d_j^2\rangle$.
   • Adding these squared values to get the total distance $|d\rangle = |d_i^2 + d_j^2\rangle$.

3. Fitness Calculation: The fitness value is computed using a reversible subtractor: $|f\rangle = |C - d\rangle$ The constant $C = 2^r$ is hardcoded as a fixed binary input to the arithmetic circuit. The result is written into the fitness register $|f\rangle$.

4. Uncomputation: All ancilla registers used for intermediate calculations (subtraction, squaring, validity check) are reset to $|0\rangle$ by reversing the operations that created them. This ensures the overall reversibility of the operator, leaving the path register $|x\rangle$ and the fitness register $|f\rangle$ in their final entangled state: $|x\rangle |f\rangle$.

   Theorem 2 (Fitness Operator is Unitary). The fitness operator $F$ defined above is unitary on the joint space of the path and fitness registers: $F^\dagger F = I$ Proof. The operator $F$ is composed of the following reversible components:

• Path simulation: This involves coordinate updates controlled by path data, implemented with multi-controlled add/subtract gates, which are unitary.
• Distance computation: This involves reversible arithmetic operations (subtraction, squaring, addition) on position deltas, all of which can be constructed from unitary gates (e.g., Toffoli, CNOT).
• Fitness evaluation: This is a subtraction from a fixed power-of-two constant, also implemented using reversible arithmetic circuits, thus unitary.
• Uncomputation: This stage reverses all ancilla-internal operations, which is equivalent to applying the inverse of the unitary operations used to compute them. This ensures that the overall transformation is reversible and thus unitary. Since the overall transformation $F$ is a composition of unitary operations, it is itself unitary. $\blacksquare$

Worked Example

Let $m=2, n=2$, with $(i_s, j_s) = (0,0)$ and $(i_f, j_f) = (1,1)$. Consider the path $|x\rangle = |1001\rangle$. Decoded: $S$ (10) $\to i \mapsto i+1$, $E$ (01) $\to j \mapsto j+1$.

1. Path Simulation:

   • Start: $(0,0)$
   • Move $S$: $(0,0) \stackrel{S}{\to} (1,0)$
   • Move $E$: $(1,0) \stackrel{E}{\to} (1,1)$
   • Final cell: $\mathrm{end}(P) = (1,1)$.

2. Distance Calculation:

   • $i_{\mathrm{end}}=1, j_{\mathrm{end}}=1$. Goal: $i_f=1, j_f=1$.
   • Distance $d = (1-1)^2 + (1-1)^2 = 0^2 + 0^2 = 0$.

3. Fitness Calculation:

   • Let $C = 2^2 = 4$ (since $2(m-1)^2 = 2(2-1)^2 = 2$, $C=4$ is the smallest power of 2 greater than or equal to 2).

   • Fitness = $C - d = 4 - 0 = 4$.

   • The fitness register $|f\rangle$ would store $|100\rangle$ (binary representation of 4).

     The circuit then entangles this output $|f\rangle$ with $|x\rangle$, and all ancilla qubits are reset to zero via uncomputation.

4.2.4. Oracle Design

The oracle operator $O$ is responsible for selectively marking high-fitness paths. It does this by applying a phase flip (multiplying the amplitude by -1) to those quantum states whose fitness value exceeds a specific cutoff threshold. This phase flip is what Grover's amplitude amplification mechanism uses to identify and amplify the desired states.

Let cutoff $\in \mathbb{N}$ denote the threshold. The oracle acts on the path register $|x\rangle$ and the fitness register $|f_x\rangle$ (which contains the fitness of path $x$) as: $$O : |x\rangle |f_x\rangle \mapsto (-1)^{g(f_x)} |x\rangle |f_x\rangle,$$ where: $$g(f_x) = \left\{ \begin{array}{ll} 1 & \mathrm{if~} f_x > \mathrm{cutoff} \\ 0 & \mathrm{otherwise} \end{array} \right.$$ The function $g(f_x)$ evaluates to 1 (triggering a phase flip) if the fitness $f_x$ is strictly greater than the cutoff, and 0 otherwise.

Encoding the Cutoff: Classical vs. Quantum

The cutoff value can be handled in two ways:

1. Classical cutoff: The cutoff is a fixed classical constant, hardcoded directly into the comparator circuit.
2. Quantum cutoff: The cutoff is stored in a quantum register $|c\rangle$, allowing for dynamic adjustment in adaptive or iterative schemes. Both scenarios are accommodated by a reversible comparator circuit that compares the fitness register $|f_x\rangle$ to either a classical constant or a quantum register $|c\rangle$.

Oracle Circuit Construction

The oracle proceeds in three reversible stages:

1. Comparator Stage: $$|f_x\rangle |0\rangle_b \mapsto |f_x\rangle |b\rangle,$$ where $|b\rangle = 1$ if and only if $f_x > \mathrm{cutoff}$. This stage employs a reversible greater-than comparator circuit. Such a circuit can be built using bitwise subtraction with carry logic.

2. Phase Flip Stage: A controlled-Z gate (CZ gate) is applied, conditioned on the ancilla qubit $|b\rangle$ being $|1\rangle$: $$|x\rangle |f_x\rangle |1\rangle_b \mapsto -|x\rangle |f_x\rangle |1\rangle_b.$$ This operation induces a phase flip specifically on the states where $|b\rangle = 1$, i.e., "marked" states. If $|b\rangle = 0$, the state remains unchanged.

3. Uncomputation Stage: The comparator logic is reversed to reset the ancilla qubit $|b\rangle$ to $|0\rangle$: $$|f_x\rangle |b\rangle \mapsto |f_x\rangle |0\rangle.$$ This preserves reversibility and restores the ancilla workspace for subsequent operations.

Greater-Than Comparator Circuit

To check if $f_x > \mathrm{cutoff}$, a reversible subtractor can be used. For example, if $|f_x\rangle = f_{m-1}\ldots f_0$ and cutoff $= c_{m-1}\ldots c_0$, the condition $f_x > \mathrm{cutoff}$ is equivalent to checking if the most significant bit (MSB) of $(f_x - \mathrm{cutoff})$ is 0, assuming a specific subtraction scheme for unsigned integers. A common approach implements this with a reversible subtractor (e.g., Cuccaro's ripple-carry subtractor [1]): $$|f\rangle |\mathrm{cutoff}\rangle |0\rangle_b \mapsto |f\rangle |\mathrm{cutoff}\rangle |f - \mathrm{cutoff}\rangle \xrightarrow{\mathrm{MSB-check}} |f\rangle |\mathrm{cutoff}\rangle |b\rangle.$$ This circuit is composed of:

• $m$ controlled-NOT and Toffoli gates for bitwise difference.
• A carry-lookahead or ripple-carry network for subtraction.
• MSB-extract logic using one ancilla qubit to determine if the result is positive. All these gates are reversible and can be implemented using Clifford + Toffoli operations.

Unitarity Proof

Each stage of the oracle is unitary:

• The comparator is a reversible function (a permutation of basis states) $C$, so its corresponding quantum operator is unitary, and $C^\dagger = C^{-1}$.
• The phase flip (a controlled-Z operation) is a diagonal unitary operator. The full oracle $O = C^\dagger \cdot Z \cdot C$ is a composition of unitary operations, and thus $O$ is unitary.

Quantum Resource Cost

Let $m_f$ be the number of qubits in $|f_x\rangle$ (e.g., $\lceil \log_2 C \rceil$).

• Comparator cost: $O(m_f)$ Toffoli gates and $O(m_f)$ ancilla qubits for carry bits (which can often be reused).
• Phase flip: One controlled-Z gate.
• Total depth: $O(m_f)$ for subtraction plus $O(m_f)$ for uncomputation.
• Total width: $m_f$ qubits for $|f_x\rangle$, 1 for the flag bit, and approximately $m_f$ ancilla qubits. Optimizations like Bennett-style garbage cleanup or ancilla reuse can further reduce the cost.

Example

Let $|f_x\rangle = |1011\rangle = 11$ (decimal), and cutoff $= 9$. Since $11 > 9$, the comparator sets $|b\rangle = 1$. The phase flip operation then acts as: $$O |x\rangle |f_x\rangle = -|x\rangle |f_x\rangle.$$ If $|f_x\rangle = |0101\rangle = 5$, then $5 \ngtr 9$. The comparator sets $|b\rangle = 0$. The phase flip operation then acts as: $$O |x\rangle |f_x\rangle = |x\rangle |f_x\rangle.$$ This oracle is Grover-compatible and supports adaptive cutoff tuning.

Boolean Logic Definition

Let the fitness register $|f_x\rangle$ contain $m_f$ qubits representing an unsigned integer $a = a_{m_f-1} a_{m_f-2} \ldots a_0$. Let the cutoff value be $c = c_{m_f-1} c_{m_f-2} \ldots c_0$, which can be classical or stored in a quantum register. The output bit $b$ (which becomes 1 if $a > c$) is defined as: $$\mathrm{GT}(a, c) = \bigcup_{i=0}^{m_f-1} \left[ a_i \wedge \neg c_i \wedge \bigwedge_{j=i+1}^{m_f-1} (a_j \oplus c_j = 0 \text{ or } a_j \wedge c_j) \right]$$ The paper's formula for the conjunction part is $\bigwedge_{j=i+1}^{m_f-1} (a_j \leftrightarrow c_j)$, where $a_j \leftrightarrow c_j$ implies $(a_j \land c_j) \lor (\neg a_j \land \neg c_j)$. This logic returns $b=1$ if and only if the unsigned integer $a$ is strictly greater than $c$.

Proof. Let $a, c \in \{0, 1\}^{m_f}$ be interpreted as unsigned binary integers. The goal is to show that $\mathrm{GT}(a, c) = 1$ if and only if $a > c$. A standard lexicographic comparison of $a$ and $c$ proceeds by examining bits from the most significant bit (MSB) ($j = m_f-1$) down to the least significant bit (LSB) ($j = 0$). The first position $i$ where $a_i \neq c_i$ determines the result:

• If $a_i = 1$ and $c_i = 0$, then $a > c$.

• If $a_i = 0$ and $c_i = 1$, then $a < c$.

• If $a_i = c_i$, continue checking the next lower bit.

  The Boolean formula provided for $\mathrm{GT}(a, c)$ explicitly encodes this logic: $$\mathrm{GT}(a, c) = \bigcup_{i=0}^{m_f-1} \left[ a_i \wedge \neg c_i \wedge \bigwedge_{j=i+1}^{m_f-1} (a_j \leftrightarrow c_j) \right]$$ For a particular bit position $i$, a term in the disjunction (OR) contributes to true if two conditions are met:

1. All more significant bits ($j > i$) match: $a_j \leftrightarrow c_j$ (i.e., $a_j = c_j$). This is captured by the conjunction $\bigwedge_{j=i+1}^{m_f-1} (a_j \leftrightarrow c_j)$.
2. At bit position $i$, we have $a_i = 1$ and $c_i = 0$. This is captured by $a_i \wedge \neg c_i$. Thus, the OR expression evaluates to true if and only if the most significant bit position where $a$ and $c$ differ is one where $a_i = 1$ and $c_i = 0$. This precisely implies that $a > c$. Since each operation in this Boolean formula (AND, OR, NOT, XNOR for $\leftrightarrow$) is reversible when implemented using standard quantum logic gates (CNOTs and Toffolis), the comparator circuit preserves unitarity and can be uncomputed. $\blacksquare$

4.2.5. Grover Iteration and Amplitude Amplification

This section details how Grover's algorithm is applied once the oracle is defined.

Let $N = 4^n$ be the total number of encoded maze paths of length $n$. Let $\mathcal{H} = \mathrm{span}\{|x\rangle : x \in \mathcal{P}_n\}$ denote the Hilbert space of path states. Let $M \subseteq \mathcal{P}_n$ be the set of marked states (those with fitness $f(x) > \mathrm{cutoff}$), and let $k = |M|$ be the number of marked states.

The initial state is the uniform superposition over all paths: $$|\Omega\rangle := \frac{1}{\sqrt{N}} \sum_{x \in \mathcal{P}_n} |x\rangle$$ This state is also sometimes denoted as $|\psi_0\rangle$ or $|\Psi\rangle$ in the paper.

Two normalized vectors are defined to represent the marked and unmarked subspaces: $$|\psi_T\rangle := \frac{1}{\sqrt{k}} \sum_{x \in M} |x\rangle \quad (\text{target subspace})$$ $$|\psi_\perp\rangle := \frac{1}{\sqrt{N-k}} \sum_{x \notin M} |x\rangle \quad (\text{unmarked subspace})$$

Lemma 1: The states $\{|\psi_T\rangle, |\psi_\perp\rangle\}$ form an orthonormal basis for a 2D subspace $\mathcal{H}_G \subset \mathcal{H}$ that contains all Grover dynamics.

Proof.

1. Normalization: Both $|\psi_T\rangle$ and $|\psi_\perp\rangle$ are normalized by construction because $\frac{1}{\sqrt{k}}\sum_{x \in M} \langle x|x \rangle = \frac{k}{\sqrt{k}\sqrt{k}} = 1$ and similarly for $|\psi_\perp\rangle$.
2. Orthogonality: Their inner product is: $$\langle \psi_T | \psi_\perp \rangle = \frac{1}{\sqrt{k(N-k)}} \sum_{x \in M} \sum_{y \notin M} \langle x | y \rangle$$ Since $M$ and its complement $(\mathcal{P}_n \setminus M)$ are disjoint sets, there is no $x=y$ such that $x \in M$ and $y \notin M$. Therefore, $\langle x | y \rangle = 0$ for all terms in the sum, and thus $\langle \psi_T | \psi_\perp \rangle = 0$. Thus, orthonormality holds. $\blacksquare$

Lemma 2: The initial state $|\Omega\rangle$ decomposes as: $$|\Omega\rangle = \sin(\theta) |\psi_T\rangle + \cos(\theta) |\psi_\perp\rangle, \quad \theta := \arcsin\left(\sqrt{\frac{k}{N}}\right).$$ Proof. We compute the projection of $|\Omega\rangle$ onto $|\psi_T\rangle$: $$\langle \psi_T | \Omega \rangle = \left( \frac{1}{\sqrt{k}} \sum_{x \in M} \langle x| \right) \left( \frac{1}{\sqrt{N}} \sum_{y \in \mathcal{P}_n} |y\rangle \right) = \frac{1}{\sqrt{N}\sqrt{k}} \sum_{x \in M} \sum_{y \in \mathcal{P}_n} \langle x|y \rangle$$ Since $\langle x|y \rangle = 1$ only if $x=y$, and $x \in M$, the sum effectively counts the number of elements in $M$: $$\langle \psi_T | \Omega \rangle = \frac{1}{\sqrt{N}\sqrt{k}} \sum_{x \in M} 1 = \frac{k}{\sqrt{N}\sqrt{k}} = \frac{\sqrt{k}}{\sqrt{N}} = \sqrt{\frac{k}{N}}$$ By definition of $\theta$, this is equal to $\sin(\theta)$. Given that $|\Omega\rangle$ is normalized and the two subspaces are orthonormal, the projection onto $|\psi_\perp\rangle$ must satisfy: $$|\langle \psi_\perp | \Omega \rangle|^2 = 1 - |\langle \psi_T | \Omega \rangle|^2 = 1 - \frac{k}{N} = \frac{N-k}{N}$$ So, $\langle \psi_\perp | \Omega \rangle = \sqrt{\frac{N-k}{N}}$. By trigonometric identity, this is $\sqrt{1 - \sin^2(\theta)} = \cos(\theta)$. Thus, the initial state can be expressed as a linear combination of the marked and unmarked subspaces: $$|\Omega\rangle = \sin(\theta) |\psi_T\rangle + \cos(\theta) |\psi_\perp\rangle$$ $\blacksquare$

Now, define the Oracle operator $O$: $$O := I - 2 \Pi_T \quad \mathrm{where} \quad \Pi_T = \sum_{x \in M} |x\rangle \langle x|$$ This oracle flips the phase of states in the marked subspace $M$. So, $O|\psi_T\rangle = -|\psi_T\rangle$ and $O|\psi_\perp\rangle = |\psi_\perp\rangle$.

And the Diffuser operator $D$: $$D := 2 |\Omega\rangle \langle \Omega| - I$$ This operator reflects any state vector about the initial state $|\Omega\rangle$.

Theorem (Grover Operator Rotation). The composite Grover operator $G := D \cdot O$ performs a rotation by an angle $2\theta$ in the plane spanned by $\{|\psi_T\rangle, |\psi_\perp\rangle\}$.

Proof. Let the initial state be $|\psi_0\rangle := |\Omega\rangle = \sin(\theta) |\psi_T\rangle + \cos(\theta) |\psi_\perp\rangle$.

1. Apply Oracle $O$: $$\begin{array}{rl} O |\psi_0\rangle &= O (\sin \theta |\psi_T\rangle + \cos \theta |\psi_\perp\rangle) \\ &= \sin \theta (O |\psi_T\rangle) + \cos \theta (O |\psi_\perp\rangle) \\ &= \sin \theta (-|\psi_T\rangle) + \cos \theta (|\psi_\perp\rangle) \\ &= -\sin \theta |\psi_T\rangle + \cos \theta |\psi_\perp\rangle \end{array}$$

2. Apply Diffuser $D = 2 |\psi_0\rangle \langle \psi_0| - I$: $$G |\psi_0\rangle = D (O |\psi_0\rangle) = (2 |\psi_0\rangle \langle \psi_0| - I) (-\sin \theta |\psi_T\rangle + \cos \theta |\psi_\perp\rangle)$$ Substitute $|\psi_0\rangle = \sin(\theta) |\psi_T\rangle + \cos(\theta) |\psi_\perp\rangle$: $$\begin{array}{l} G |\psi_0\rangle = 2 (\sin \theta |\psi_T\rangle + \cos \theta |\psi_\perp\rangle) (\sin \theta \langle \psi_T| + \cos \theta \langle \psi_\perp|) (-\sin \theta |\psi_T\rangle + \cos \theta |\psi_\perp\rangle) \\ \quad \quad - (-\sin \theta |\psi_T\rangle + \cos \theta |\psi_\perp\rangle) \\ \end{array}$$ Let's evaluate the inner product $\langle \psi_0 | (-\sin \theta |\psi_T\rangle + \cos \theta |\psi_\perp\rangle)$: $$\langle \psi_0 | (-\sin \theta |\psi_T\rangle + \cos \theta |\psi_\perp\rangle) = (\sin \theta \langle \psi_T| + \cos \theta \langle \psi_\perp|) (-\sin \theta |\psi_T\rangle + \cos \theta |\psi_\perp\rangle)$$ Since $\langle \psi_T|\psi_T\rangle=1, \langle \psi_\perp|\psi_\perp\rangle=1, \langle \psi_T|\psi_\perp\rangle=0$: $$= -\sin^2 \theta + \cos^2 \theta = \cos(2\theta)$$ So, the expression becomes: $$G |\psi_0\rangle = 2 |\psi_0\rangle \cos(2\theta) - (-\sin \theta |\psi_T\rangle + \cos \theta |\psi_\perp\rangle)$$ Substitute $|\psi_0\rangle$ back: $$\begin{array}{rl} G |\psi_0\rangle &= 2 (\sin \theta |\psi_T\rangle + \cos \theta |\psi_\perp\rangle) \cos(2\theta) + \sin \theta |\psi_T\rangle - \cos \theta |\psi_\perp\rangle \\ &= |\psi_T\rangle (2 \sin \theta \cos(2\theta) + \sin \theta) + |\psi_\perp\rangle (2 \cos \theta \cos(2\theta) - \cos \theta) \\ &= |\psi_T\rangle (\sin \theta (2 \cos(2\theta) + 1)) + |\psi_\perp\rangle (\cos \theta (2 \cos(2\theta) - 1)) \end{array}$$ Using trigonometric identities: $2 \cos(2\theta) + 1 = 2 (1 - 2\sin^2\theta) + 1 = 3 - 4\sin^2\theta = \frac{\sin(3\theta)}{\sin\theta}$ (if $\sin\theta \ne 0$) $2 \cos(2\theta) - 1 = 2 (2\cos^2\theta - 1) - 1 = 4\cos^2\theta - 3 = \frac{\cos(3\theta)}{\cos\theta}$ (if $\cos\theta \ne 0$)

   Substituting these identities: $$G |\psi_0\rangle = |\psi_T\rangle (\sin \theta \frac{\sin(3\theta)}{\sin\theta}) + |\psi_\perp\rangle (\cos \theta \frac{\cos(3\theta)}{\cos\theta}) = \sin(3\theta) |\psi_T\rangle + \cos(3\theta) |\psi_\perp\rangle.$$ (Note: The paper simplifies directly to $\sin(3\theta) |\psi_T\rangle + \cos(3\theta) |\psi_\perp\rangle$. The full algebraic steps confirm this result. This means that if the initial state is represented by an angle $\theta$ relative to the unmarked subspace, after one Grover iteration, it rotates to an angle $3\theta$, which is a rotation by $2\theta$ from the initial angle $\theta$.)

   Hence, each application of $G$ rotates the state vector by an angle $2\theta$ in the 2D subspace spanned by $\{|\psi_T\rangle, |\psi_\perp\rangle\}$. So, after $r$ Grover iterations, the state becomes: $$G^r |\psi_0\rangle = \sin((2r+1)\theta) |\psi_T\rangle + \cos((2r+1)\theta) |\psi_\perp\rangle.$$ The probability of observing a marked state (i.e., measuring a state in the target subspace) is the square of the amplitude of $|\psi_T\rangle$: $$P_{\mathrm{success}} = \sin^2((2r+1)\theta).$$

Corollary 1: The maximum success probability is achieved when $(2r+1)\theta \approx \frac{\pi}{2}$. The optimal number of iterations $r^\star$ is: $$r^\star = \left\lfloor \frac{\pi}{4\theta} - \frac{1}{2} \right\rfloor$$

4.2.6. Grover Geometry and Amplitude Dynamics

This section re-iterates and formalizes the Grover iteration as a unitary rotation.

Grover Operator Definition

Let $|\Psi\rangle$ be the uniform superposition state over all $N=4^n$ encoded maze paths: $$|\Psi\rangle = \frac{1}{\sqrt{N}} \sum_{x \in \mathcal{P}_n} |x\rangle$$ Let $O$ be the oracle operator that flips the sign of marked (high-fitness) solutions. Let $D = 2|\Psi\rangle\langle\Psi| - I$ be the Grover diffusion operator (reflection about $|\Psi\rangle$). The Grover iterate is: $$G = D \cdot O = (2|\Psi\rangle\langle\Psi| - I) \cdot O$$

Subspace Decomposition

Let $\mathcal{M}$ be the set of marked solutions with $|\mathcal{M}| = k$. Define two orthonormal vectors: $$|\Psi_T\rangle = \frac{1}{\sqrt{k}} \sum_{x \in \mathcal{M}} |x\rangle \quad (\text{target subspace})$$ $$|\Psi_\perp\rangle = \frac{1}{\sqrt{N-k}} \sum_{x \notin \mathcal{M}} |x\rangle \quad (\text{unmarked subspace})$$ The initial state $|\Psi\rangle$ decomposes as: $$|\Psi\rangle = \sqrt{\frac{k}{N}} |\Psi_T\rangle + \sqrt{1 - \frac{k}{N}} |\Psi_\perp\rangle = \sin(\theta) |\Psi_T\rangle + \cos(\theta) |\Psi_\perp\rangle$$ where $\theta = \arcsin\left(\sqrt{\frac{k}{N}}\right)$ is the initial angle between $|\Psi\rangle$ and the unmarked subspace.

Grover Rotation as Reflection Composition

• The oracle $O$ reflects about the unmarked subspace (or equivalently, applies a phase flip to the marked subspace): $$O |x\rangle = \left\{ \begin{array}{ll} -|x\rangle & \mathrm{if~} x \in \mathcal{M} \\ |x\rangle & \mathrm{otherwise} \end{array} \right.$$ This implies $O = I - 2\Pi_T$, where $\Pi_T = |\Psi_T\rangle\langle\Psi_T|$ is the projector onto the marked subspace.

• The diffuser $D$ reflects about the initial state $|\Psi\rangle$: $$D = 2|\Psi\rangle\langle\Psi| - I$$

• The composite operator $G = D \cdot O$ performs a rotation by an angle $2\theta$ in the 2D plane spanned by $\{|\Psi_T\rangle, |\Psi_\perp\rangle\}$.

  Proof (Revisited). Consider the action of $G$ on the initial state $|\Psi\rangle$.

1. Apply $O$: $$O |\Psi\rangle = O (\sin(\theta) |\Psi_T\rangle + \cos(\theta) |\Psi_\perp\rangle) = -\sin(\theta) |\Psi_T\rangle + \cos(\theta) |\Psi_\perp\rangle$$
2. Apply $D$: $$G |\Psi\rangle = D (O |\Psi\rangle) = (2|\Psi\rangle\langle\Psi| - I) (-\sin(\theta) |\Psi_T\rangle + \cos(\theta) |\Psi_\perp\rangle)$$ As shown in the previous section's proof, this results in: $$G |\Psi\rangle = \sin(3\theta) |\Psi_T\rangle + \cos(3\theta) |\Psi_\perp\rangle$$ By induction, after $r$ applications of $G$: $$G^r |\Psi\rangle = \sin((2r+1)\theta) |\Psi_T\rangle + \cos((2r+1)\theta) |\Psi_\perp\rangle$$ This demonstrates that each iteration of $G$ rotates the state vector by $2\theta$ towards the target subspace $|\Psi_T\rangle$.

Success Probability

The probability of measuring a marked state (i.e., a path with high fitness) after $r$ Grover iterations is given by the square of the amplitude of $|\Psi_T\rangle$: $$P_{\mathrm{success}}(r) = |\langle\Psi_T| G^r |\Psi\rangle|^2 = \sin^2((2r+1)\theta)$$ To maximize $P_{\mathrm{success}}$, the number of iterations $r$ should be chosen such that $(2r+1)\theta$ is as close as possible to $\frac{\pi}{2}$. The optimal number of iterations $r^\star$ is: $$r^\star = \left\lfloor \frac{\pi}{4\theta} - \frac{1}{2} \right\rfloor$$ This choice ensures that $P_{\mathrm{success}} \approx 1$.

4.2.7. Monotonic Cutoff Update Guarantees Convergence

This section introduces and proves the convergence of the adaptive cutoff strategy. The goal is to find the optimal path without prior knowledge of its fitness value.

The algorithm runs for $T$ iterations. In each iteration $t \in \{1, \ldots, T\}$, the algorithm observes a fitness value $f_t^*$ (from a measurement after Grover iterations) and updates a classical cutoff threshold $C_t$.

Definition 2 (Monotonic Cutoff Policy). Let $C_1 \in \mathbb{N}$ be an initial cutoff. Then define: $$C_{t+1} := \max(C_t, f_t^*) \quad \mathrm{for~} t = 1, \ldots, T-1$$ where:

• $C_t$ is the cutoff value at iteration $t$.
• $f_t^*$ is the observed fitness of a measured path in iteration $t$. Let $f_{\mathrm{max}} := \max_{x \in \mathcal{P}_n} f(x)$ be the maximum possible fitness (achieved by an optimal path).

Lemma 1 (Cutoff Sequence Properties). The sequence $\{C_t\}$ is non-decreasing and bounded above by $f_{\mathrm{max}}$.

Proof.

1. Monotonicity: From the update rule, $C_{t+1} = \max(C_t, f_t^*)$. By definition of the maximum function, $C_{t+1} \geq C_t$. This means $C_1 \leq C_2 \leq \ldots \leq C_T$, so the sequence is non-decreasing.
2. Boundedness: The observed fitness $f_t^*$ is always a fitness value of a path in $\mathcal{P}_n$, so $f_t^* \leq f_{\mathrm{max}}$ for all $t$. Therefore, $C_{t+1} = \max(C_t, f_t^*) \leq \max(C_t, f_{\mathrm{max}})$. If $C_t \leq f_{\mathrm{max}}$, then $C_{t+1} \leq f_{\mathrm{max}}$. By induction (assuming $C_1 \leq f_{\mathrm{max}}$, which is typically true for an initial low cutoff), $C_t \leq f_{\mathrm{max}}$ for all $t$. Since $\{C_t\}$ is a monotonic non-decreasing sequence of integers that is bounded above by $f_{\mathrm{max}}$, it must converge. $\blacksquare$

Theorem 3 (Finite-Time Convergence). The cutoff sequence $\{C_t\}$ converges to $f_{\mathrm{max}}$ in at most $f_{\mathrm{max}} - C_1$ steps.

Proof. Each time an observation $f_t^*$ is strictly greater than the current cutoff $C_t$ ($f_t^* > C_t$), the cutoff strictly increases: $$C_{t+1} = f_t^* > C_t \implies C_{t+1} > C_t.$$ Since $C_t$ is an integer-valued sequence and each strict increase means $C_{t+1} \geq C_t + 1$, the number of possible strict increments from $C_1$ to $f_{\mathrm{max}}$ is at most $f_{\mathrm{max}} - C_1$. Once $C_t$ reaches $f_{\mathrm{max}}$, it can no longer strictly increase because $f_t^* \leq f_{\mathrm{max}}$ for all $t$. Thus, the sequence stabilizes at $f_{\mathrm{max}}$ in at most $f_{\mathrm{max}} - C_1$ iterations. $\blacksquare$

Corollary 2 (Persistence of Maximum Amplification). Once $C_t = f_{\mathrm{max}}$, all optimal states $x^\star$ with $f(x^\star) = f_{\mathrm{max}}$ will be marked by the oracle in all subsequent iterations. The oracle marks states $x$ where $f(x) > C_t$. If $C_t = f_{\mathrm{max}}$, then for an optimal state $x^\star$, $f(x^\star) = f_{\mathrm{max}}$. The condition $f(x^\star) > C_t$ would be $f_{\mathrm{max}} > f_{\mathrm{max}}$, which is False. However, the paper states: "Therefore, the oracle permanently marks all global optima once cutoff reaches $f_{\mathrm{max}}$, enabling Grover amplification to amplify them indefinitely." This implies the oracle condition is actually $f_x \ge \mathrm{cutoff}$ rather than $f_x > \mathrm{cutoff}$ for optimal states. If the oracle definition is strictly $f_x > \mathrm{cutoff}$, then optimal states would not be marked once $C_t = f_{\mathrm{max}}$. If the intent is to mark optimal states, the definition of $g(f_x)$ should be $f_x \ge \mathrm{cutoff}$ instead of $f_x > \mathrm{cutoff}$. The paper's oracle definition uses > so there is a slight discrepancy here; for the corollary to hold, the oracle marking criterion would need to be $f_x \ge \mathrm{cutoff}$ for values equal to $f_{\mathrm{max}}$. Assuming the intent is to mark the optimal states, this implies a subtle adjustment to the oracle's comparison logic is necessary, or that the corollary implicitly refers to the set of states that led to $f_{\mathrm{max}}$ previously. Given the phrasing of the proof of Theorem 4, it's more likely that the oracle implicitly (or should be explicitly defined to) mark states with $f_x \geq \mathrm{cutoff}$ when $C_t = f_{\mathrm{max}}$. This corollary ensures that once the best possible fitness is identified, the algorithm consistently targets those optimal paths for amplification. $\blacksquare$

4.2.8. Convergence of Adaptive Cutoff Strategy

This section combines the monotonic convergence of the cutoff with the probabilistic nature of Grover's search to guarantee that the algorithm finds the maximum-fitness states with high probability.

The adaptive cutoff strategy requires only fitness observations and classical maximum tracking, making it simpler than running full Grover iterations with a priori known $k$ (number of marked states). It dynamically reduces the oracle's acceptance set until only global optima remain.

Let the quantum search be run over a Grover operator $G_t$ with an oracle defined by a cutoff value $C_t$ at each step. After each round, the cutoff is updated as: $C_{t+1} := \max(C_t, f_t^*),$ where $f_t^*$ is the observed fitness in the $t$-th iteration. It is assumed that fitness values are integers bounded above by $f_{\mathrm{max}} \leq 2m$ (which comes from the maximum possible squared Euclidean distance $2(m-1)^2$ and the constant $C=2^r$, where $r \approx \log_2(2m^2)$).

Theorem 4 (Cutoff Convergence). Let fitness values be bounded and the cutoff update rule be monotonic. Then with high probability, the algorithm halts with a solution $x^\star$ such that $f(x^\star) = f_{\mathrm{max}}$ after at most $T \le 2m$ steps with success probability at least $P_{\mathrm{success}} \geq 1 - \varepsilon$.

Proof. This proof combines the properties of the cutoff sequence with Grover's probabilistic success.

1. Cutoff Sequence Convergence: As proven in Theorem 3, the cutoff sequence $C_t$ is monotonic non-decreasing and bounded above by $f_{\mathrm{max}}$. If an initial $C_1 = 0$, then each update that finds a new maximum increases $C_t$ by at least 1. Thus, $C_t$ converges to $f_{\mathrm{max}}$ in at most $f_{\mathrm{max}} - C_1$ steps. Given $f_{\mathrm{max}} \leq 2m$, the number of rounds $T$ for the cutoff to reach $f_{\mathrm{max}}$ is at most 2m.

2. Grover's Probabilistic Guarantee: At each step $t$, Grover's search is run for $r_t$ iterations with an oracle threshold $C_t$. Let $\theta_t$ be the angle defined by: $$\sin^2 \theta_t = \frac{k_t}{N}, \quad \mathrm{where} \quad k_t = |\{x : f(x) > C_t\}|, \quad N = 4^n.$$ By Grover's geometry, the success probability of measuring a marked state after $r_t$ rounds is: $$P_t = \sin^2((2r_t+1)\theta_t).$$ If $r_t$ is chosen such that $(2r_t+1)\theta_t \approx \frac{\pi}{2}$, then $P_t \ge 1 - \delta_t$, where $\delta_t$ is a small error probability for that round.

3. Overall Success Probability: Let $\varepsilon$ be the total allowable failure budget for the entire process. If we set $\delta_t = \varepsilon/T$ for each of the $T$ rounds (or more generally, ensure $\sum_t \delta_t \le \varepsilon$), then with probability at least $1 - \varepsilon$, at least one round will succeed in returning an $x^*$ such that $f(x^*) \ge C_t$. This means we will eventually observe a path that allows $C_t$ to increase.

4. Final Optimal Solution: Once $C_t = f_{\mathrm{max}}$, the oracle, according to Corollary 2, marks only the optimal solutions (paths with fitness $f_{\mathrm{max}}$). By running Grover's algorithm again with this final cutoff, the final amplification step will return a true optimum with probability $\ge 1 - \delta_{final}$ (where $k$ would be the number of optimal paths).

   Thus, the adaptive procedure converges to $f_{\mathrm{max}}$ within $T \leq 2m$ rounds, and the final measurement will yield an optimal path with high probability ($1 - \varepsilon$). $\blacksquare$

4.3. Resource Summary

The paper provides a summary of the quantum resource requirements for the full Grover-style quantum maze solver circuit in the Appendix.

The following are the results from Table I of the original paper:

Resource Notes:

• Arithmetic: All arithmetic operations, such as computing $(i - i_f)$, squaring, and $C - d$, are performed using known quantum arithmetic primitives like Cuccaro-style ripple-carry adders and CNOT-based multipliers.
• Comparator Cost: The cost of the comparator scales with the number of qubits in the fitness register, $m_f = \lceil \log_2(2m) \rceil$.
• Ancilla Efficiency: The design emphasizes ancilla-efficient techniques such as uncomputation and Bennett-style cleanup to reduce the overall qubit overhead by reusing temporary registers.
• Scaling Insights:
  • Linear scaling in path length $n$: This comes from the sequential decoding and movement updates for each of the $n$ steps in a path.
  • Logarithmic scaling in maze size $m$: This is due to the positional coordinates requiring $\lceil \log_2 m \rceil$ qubits, and arithmetic operations scaling polynomially with the number of bits.

5. Experimental Setup

The paper primarily presents a theoretical algorithmic framework with formal proofs and resource analysis, rather than empirical experimental results using specific quantum hardware or simulators. Therefore, the "experimental setup" is conceptual, focusing on the problem instance for illustration and the inherent metrics of quantum algorithms.

5.1. Datasets

The paper does not use traditional datasets. Instead, it defines the problem for a general perfectm \times mgrid maze. For illustrative purposes, an example2 \times 2maze is used in the appendix to walk through the algorithm's steps.

Concrete Example of a Data Sample: The example maze is a $2 \times 2$ grid.

• Start cell: $(i_s, j_s) = (0,0)$

• Goal cell: $(i_f, j_f) = (1,1)$

• Path length: $n=2$ (meaning paths consist of 2 moves)

  Directions are encoded as:

• $N = 00$

• $E = 01$

• $S = 10$

• $W = 11$

  A path of length $n=2$ corresponds to a $2n=4$ qubit register. The total number of candidate paths is $4^n = 4^2 = 16$.

Example Path (from the paper's appendix): A specific path considered is $|x\rangle = |1001\rangle$. This decodes to $S$ (10) followed by $E$ (01). Simulation of this path:

1. Starts at $(0,0)$.
2. Move $S$ (South): $(0,0) \to (1,0)$.
3. Move $E$ (East): $(1,0) \to (1,1)$. The path successfully reaches the goal $(1,1)$.

These types of small maze configurations are chosen because they are simple enough to manually verify the steps of the algorithm (encoding, simulation, fitness calculation, oracle action) and illustrate the principles without requiring extensive computation. They are effective for validating the conceptual correctness and step-by-step logic of the proposed quantum circuits.

5.2. Evaluation Metrics

The paper implicitly evaluates the algorithm based on the following:

5.2.1. Success Probability ($P_{\mathrm{success}}$)

Conceptual Definition: This metric quantifies the likelihood of measuring a desired (marked, high-fitness) state after performing Grover iterations. In the context of maze solving, it represents the probability of measuring an optimal or near-optimal path. The goal of Grover's algorithm is to maximize this probability, ideally to nearly 1.

Mathematical Formula: $$P_{\mathrm{success}}(r) = \sin^2((2r+1)\theta)$$ Symbol Explanation:

• $P_{\mathrm{success}}(r)$: The probability of successfully measuring a marked state after $r$ Grover iterations.
• $r$: The number of Grover iterations performed.
• $\sin^2(\cdot)$: The square of the sine function, which yields a probability value between 0 and 1.
• $\theta$: The initial angle of the state vector in the 2D plane spanned by marked and unmarked states. It is defined as $\theta = \arcsin\left(\sqrt{\frac{k}{N}}\right)$.
• $k$: The number of marked (high-fitness) states.
• $N$: The total number of states in the search space (total number of candidate paths, $4^n$).

5.2.2. Quantum Resource Cost (Qubit Count, Gate Depth, Gate Types)

Conceptual Definition: These metrics assess the practical feasibility and efficiency of the quantum algorithm on real or theoretical quantum hardware.

• Qubit count indicates the minimum number of qubits required to run the algorithm. Lower qubit counts are desirable for current NISQ devices.
• Gate depth (or circuit depth) refers to the longest sequence of quantum gates that must be executed sequentially. Lower depth is critical for NISQ devices due to limited coherence times and increasing error rates with more gates.
• Gate types (e.g., Toffoli gates, CNOT gates) indicate the complexity and universality requirements of the quantum hardware.

Mathematical Formula/Asymptotic Costs (from Table I, see 4.3):

• Qubit Count:
  • Path register: 2n qubits
  • Position registers: $2 \cdot \lceil \log_2 m \rceil$ qubits
  • Distance register: $\lceil \log_2 m \rceil$ qubits
  • Fitness register: $\lceil \log_2(2m) \rceil$ qubits
  • Total ancilla: $O(n \log m)$ qubits
• Gate Depth (for 1 Grover round): $O(n \log m)$
• Gate Types (dominant): Toffoli gates, CNOT gates.

Symbol Explanation:

• $n$: Length of the path.
• $m$: Dimension of the maze grid (e.g., for an $m \times m$ maze).
• $\lceil \cdot \rceil$: The ceiling function, which rounds up to the nearest integer.
• $O(\cdot)$: Big O notation, indicating the asymptotic upper bound of the growth rate of the cost.

5.3. Baselines

The paper primarily compares its quantum algorithm against classical approaches implicitly, particularly emphasizing the exponential scaling behavior of classical search algorithms like backtracking and breadth-first search. It highlights that these classical methods are computationally intractable for large instances.

The paper does not explicitly compare against other quantum maze-solving algorithms with concrete circuit implementations. It notes that previous quantum approaches were often conceptual or lacked rigorous definitions for key components. Therefore, the baseline for comparison is the general computational efficiency of classical algorithms versus the potential quadratic speedup offered by Grover's algorithm.

6. Results & Analysis

The paper presents theoretical results, formal proofs, and a resource analysis, rather than empirical experimental data. The primary "results" are the validated correctness, unitarity, convergence properties, and scaling characteristics of the proposed quantum algorithm.

6.1. Core Results Analysis

The paper's core results strongly validate the effectiveness of its proposed quantum algorithm for solving perfect mazes:

• Formal Correctness and Unitarity: The algorithm's fundamental components—the quantum encoding, reversible fitness operator, and Grover-compatible oracle—are formally defined and proven to be correct and unitary.

  • Theorem 1 (Superposition Correctness): This theorem rigorously establishes that the initial state preparation method (applying $H^{\otimes 2}$ to 2-qubit blocks) correctly creates a uniform superposition over all valid path encodings. This is crucial for Grover's algorithm, as it ensures all candidate solutions are equally represented initially.
  • Theorem 2 (Fitness Operator is Unitary): The proof confirms that the fitness operator $F$, constructed from reversible quantum arithmetic primitives, is unitary. This is a non-trivial result, as ensuring reversibility for complex arithmetic operations (like path simulation, distance calculation, and subtraction) is a core challenge in quantum circuit design. Unitarity guarantees that the operation can be implemented without information loss or decoherence (in an ideal scenario).
  • Oracle Unitarity: The oracle's unitarity is also formally demonstrated, being composed of a reversible comparator and a controlled-Z gate. This ensures that the marking of high-fitness states does not introduce non-unitary behavior.

• Guaranteed Convergence of Adaptive Cutoff Strategy: The adaptive cutoff strategy is a significant innovation that addresses a practical challenge in Grover's algorithm—the need to know the number of marked states $k$ (or optimal fitness) beforehand.

  • Lemma 1 (Cutoff Sequence Properties): Proves that the cutoff value $C_t$ is non-decreasing and bounded above by the maximum possible fitness $f_{\mathrm{max}}$. This property is fundamental for guaranteeing convergence.
  • Theorem 3 (Finite-Time Convergence): This theorem guarantees that the cutoff sequence converges tof_{\mathrm{max}} in a finite number of steps (at most $f_{\mathrm{max}} - C_1$). This means the algorithm will eventually identify the optimal fitness value. * **Corollary 2 (Persistence of Maximum Amplification):** States that once the cutoff reaches $f_{\mathrm{max}}$, the oracle will permanently mark all `global optima`. This ensures that subsequent `Grover iterations` will exclusively amplify the true best solutions. * **Theorem 4 (Cutoff Convergence):** Combines these elements to prove that the adaptive procedure will halt with a solution achieving $f_{\mathrm{max}}$ (i.e., an optimal path) with `high probability` ($1-\varepsilon$) within a bounded number of iterations ($T \le 2m$). This probabilistic guarantee, combined with bounded runtime, makes the algorithm robust and practical. * **Efficient Resource Scaling:** The `resource analysis` provided in the Appendix highlights the algorithm's efficiency. * **Qubit Count:** The qubit count scales linearly with path length $n$ (`2n` for path encoding) and logarithmically with maze size $m$ ($O(\log m)$ for position, distance, and fitness registers). The total `ancilla` qubits are $O(n \log m)$, demonstrating efficient use of qubits given the problem complexity. * **Gate Depth:** The `Grover iteration depth` (for one round) scales as $O(n \log m)$. This logarithmic dependence on maze size is particularly advantageous for larger mazes. The use of reversible arithmetic techniques (e.g., `Cuccaro adders`) contributes to this efficiency. * **Comparison with Classical Baselines:** While not explicitly tabulated against classical algorithms, the implied advantage is that classical search for $N$ paths takes $O(N)$ time (e.g., BFS worst case) while Grover's algorithm (after $r^\star$ iterations) takes $O(\sqrt{N})$ queries to the oracle. Combined with the $O(n \log m)$ depth per oracle query, the total complexity would be roughly $O(\sqrt{N} \cdot n \log m) = O(\sqrt{4^n} \cdot n \log m) = O(2^n \cdot n \log m)$. This still appears exponential in $n$. However, the `quadratic speedup` applies to the number of *queries* to the oracle. The oracle itself has a complexity. The "efficient scaling" refers to the polynomial dependence on $n$ and $m$ within the oracle, which is typically what is focused on for `Grover's algorithm` applications. For `unstructured search`, $\sqrt{N}$ is the query complexity. Here, the structure of the oracle is taken into account. ## 6.2. Data Presentation (Tables) The paper includes a table summarizing the circuit resource cost. The following are the results from Table I of the original paper: <div class="table-wrapper"><table> <thead> <tr> <td>Parameter</td> <td>Asymptotic Cost</td> </tr> </thead> <tbody> <tr> <td>Path register size ($|x\rangle$)</td> <td>`2n` qubits</td> </tr> <tr> <td>Position registers ($|i\rangle, |j\rangle$)</td> <td>$2 \cdot \lceil \log_2 m \rceil$ qubits</td> </tr> <tr> <td>Distance register ($|d\rangle$)</td> <td>$\lceil \log_2 m \rceil$ qubits</td> </tr> <tr> <td>Fitness register ($|f\rangle$)</td> <td>$\lceil \log_2(2m) \rceil$ qubits</td> </tr> <tr> <td>Comparator ancilla ($|b\rangle$, carry bits)</td> <td>$O(\log m)$ qubits</td> </tr> <tr> <td>Total ancilla (adder, comparator, cleanup)</td> <td>$O(n \log m)$ qubits</td> </tr> <tr> <td>Toffoli gates (path simulation)</td> <td>$O(n \log m)$</td> </tr> <tr> <td>Toffoli gates (distance + fitness)</td> <td>$O(\log^2 m)$</td> </tr> <tr> <td>Toffoli gates (oracle comparator)</td> <td>$O(\log m)$</td> </tr> <tr> <td>Grover iteration depth (1 round)</td> <td>$O(n \log m)$</td> </tr> </tbody> </table></div> ## 6.3. Ablation Studies / Parameter Analysis The paper does not present explicit `ablation studies` in the traditional sense (e.g., removing components to see performance degradation). However, it implicitly performs a `parameter analysis` through its discussion of the `path length parameter $n$` and the introduction of the `adaptive cutoff strategy`. * **Path Length Parameter $n$**: The paper highlights the crucial choice of $n$: * If $n < \mathrm{length}(P^*)$, the true solution is excluded. * If $n > \mathrm{length}(P^*)$, the search space includes redundant or invalid paths. While the paper assumes $n \ge \ell_{\mathrm{min}}$ (minimum path length), it suggests that this value "may be set heuristically or adapted in an iterative process." This implies that $n$ is a tunable parameter, and its optimal setting is critical. The `linear scaling in path length $n$` for `Toffoli gates` and `Grover iteration depth` means that choosing an overly long $n$ will directly increase resource costs. * **Adaptive Cutoff Strategy**: The `adaptive cutoff strategy` itself can be seen as an iterative refinement of a key parameter (`cutoff`). Its analysis demonstrates how this parameter is dynamically adjusted. * **Effect on Search:** By incrementally increasing the `cutoff`, the `oracle` becomes more selective, reducing the number of `marked states $k$`. This changes the `Grover angle`\theta = \arcsin(\sqrt{k/N}), affecting the optimal number of Grover iterationsr^\star$$. As $k$ decreases, $\theta$ decreases, and $r^\star$ increases, meaning more iterations are needed per round, but the search becomes increasingly focused on higher-quality solutions.
  • Convergence Guarantee: The proofs for monotonic non-decreasing nature and finite-time convergence of the cutoff confirm that this adaptive approach effectively guides the search towards optimal paths, mitigating the need for prior knowledge about the optimal fitness value. This is a critical functional analysis of a core parameter's dynamic behavior.

7. Conclusion & Reflections

7.1. Conclusion Summary

This paper successfully presents a comprehensive quantum algorithmic framework for solving perfect mazes using Grover's amplitude amplification. It provides a full theoretical pipeline, starting from formally defining the maze and path representations to specifying the quantum operations for encoding, fitness evaluation, oracle design, and iterative amplitude amplification. Key contributions include the rigorous definition and construction of a reversible fitness operator using quantum arithmetic and a Grover-compatible oracle with a reversible comparator. Crucially, an adaptive cutoff strategy is introduced and proven to guarantee monotonic improvement and finite-time convergence to an optimal solution with high probability. The accompanying resource analysis demonstrates efficient scaling of qubit count and circuit depth with maze size and path length, supporting its potential feasibility.

7.2. Limitations & Future Work

The authors acknowledge several limitations and propose future research directions:

• Idealized Assumptions: The current framework operates under idealized conditions, assuming noiseless quantum gates and perfect measurements. This is a common assumption in theoretical quantum algorithm design but deviates from the reality of current quantum hardware.
• NISQ Device Suitability: Directly related to the idealized assumptions, the algorithm's performance on Noisy Intermediate-Scale Quantum (NISQ) devices is not fully addressed. NISQ devices suffer from high error rates and limited coherence times.

Proposed Future Work:

• Error Mitigation/Fault Tolerance: Extending the algorithm to NISQ devices through error mitigation or fault-tolerant techniques (e.g., surface codes) is a crucial next step.
• Generalization to Complex Environments: The current work focuses on perfect mazes (acyclic, tree-like graphs). Future work could generalize the framework to:
  • Mazes with cycles.
  • Dynamically evolving topologies.
  • Environments with weighted traversal costs.
• Alternative Quantum Models: Investigating the integration of the approach with quantum walk models or variational oracle constructions could lead to further performance improvements.
• Hybrid Classical-Quantum Approaches: Exploring hybrid classical-quantum preprocessing to reduce the effective search space before quantum execution could enhance practicality on near-term hardware. This suggests a recognition that a purely quantum solution might still be resource-intensive for very large problems, and classical optimization steps could offload some computational burden.

7.3. Personal Insights & Critique

• Innovation in Rigor: The paper's most significant strength is its rigorous definition and circuit-level specification of every component. Many quantum algorithm papers focus on the high-level speedup but leave the intricate unitary construction to implementation. This paper fills that gap, especially for the fitness operator and oracle, which are often non-trivial for real-world problems. The proofs of unitarity and convergence are particularly valuable for building confidence in the theoretical soundness.
• Practicality of Adaptive Cutoff: The adaptive cutoff strategy is a clever and practical addition. In real-world optimization problems, knowing the optimal fitness beforehand is rare. This strategy makes the Grover-based search more robust and applicable to black-box optimization scenarios where the quality of solutions is learned dynamically. This feature enhances the algorithm's applicability beyond purely theoretical exercises.
• Extensibility: The framework's stated extensibility to tree-like or acyclic graphs is promising. This broadens the impact beyond just mazes, potentially covering problems in network routing, decision trees, or certain types of database queries.
• Potential Issues/Unverified Assumptions:
  • Oracle Definition Discrepancy: As noted in the analysis of Corollary 2, there appears to be a minor discrepancy in the oracle definition: if $g(f_x) = 1$ for $f_x > cutoff$, then f_max itself would not be marked when $cutoff = f_max$. For the corollary to hold, the oracle condition for optimal states might need to be $f_x >= cutoff$. This is a subtle but important point for the exact behavior of the algorithm at convergence.
  • Cost of $n$: While logarithmic scaling with $m$ is excellent, linear scaling with $n$ (path length) for Toffoli gates and Grover iteration depth is still significant. The total complexity involves $2^n$ from the sqrt(N) factor. This means that for very long paths, the algorithm might still be challenging on NISQ devices, even with the quadratic speedup in query complexity. For an $N = 4^n$ search space, the $\sqrt{N}$ factor is $2^n$. The overall complexity remains exponential in $n$ (the length of the path), even if it's a quadratic speedup over $4^n$. This needs to be considered when comparing it to classical algorithms whose complexity might be polynomial in $n$ but exponential in $m$. For maze solving, $n$ can be roughly proportional to $m^2$ in worst-case (e.g., a snake-like path). So, the "efficient scaling" is relative.
  • Qubit Count for Practical Mazes: For a $100 \times 100$ maze ($m=100$) and a path length of $n=200$ (a reasonable path in a $100 \times 100$ maze), $2n = 400$ qubits for the path register alone is a substantial requirement for current hardware. The total ancilla $O(n \log m)$ would be $O(200 \cdot \log_2 100) \approx O(200 \cdot 7) = O(1400)$ qubits. This makes it a target for future fault-tolerant quantum computers rather than near-term devices.
• Transferability: The methods, particularly the reversible arithmetic for fitness evaluation and the adaptive cutoff strategy, are highly transferable.

  • Reversible Arithmetic: The techniques used for path simulation, distance calculation, and fitness scoring are general and could be applied to any problem requiring arithmetic computations within a quantum circuit, especially in optimization or simulation tasks.

  • Adaptive Search: The adaptive cutoff strategy is a general technique for Grover's algorithm when the number of solutions or optimal value is unknown. It could be adapted to other black-box optimization or search problems across various domains like materials science, drug discovery, or financial modeling.

    Overall, this paper makes a strong contribution by providing a thoroughly detailed and proven quantum algorithm, laying important groundwork for future developments in quantum pathfinding and optimization.