Nested Quantum Walks with Quantum Data Structures

DOI10.1137/1.9781611973105.106MaRDI QIDQ5741815zbMATH OpenOpenAlexFDO

Authors Stacey Jeffery, Robin Kothari, Frédéric Magniez

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.1199

Mathematics Subject Classification ID

Random walks on graphs (05C81) Data structures (68P05) Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: We develop a new framework that extends the quantum walk framework of Magniez, Nayak, Roland, and Santha, by utilizing the idea of quantum data structures to construct an efficient method of nesting quantum walks. Surprisingly, only classical data structures were considered before for searching via quantum walks. The recently proposed learning graph framework of Belovs has yielded improved upper bounds for several problems, including triangle finding and more general subgraph detection. We exhibit the power of our framework by giving a simple explicit constructions that reproduce both the $O(n^{35/27})$ and $O(n^{9/7})$ learning graph upper bounds (up to logarithmic factors) for triangle finding, and discuss how other known upper bounds in the original learning graph framework can be converted to algorithms in our framework. We hope that the ease of use of this framework will lead to the discovery of new upper bounds.

Recommendations

• Discrete-time quantum walks and graph structures
• QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
• Quantum walks on embeddings
• Quantum walks on graphs
• Quantum walks and search algorithms
• Quantum walks and search algorithms
• Quantum Walks
• Quantum walks
• Quantum walks on hypergraphs
• Quantum walks with memory on cycles

Cited in

(11)

• Quantum algorithm design: techniques and applications
• Improved quantum query algorithms for triangle detection and associativity testing
• Quantum algorithm for lexicographically minimal string rotation
• Near-optimal quantum algorithms for string problems
• Recovering the original simplicity: succinct and exact quantum algorithm for the welded tree problem
• Quantum data structure for range minimum query
• Derandomization of quantum algorithm for triangle finding
• A unified framework of quantum walk search
• On quantum query complexities of collision-finding in non-uniform random functions
• Parameterized quantum query algorithms for graph problems
• Quantum algorithms for finding constant-sized sub-hypergraphs

This page was built for publication: Nested Quantum Walks with Quantum Data Structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741815)