# Techniques: Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs

## What the paper contributes (one paragraph)
The paper gives quantum algorithms and matching-style query lower bounds for computing the diameter, radius, and eccentricity of undirected, weighted graphs in the adjacency list model (arXiv:2502.20148). It presents an exact quantum algorithm that returns the diameter and radius, together with the witnessing paths, in time O(n sqrt(m)), built by nesting quantum search over a quantum single-source shortest paths subroutine and offloading one layer of search into the oracle. For diameter it gives the first quantum approximation algorithm, achieving a 2/3 ratio in time O(sqrt(m) n^{3/4}) via a quantum partial breadth-first search subroutine that uses quantum threshold searching. On the hardness side it proves an Omega(sqrt(nm)) quantum query lower bound for all three problems through a combinatorial reduction from quantum minima finding on items of different types, improving the previous Omega(n) bound for dense graphs.

## Techniques offered
- **Quantum shortest-path-based diameter and radius algorithm** - nests quantum search over a quantum single-source shortest paths subroutine to output the exact diameter and radius with witnessing paths in O(n sqrt(m)) time.
  - guarantee: bounded-error quantum algorithm returning exact diameter/radius plus a witness path with time complexity O~(n sqrt(m)).
  - quote: "Our quantum algorithm combines the quantum search~\cite{boyer1998tight} with quantum single source shortest paths (SSSP) algorithm~\cite{durr2006quantum}."
- **Quantum 2/3-approximation algorithm for diameter (quantum partial BFS)** - refines partial breadth-first search in the quantum setting using quantum threshold searching to estimate the diameter within a 2/3 ratio in O(sqrt(m) n^{3/4}) time.
  - guarantee: approximation guarantee 2/3 D <= D_hat <= D with a corresponding path, returned in O~(m^{1/2} n^{3/4}) time, with high probability.
  - quote: "Instead of simply quantizing the classical algorithm, we refine the analysis of partial breadth-first search in the quantum setting by leveraging the quantum threshold searching~\cite{ambainis2004quantum}."
- **Quantum query lower bound via reduction from minima finding** - a combinatorial reduction from quantum minima finding on d items of different types yielding an Omega(sqrt(nm)) query lower bound for eccentricity, diameter, and radius.
  - guarantee: unconditional quantum query lower bound of Omega(sqrt(nm)) for all three problems, improving the previous Omega(n) bound for dense graphs.
  - quote: "We show that we can obtain an $\Omega(\sqrt{nm})$ query lower bound for all of the considered problems by reducing from quantum minima finding on $d$ items of different types~\cite{durr2006quantum}."

## Where it could apply
- Target primitive(s): sampling and amplitude-based search subroutines (quantum search, quantum minimum finding, quantum threshold finding); shortest-path and graph-traversal subroutines (quantum SSSP, quantum BFS).
- Target application group(s): platforms_tooling; optimization.
- Code family / hardware assumptions: none (model-level results assuming the QRAG quantum memory model and adjacency list oracle access; no code family or physical hardware assumed).

## Caveats
This is a query-complexity and algorithms paper, not a supplier of accreditation, decoding, error correction, or mitigation primitives. The contributions are theoretical graph algorithms and lower bounds in the adjacency list model under the QRAG memory model; what is suppliable to an external result is the algorithmic speedup and the lower-bound reduction technique, not a hardware-facing capability. Do not use the em dash character.