Applications of the Adversary Method in Quantum Query Algorithms

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 $k$-distinctness problems. * We prove tight lower bounds for the $k$-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.

PhD Thesis, 169 pages

References in corpus (7)

• Exponential algorithmic speedup by quantum walk
• Architectures for a quantum random access memory
• Learning-Graph-Based Quantum Algorithm for k-distinctness
• Quantum Walks and Electric Networks
• On the Quantum Query Complexity of Detecting Triangles in Graphs
• A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates
• Symmetry-assisted adversaries for quantum state generation

Cited by in corpus (3)

• Quantum Coupon Collector
• Taming Quantum Time Complexity
• Provably secure key establishment against quantum adversaries