Nested Quantum Walks with Quantum Data Structures

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.

References in corpus (5)

• Quantum query complexity of state conversion
• Learning-Graph-Based Quantum Algorithm for k-distinctness
• Quantum Algorithm for k-distinctness with Prior Knowledge on the Input
• Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates
• A learning graph based quantum query algorithm for finding constant-size subgraphs

Cited by in corpus (9)

• Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments
• Tower: Data Structures in Quantum Superposition
• Quantum Walks and Electric Networks
• Quantum Algorithm for Triangle Finding in Sparse Graphs
• Quantum Algorithm for Lexicographically Minimal String Rotation
• Derandomization of quantum algorithm for triangle finding
• Data Structures in Classical and Quantum Computing
• Quantum Data Structure for Range Minimum Query
• Quantum Approximate Counting for Markov Chains and Application to Collision Counting