Optimizing Urban Accessibility: Quantum Acceleration of the Steiner Tree for the 15-Minute City

Overview

Urban accessibility optimization is a pressing challenge for sustainable urban development. Classical graph-theoretical methods, such as the Steiner tree problem, provide a framework for constructing 15-minute cities but face exponential computational barriers at the metropolitan scale. Classical algorithms remain intractable for hundreds of service locations, limiting real-time and city-wide feasibility. This study investigates how quantum algorithms can overcome these bottlenecks to enable scalable planning using an originally-developed quantum-enhanced framework for the minimum Steiner tree problem, leveraging the Miyamoto et al. algorithm and integrating quantum shortest path subroutines. The methodology combines quantum parallelism, flow state sparsification, and minimum finding with classical dynamic programming in a hybrid approach. Manhattan's urban network served as a case study, with experiments comparing classical and quantum performance across thousands of nodes and hundreds of service terminals. Results demonstrate exponential quantum speedup, enabling analysis of 100 service locations compared to the classical limit of 50; the Manhattan case yielded a 1.94 times 104 acceleration. Quantum integration supported equity-focused optimization and scenario analysis across diverse service types, showing that previously intractable problems become solvable. In conclusion, quantum-enhanced Steiner tree optimization provides a practical pathway for sustainable urban development, enabling planners to account for equity, environmental, and accessibility constraints. Beyond cities, the approach establishes a foundation for quantum acceleration in other domains requiring large-scale combinatorial optimization, like supply chain management and telecommunications.

Awards (1)

• American Mathematical Society: Honorable Mention and One-Year Membership to AMS (for 5 projects with up to 3 team members per project)

Competition history

• ISEF 2026 Mathematics · Entry MATH037

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.