Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913344489783296 |
|---|---|
| author | Jeffery, Stacey Pass, Galina |
| author_facet | Jeffery, Stacey Pass, Galina |
| contents | We introduce an object called a \emph{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 \emph{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_08355 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer Jeffery, Stacey Pass, Galina Quantum Physics Data Structures and Algorithms We introduce an object called a \emph{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 \emph{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. |
| title | Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2401.08355 |