2026-09-13T16:03:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22879 2026-09-05T17:59:41Z ddc:004 open_access

Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer Jeffery, Stacey Pass, Galina Quantum Divide & Conquer Time-Efficient Subspace Graphs Quantum Walks Switching Networks Directed st-Connectivity We introduce an object called a subspace graph that formalizes the technique of multidimensional quantum walks. Composing subspace graphs allows one to seamlessly combine quantum and classical reasoning, keeping a classical structure in mind, while abstracting quantum parts into subgraphs with simple boundaries as needed. As an example, we show how to combine a switching network with arbitrary quantum subroutines, to compute a composed function. As another application, we give a time-efficient implementation of quantum Divide & Conquer when the sub-problems are combined via a Boolean formula. We use this to quadratically speed up Savitch’s algorithm for directed st-connectivity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stacey Jeffery and Galina Pass 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.54 urn:nbn:de:0030-drops-228791 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.54 eng https://creativecommons.org/licenses/by/4.0/legalcode