Applications of the Adversary Method in Quantum Query Algorithms
arXiv:1402.3858
Abstract
In the thesis, we use a recently developed tight characterisation of quantum query complexity, the adversary bound, to develop new quantum algorithms and lower bounds. Our results are as follows: * We develop a new technique for the construction of quantum algorithms: learning graphs. * We use learning graphs to improve quantum query complexity of the triangle detection and the -distinctness problems. * We prove tight lower bounds for the -sum and the triangle sum problems. * We construct quantum algorithms for some subgraph-finding problems that are optimal in terms of query, time and space complexities. * We develop a generalisation of quantum walks that connects electrical properties of a graph and its quantum hitting time. We use it to construct a time-efficient quantum algorithm for 3-distinctness.
arXiv commentPhD Thesis, 169 pages
References in corpus (26)
- Strengths and Weaknesses of Quantum Computing
- Quantum Amplitude Amplification and Estimation
- Quantum Algorithms Revisited
- Exponential algorithmic speedup by quantum walk
- Quantum computers can search rapidly by using almost any transformation
- Architectures for a quantum random access memory
- Search via Quantum Walk
- An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
- Quantum Algorithm for the Collision Problem
- Negative weights make adversaries stronger
- Complexity limitations on quantum computation
- The quantum query complexity of the hidden subgroup problem is polynomial
- Quantum Search on Bounded-Error Inputs
- Quantum lower bounds for the collision and the element distinctness problems
- Lower Bounds on Quantum Query Complexity
- A Robust Quantum Random Access Memory
- Models of quantum computation and quantum programming languages
- Learning-Graph-Based Quantum Algorithm for k-distinctness
- Quantum Walks and Electric Networks
- Quantum Algorithm for k-distinctness with Prior Knowledge on the Input
- Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates
- On the Quantum Query Complexity of Detecting Triangles in Graphs
- A learning graph based quantum query algorithm for finding constant-size subgraphs
- Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
- A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates
- Symmetry-assisted adversaries for quantum state generation